구현에 앞서서..
- 리스트 연결 최소 단위는 Node입니다.
- 연결 리스트의 마지막 노드가 가장 첫 번째 head 노드를 가리켜야 합니다.
- 조회, 삽입, 삭제 과정이 존재합니다.
Node 구현
template <typename T>
class Node
{
// 1. Node는 prev, data, next 로 이루어져 있습니다.
public:
Node(Node<T>* prev, T data, Node<T>* next)
: prev(prev)
, data(data)
, next(next)
{
}
Node(T data)
: prev(nullptr)
, data(data)
, next(nullptr)
{
}
Node()
: prev(nullptr)
, data(0)
, next(nullptr)
{
}
public:
Node* prev;
int data;
Node* next;
};
이중 원형 연결 리스트의 설계도
template <typename T>
class CircularDoublyLinkedList
{
// 1. 이중 원형 연결 리스트 초기화 구현
public:
CircularDoublyLinkedList()
: head(nullptr)
, tail(nullptr)
, size(0)
{
}
// 2. 이중 원형 연결 리스트 삽입 구현
void insertData(T data);
// 3. 이중 원형 연결 리스트 삭제 구현
void deleteData(T data);
// 4. 이중 원형 연결 리스트 탐색 구현
Node<T>* searchData(T data);
public:
// head 노드로 빈 노드를 두지 않는다.
Node<T>* head;
Node<T>* tail;
int size;
};
head : 이중 원형 연결리스트의 첫번째 노드, prev 노드가 tail
tail : 이중 원형 연결리스트의 마지막 노드, next 노드가 head
size : 연결리스트에 노드가 얼마나 들어있는지를 파악하기 위함.
insertData(T data) : 이중 원형 연결 리스트의 삽입 구현
deleteData(T data) : 이중 원형 연결 리스트의 삭제 구현
searchData(T data) : 이중 원형 연결 리스트의 탐색 구현
1. searchData(T data) : 데이터 탐색
template<typename T>
Node<T>* CircularDoublyLinkedList<T>::searchData(T data)
{
Node<T>* cur = head;
// 1. head Node로 접근
for (int i = 0; i < size; ++i)
{
if (cur->data == data)
{
return cur;
}
cur = cur->next;
}
return nullptr;
}
int size 변수를 통해 현재 들어오는 Node 개수를 알 수 있으므로 for문을 이용하여 node들을 순회합니다.
- data에 해당하는 Node가 존재하면 해당 Node를 반환합니다.
- data에 해당하는 Node가 존재하지 않는다면 nullptr을 반환합니다.
2. insertData(T data) : 데이터 삽입
template<typename T>
void CircularDoublyLinkedList<T>::insertData(T data)
{
// 1. data가 있는지 확인. searchData(data)
if (searchData(data) != nullptr)
{
return;
}
// 2. 없다면 노드 생성
Node<T>* node = new Node<T>(data);
// 3. 삽입 시 과정 수행
if (head == nullptr)
{
head = node;
tail = node;
node->prev = node;
node->next = node;
}
else
{
tail->next = node;
node->prev = tail;
node->next = head;
head->prev = node;
tail = node;
}
++size;
}
데이터가 있다면 이미 데이터가 존재하므로 삽입하지 않습니다.
- 데이터가 없다면 받은 데이터 값으로 Node를 생성합니다.
- 삽입 시 head Node가 없다면 해당 Node는 head Node가 됩니다.
- head Node가 존재한다면 가장 뒤의 tail Node의 연결 관계를 수정하고 tail Node로 만듭니다.
- node 개수를 파악하기 위해 size 변수를 증가 시킵니다.
head Node만 있는 경우
- 현재 Node를 head, tail Node로 설정
- 현재 Node의 prev, next를 현재 Node로 설정
head Node만 있는 것이 아닌 경우
- 현재 tail Node의 next를 node로 설정
- 현재 node의 prev를 tail로 설정
- 현재 node의 next를 head로 설정
- 현재 head의 prev Node를 node로 설정.
- tail Node를 현재 node로 설정
3. deleteNode(T data) : 데이터 삭제
template<typename T>
void CircularDoublyLinkedList<T>::deleteData(T data)
{
// 1. data가 있는지 확인
Node<T>* cur = searchData(data);
if (cur == nullptr)
{
return;
}
// 2. data가 있다면 연결관계 수정
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
if (head == cur && tail == cur)
{
head = nullptr;
tail = nullptr;
}
else if (tail == cur)
{
tail = cur->prev;
}
else if (head == cur)
{
head = cur->next;
}
// 3. 삭제
delete cur;
/*
검증해봐야할 것.
1. head, tail 노드만 존재할 때
2. head 노드만 존재할 떄
3. 3개 이상의 노드가 존재할 때
*/
--size;
}
데이터가 있는지 확인하고 없다면 종료
데이터가 있다면 해당 node의 연결 관계를 수정합니다.
데이터가 있는 노드의 prev node의 next는 현재 node의 next
데이터가 있는 노드의 next node의 prev는 현재 node의 prev
node가 한 개만 있는 경우 (head == cur && tail == cur)
- head nullptr
- tail nullptr
node가 tail node인 경우
tail 노드를 현재 노드의 prev Node로 지정
node가 head node인 경우
head 노드를 현재 노드의 next Node로 지정
현재 노드를 메모리 해제합니다. (delete) size를 감소합니다.
