목차
환형 링크드 리스트(Circular Linked List)
머리가 꼬리를 문다!
여태까지 단순 연결 리스트, 이중 연결 리스트에 대해 알아봤습니다. 이번에는 원형 연결 리스트(Circular Linked List)에 대해 알아보도록 하겠습니다. 원형 연결 리스트의 특징은 머리와 꼬리가 연결되어 순환(Circular) 구조를 지닙니다. 즉, 꼬리(Tail, 테일) 노드의 다음 노드는 머리(Head, 헤드) 노드를 가리킵니다. 여기서는 환형 더블 링크드 리스트가 아닌 환형 싱글 링크드 리스트 기준으로 다루도록 하겠습니다. 환형 싱글 링크드 리스트는 싱글 링크드 리스트에서 헤드와 테일을 연결한 것입니다.
위의 그림을 보면 알 수 있듯이, 원형 단순 연결 리스트는 단순 연결 리스트에서 머리와 꼬리를 연결했다는 것을 알 수 있습니다. 여기에서는 꼬리란 개념이 사라집니다. 원형 단순 연결 리스트에서의 노드는 단순 연결 리스트의 노드의 구조와 똑같습니다. 데이터와 다음 노드를 가리키는 포인터를 담고 있습니다.
class Node
{
public:
string data; // 데이터 필드
Node* link; // 다음 노드를 가리키는 포인터
};
이제, 원형 단순 연결 리스트를 직접 구현해보도록 합시다. 원형 단순 연결 리스트는 마지막 노드의 앞 노드는 헤드 노드라는 것을 염두해두시고 구현하셔야 합니다.
void appendNode(string data)
{
Node* newNode = new Node(); // 새로운 노드를 생성한다.
newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
newNode->NextLink = NULL; // 다음 노드를 이어주는 링크를 NULL로 초기화 시킨다.
newNode->PrevLink = NULL; // 이전 노드를 이어주는 링크를 NULL로 초기화 시킨다.
if (Head != NULL) { // 노드를 처음 추가하는 것이 아니라면
Node* Tail = Head->PrevLink; // Tail이 헤드의 이전 노드를 가리키게 한다
Tail->NextLink->PrevLink = newNode; // 꼬리 노드의 다음 노드, 즉 헤드 노드의 이전 노드는 새로운 노드
Tail->NextLink = newNode; // 꼬리 노드의 다음을 가리키는 노드를 새로 추가되는 노드로 지정
newNode->NextLink = Head; // 새로 추가되는 노드의 다음 노드는 헤드를 가리키도록 지정
newNode->PrevLink = Tail; // 새로 추가되는 노드의 이전 노드는 현재 꼬리 노드로 지정
}
else { // 노드를 처음 추가하는 것이라면
Head = newNode; // 새로 추가되는 노드를 헤드로 지정한다
Head->NextLink = Head; // 헤드의 다음 노드를 헤드로 지정한다. 자신이 첫 노드이자 마지막 노드.
Head->PrevLink = Head; // 헤드의 이전 노드를 헤드로 지정한다. 자신이 첫 노드이자 마지막 노드.
}
}
13행부터 보자면, 헤드 노드의 이전 노드를 새로 추가되는 노드로 지정하고 14행에서 꼬리 노드의 다음 노드를 새로운 노드로 지정합니다. 그런 뒤에 15행에서 새로 추가되는 노드의 다음 노드를 헤드 노드로 지정하게 하고, 이전 노드를 전의 꼬리 노드로 지정하게 함으로써 머리와 꼬리를 연결합니다. 이어서 삭제 함수를 보도록 합시다.
void deleteNode(string data)
{
Node* pNode = Head; // 임시 포인터에 헤드의 주소 값으로 초기화 한다
if (pNode == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
else { // 노드가 하나만 존재하는 것이 아니라면
do {
// data와 pNode->data와 비교하여 일치하면 반복문을 빠져 나온다
if (data.compare(pNode->data) == 0) break;
pNode = pNode->NextLink; // 임시 노드에 다음 노드의 주소값을 대입한다.
} while (pNode != Head); // 임시 포인터의 주소 값이 헤드의 주소 값이 될때까지 반복
if (pNode == Head) { // 삭제하려는 노드가 헤드 노드이면
Head->PrevLink->NextLink = pNode->NextLink; // 꼬리 노드가 가리키는 다음 노드를 삭제하려는 노드의 다음 노드로 지정
Head->NextLink->PrevLink = pNode->PrevLink; // 헤드 노드 다음에 위치하는 노드의 이전 노드를 삭제하려는 노드의 이전 노드로 지정
Head = pNode->NextLink; // 삭제하려는 노드의 다음 노드를 헤드 노드로 지정
pNode->PrevLink = NULL; // pNode의 PrevLink를 NULL로 지정
pNode->NextLink = NULL; // pNode의 NextLink를 NULL로 지정
}
else {
Node* Temp = pNode; // 임시 노드를 만들고 임시 노드에 삭제하려는 노드 지정
pNode->PrevLink->NextLink = Temp->NextLink; // 삭제하려는 노드의 이전 노드의 다음 노드를 삭제하려는 노드의 다음 노드로 지정
pNode->NextLink->PrevLink = Temp->PrevLink; // 삭제하려는 노드의 다음 노드의 이전 노드를 삭제하려는 노드의 이전 노드로 지정
pNode->PrevLink = NULL; // pNode의 PrevLink를 NULL로 지정
pNode->NextLink = NULL; // pNode의 NextLink를 NULL로 지정
}
}
}
짚고 넘어가야 할 부분만 살짝살짝 보도록 합시다. 먼저 12행을 보시면, 환형 연결 리스트에는 다음을 가리키는 노드가 NULL 일 수가 없습니다. 그렇기 때문에, 헤드 노드를 끝으로 조건식을 작성합니다. 그런데, 삭제하려는 노드가 만약 헤드 노드일 경우에는 제거되는 헤드 노드의 다음 노드를 새로운 헤드 노드로 지정하고, 꼬리 노드의 다음 노드는 새로운 헤드 노드를 가리키게 하여야 합니다. (15~18) 반대로, 삭제하려는 노드가 헤드 노드가 아닐 경우에는 그냥 삭제하려는 노드의 전 노드와 앞의 노드를 이어주면 되겠죠. (26~27) 이번에는 출력 함수를 보도록 합시다.
void printNode() {
Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입
// 노드가 하나도 존재하지 않으면 함수를 빠져나옴
if (tempPoint->NextLink == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
// 노드가 하나만 존재할 경우
if (tempPoint->NextLink == Head) { cout << tempPoint->data << "[" << tempPoint << "-" << tempPoint->NextLink << "]" << endl; }
// 노드가 하나가 아닌 하나 이상 존재할 경우
else {
while (tempPoint->NextLink != Head) // 임시 노드의 다음 노드가 헤드 노드가 될때까지 반복
{
cout << tempPoint->data << "[" << tempPoint << "-" << tempPoint->NextLink << "] <->"; // 임시 노드의 주소 값과 다음 노드의 주소 값 그리고 데이터를 출력
tempPoint = tempPoint->NextLink; // 임시 노드의 다음 노드를 가리키게 함
}
cout << tempPoint->data << "[" << tempPoint << "-" << tempPoint->NextLink << "] " << endl; // 꼬리 노드의 주소 값과 다음 노드의 주소 값 그리고 데이터를 출력
}
}
출력 함수도 바뀐 부분만 살짝살짝 살펴보도록 합시다. 먼저 8행을 보시면, 이번에도 NULL이 아닌 Head가 등장했습니다. 헤드 노드가 가리키는 다음 노드도 헤드 노드라면 결국엔 노드가 리스트에 한 개뿐이라는 소리가 됩니다. 11행도 마찬가지로, 임시 노드의 다음 노드가 헤드 노드일 때까지 반복하게 되고 이는 즉, 헤드부터 시작해서 다음 헤드 노드가 등장할 때까지 반복한다는 말입니다. 환형 이중 연결 리스트의 전체 코드를 보도록 합시다.
예제보기
#include <iostream>
#include <string>
using namespace std;
class Node
{
public:
string data; // 데이터 필드
Node* NextLink; // 다음 노드를 가리키는 포인터
Node* PrevLink; // 이전 노드를 가리키는 포인터
};
class CDLL
{
public:
Node* Head; // 리스트의 머리 부분, 처음 부분
CDLL()
{
Head = NULL; // 헤드(Head)의 초기화
}
void appendNode(string data)
{
Node* newNode = new Node(); // 새로운 노드를 생성한다.
newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
newNode->NextLink = NULL; // 다음 노드를 이어주는 링크를 NULL로 초기화 시킨다.
newNode->PrevLink = NULL; // 이전 노드를 이어주는 링크를 NULL로 초기화 시킨다.
if (Head != NULL) { // 노드를 처음 추가하는 것이 아니라면
Node* Tail = Head->PrevLink; // Tail이 헤드의 이전 노드를 가리키게 한다
Tail->NextLink->PrevLink = newNode; // 꼬리 노드의 다음 노드, 즉 헤드 노드의 이전 노드는 새로운 노드
Tail->NextLink = newNode; // 꼬리 노드의 다음을 가리키는 노드를 새로 추가되는 노드로 지정
newNode->NextLink = Head; // 새로 추가되는 노드의 다음 노드는 헤드를 가리키도록 지정
newNode->PrevLink = Tail; // 새로 추가되는 노드의 이전 노드는 현재 꼬리 노드로 지정
}
else { // 노드를 처음 추가하는 것이라면
Head = newNode; // 새로 추가되는 노드를 헤드로 지정한다
Head->NextLink = Head; // 헤드의 다음 노드를 헤드로 지정한다. 자신이 첫 노드이자 마지막 노드.
Head->PrevLink = Head; // 헤드의 이전 노드를 헤드로 지정한다. 자신이 첫 노드이자 마지막 노드.
}
}
void deleteNode(string data)
{
Node* pNode = Head; // 임시 포인터에 헤드의 주소 값으로 초기화 한다
if (pNode == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
else { // 노드가 하나만 존재하는 것이 아니라면
do {
// data와 pNode->data와 비교하여 일치하면 반복문을 빠져 나온다
if (data.compare(pNode->data) == 0) break;
pNode = pNode->NextLink; // 임시 노드에 다음 노드의 주소값을 대입한다.
} while (pNode != Head); // 임시 포인터의 주소 값이 헤드의 주소 값이 될때까지 반복
if (pNode == Head) { // 삭제하려는 노드가 헤드 노드이면
Head->PrevLink->NextLink = pNode->NextLink; // 꼬리 노드가 가리키는 다음 노드를 삭제하려는 노드의 다음 노드로 지정
Head->NextLink->PrevLink = pNode->PrevLink; // 헤드 노드 다음에 위치하는 노드의 이전 노드를 삭제하려는 노드의 이전 노드로 지정
Head = pNode->NextLink; // 삭제하려는 노드의 다음 노드를 헤드 노드로 지정
pNode->PrevLink = NULL; // pNode의 PrevLink를 NULL로 지정
pNode->NextLink = NULL; // pNode의 NextLink를 NULL로 지정
}
else {
Node* Temp = pNode; // 임시 노드를 만들고 임시 노드에 삭제하려는 노드 지정
pNode->PrevLink->NextLink = Temp->NextLink; // 삭제하려는 노드의 이전 노드의 다음 노드를 삭제하려는 노드의 다음 노드로 지정
pNode->NextLink->PrevLink = Temp->PrevLink; // 삭제하려는 노드의 다음 노드의 이전 노드를 삭제하려는 노드의 이전 노드로 지정
pNode->PrevLink = NULL; // pNode의 PrevLink를 NULL로 지정
pNode->NextLink = NULL; // pNode의 NextLink를 NULL로 지정
}
}
}
void printNode() {
Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입
// 노드가 하나도 존재하지 않으면 함수를 빠져나옴
if (tempPoint->NextLink == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
// 노드가 하나만 존재할 경우
if (tempPoint->NextLink == Head) { cout << tempPoint->data << "[" << tempPoint << "-" << tempPoint->NextLink << "]" << endl; }
// 노드가 하나가 아닌 하나 이상 존재할 경우
else {
while (tempPoint->NextLink != Head) // 임시 노드의 다음 노드가 헤드 노드가 될때까지 반복
{
cout << tempPoint->data << "[" << tempPoint << "-" << tempPoint->NextLink << "] <->"; // 임시 노드의 주소 값과 다음 노드의 주소 값 그리고 데이터를 출력
tempPoint = tempPoint->NextLink; // 임시 노드의 다음 노드를 가리키게 함
}
cout << tempPoint->data << "[" << tempPoint << "-" << tempPoint->NextLink << "] " << endl; // 꼬리 노드의 주소 값과 다음 노드의 주소 값 그리고 데이터를 출력
}
}
};
int main()
{
CDLL List;
List.appendNode("빨강");
List.appendNode("주황");
List.appendNode("노랑");
List.printNode();
List.deleteNode("노랑");
List.deleteNode("주황");
List.printNode();
List.deleteNode("빨강");
List.printNode();
return 0;
}
결과보기
빨강[007B9E90-007BBE50] <->주황[007 BBE50-007 BBED8] <->노랑[007 BBED8-007 B9 E90] 빨강[007B9E90-007 B9 E90] 리스트가 비어 있습니다. 계속하려면 아무 키나 누르십시오...
어떤 노드가 또 다른 노드를 가리키는지 쉽게 알도록 노드의 데이터 옆에 노드의 주소 값과, 다음 노드의 주소 값을 함께 출력하였습니다. 결과의 2번째 줄을 보시면 노랑, 주황이란 데이터를 가진 노드가 삭제되고 빨강이란 데이터를 가진 노드가 혼자 남았는데, 이 노드의 주소 값과 다음을 가리키는 노드의 주소 값이 같습니다. 더블 링크드 리스트에선 노드가 혼자 남았을 경우에는 그 노드가 가리키는 다음 노드는 존재하지 않았죠. 이런 원형 이중 연결 리스트는 테일 노드에 쉽게 접근할 수 있고, 추가 함수를 좀 더 개선시킬 수 있게 되는 등 여러 가지 장점을 지니고 있습니다.
여기까지 리스트란 자료구조에 대해 알아보았습니다. 읽느라 수고하셨고, 다음 편에는 스택(Stack)이란 자료구조에 대해 다루도록 하겠습니다.