단순연결 리스트와 이어집니다.
저번 단순연결리스트를 다루었을때 단순연결리스트는 앞의 노드에서 다음노드로가는것은 가능했지만 한번조회한 노드는 그다음노드로 이동후에는 다시 조회하기가 힘들다는 단점이있었다. 이번에 다루어볼 원형연결리스트는 노드의 링크를 따라 계속 순회하면 다시 이전노드에 접근이 가능한 연결리스트이다.
원형 연결 리스트
원형연결리스트는 단순 연결리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결리스트이다.
간단하게 생각하여 단순 연결리스트에서 마지막노드가 첫번째 노드를 가르키게 만들어주기만 하면된다 .
코드로 구현
#include <iostream>
using namespace std;
template <typename T>
class CircleLinkedList
{
private:
struct Node
{
T data;
Node* next;
};
int size;
Node* head;
public:
CircleLinkedList()
{
size = 0;
head = nullptr;
}
void PushFront(T data) //앞쪽으로 삽입
{
Node* newNode = new Node;
newNode->data = data;
if (head == nullptr)
{
head = newNode; //head = newNode --> Front에서 이값은 더이상 안바뀜(얘가 맨뒤이기때문)
newNode->next = head; //노드는 하나 밖에 없으니 본인 가르키기 ㅣ
head->next = newNode;
}
else
{
newNode->next = head->next; //삽입할 노드의 next = 현재 마지막 노드가 가르키고 있는 노드
head->next = newNode; // 마지막노드가 가르킬 노드 -> 삽입한 노드
}
size++;
}
void PushBack(T data)
{
Node* newNode = new Node;
newNode->data = data;
if (head == nullptr)
{
head = newNode;
newNode->next = head;
head->next = newNode;
}
else
{
newNode->next = head->next;
head->next = newNode;
head = newNode;
}
size++;
}
void PopFront()
{
Node* deleteNode;
if (size == 0)
{
cout << "List is Empty" << '\n';
}
else if (size == 1)//노드 하나 남은경우
{
deleteNode = head;
delete deleteNode;
head = nullptr;
}
else
{
deleteNode = head->next; //deleteNode = 맨앞의 노드
head->next = deleteNode->next; //head ->next = 맨앞의 노드 의 다음노드
delete deleteNode; //맨앞 노드 삭제
}
size--;
}
void PopBack()
{
Node* deleteNode;
Node* currentNode; //노드를 이어주기 위해 사용
if (size == 0)
{
cout << "List is Empty" << '\n';
}
else if (size == 1)
{
deleteNode = head;
delete deleteNode;
head = nullptr;
}
else
{
currentNode = head;
deleteNode = head;
while (size - 1)
{
currentNode = currentNode->next; //맨뒤의 노드 바로 전의 노드까지
}
currentNode->next = head->next; //맨뒤의 노드의 앞노드 의 다음노드= 첫번째 노드
head = currentNode; // 맨뒤 = currentNode;
delete deleteNode; //삭제해야할 노드 삭제
}
size--;
}
void Print()
{
Node* currentNode;
currentNode = head;
int num = size + 4; //원형이 잘구성되어있는지 확인하기위함
cout << '\n' << "List : ";
while (num)
{
if (num > 1)
{
cout << currentNode->data << "->";
currentNode = currentNode->next;
}
if (num == 1)
{
cout << currentNode->data;
currentNode = currentNode->next;
}
num--;
}
cout << '\n';
}
~CircleLinkedList()
{
while (size != 0) // size는 pop 에서 알아서 지워짐
{
PopFront();
}
cout << "Release Node" << '\n';
}
int Size()
{
return size;
}
};
int main()
{
CircleLinkedList<int> circleLinkedList;
circleLinkedList.PushFront(10);
circleLinkedList.PushFront(20);
circleLinkedList.PushFront(30);
circleLinkedList.PushBack(40);
circleLinkedList.PushBack(50);
circleLinkedList.PushBack(60);
cout << endl << "CircleLinkedList의 크기 : " << circleLinkedList.Size() << endl;
circleLinkedList.Print();
return 0;
}그림 설명
PushFront
먼저 내가 10이라는 값을 넣어줄것이다. head 는 데이터 값이 10인 노드를 가르킨다. 노드는 현재 하나 뿐이니 데이터값이 10인 newNode 의 다음노드는 본인을 가르키게 된다. head->next 또한 newNode 를넣어주도록 한다 .
그다음 20이라는 값을 넣어주게되면 20 노드는 10 노드를 가르켜주고 10 노드의 다음노드를 20노드를 가르키게 만들어준다. 그다음 head는 10노드를 가르키게 그대로 유지를하고 head->next는 20 노드를 가르키게 만들어준다.
PushBack
이번에 PushBack을해보자
30이라는 값을 PushBack을 해주면 30노드가 맨 마지막 노드가 된다.
1. 30노드의 next는 노드는 20노드를가르키된다.
2.삽입전의 맨뒤였던 10노드의 next 는 30노드를 가르키게된다 .
3.head 는 30노드를 가르키게된다.
이렇게 되면 원형연결리스트가 유지가 된다 .
PopFront
20노드를 Pop해주기 위해서
1. head ->next는 20노드를 가르키니 deleteNode =head ->next를 해준다.
2. head->next는 20노드의 다음노드인 10노드를 가르키게 만들어준다.
3. 이후 20노드를 delete를 해준다.
PopBack
PopBack은 currentNode 와 deleteNode 2개가 필요하도록 만들었다.
currentNode 는 마지막노드의 삭제이후를 위한 노드이다.
1.while(size-1)은 마지막노드의 바로 이전 노드까지 가기 위함이다.
currentNode는 while 문을 통해 마지막노드 바로 이전노드를 가르키게 된다.
2.currentNode 의 다음노드는 맨앞의 노드를 가르키게 만들어준다.
3.head 를 currentNode 를 가르키게 만들어준다.
4.deleteNode가 가르키고 있는 노드(삭제시킬 노드) 를 삭제시켜준다.
이상으로...
머릿속으로는 원형연결리스트를 구현하는 방법이 생각이나지만 이를 말로표현하기는 나에게는 어려운과정인것같다. 이번 원형연결리스트를 구상하는데 PopBack역시 만들어보았는데 삭제시킬 노드를 삭제시키는 과정은 간단하지만
그 이전노드를 찾아서 연결시켜주는 과정은 반복문을 통해 들어가다보니 은근 비효율적이라고 느껴진다. 아마 다른 방식이 있을 수도 있을거지만 내가 만든 방식에서는 그렇게 느껴지긴한다.(공부하면서 필기한다는 느낌으로 글을 작성하고있는거라 틀린것도 많을것이다.)
그다음은 이중연결리스트를 만들어보도록하겠다.
