자료구조 1강. 리스트(List)
[자료구조 강좌]
데이터의 목록을 다루는 자료구조
리스트(List)
리스트(List)는 데이터의 목록을 다루는 구조가 단순한 자료구조 입니다. 구조가 단순하면서도, 가장 널리 쓰이며 리스트는 다른 자료구조들을 이해하는데 필요한 기초를 제공합니다. 이 리스트란 자료구조는 데이터를 순차적으로 저장하며, 이 때문에 선형 구조를 띕니다. 여기서 선형 구조란 데이터가 순차적으로 저장되기 때문에 끊어지지 않으며, 한 줄로 계속되기 때문에 마치 선과 같은 형태를 띈다 하여 선형 구조라고 하는 것입니다.
1. 링크드 리스트(Linked List) 노드의 연결로 이루어져 있다!
가장 먼저 링크드 리스트(Linked List)란 녀석에 대해 설명을 하도록 하겠습니다. 이 링크드 리스트(Linked List)는 노드(Node)라는 요소로 구성되어 있습니다. 즉, 노드를 연결하여 만들어지는 리스트라고 보시면 되겠습니다. 이 노드는 데이터와 포인터를 가집니다. (여기서 데이터는 말 그대로 데이터 필드이고, 포인터는 다음 노드를 가리키는 포인터라고 말할 수 있습니다.) 아래와 같이 노드와 노드를 서로 엮어 링크드 리스트가 됩니다.
이 위에 있는 예를 보시면, 3개의 노드가 존재하고 각각의 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있음을 확인하실 수 있습니다. 이 리스트의 첫번째 노드를 헤드(Head, 머리)라고 하며, 맨 마지막 노드를 테일(Tail, 꼬리)이라고 합니다. 링크드 리스트에 대한 간단한 설명은 이 정도로 끝내고, 노드를 어떻게 생성하고 소멸하는지, 출력은 어떻게 하는지 알아보도록 하겠습니다.
먼저, 노드를 어떻게 표현해야 할 지 알아두도록 합시다. 위에서 말했듯, 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 그렇다면 아래와 같은 클래스로 나타낼 수 있습니다.
class Node
{
public:
string data; // 데이터 필드
Node* link; // 다음 노드를 가리키는 포인터
};이제 리스트의 기본적인 것에 대해서는 모두 알았으니, 본격적으로 리스트를 생성하고, 노드를 생성해봅시다. 연결 리스트에는 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트 이 세가지가 존재하지만 단순 연결 리스트(Singly Linked List: SLL)부터 보도록 하겠습니다. 단순 연결 리스트를 만드는 코드를 먼저 살펴보도록 합시다. 단순 연결 리스트에는 헤드만 필드에 두도록 하겠습니다.
class SLL
{
public:
Node* Head;
};그리고 노드를 추가하는 함수인 appendNode를 구현해보도록 합시다. appendNode 함수에는 노드를 추가하는 부분과 만약 처음 노드를 추가하는 것이라면, 이 노드를 헤드로 지정하고 처음 추가하는게 아니라면 마지막 노드의 link에 새로 추가되는 노드의 주소값을 넣도록 만들어봅시다.
..
void appendNode(string data)
{
Node* newNode = new Node(); // 새로운 노드를 생성한다.
newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
newNode->link = NULL; // 이 노드의 링크를 NULL로 초기화 시킨다.
Node* tempPoint = Head; // 임시 포인터를 두고 이 포인터에 Head의 주소 값으로 초기화 시킨다.
if (tempPoint != NULL) { // 노드를 처음 추가하는 것이 아니라면
while (tempPoint->link != NULL) // 테일 노드를 구하기 위해 임시 포인터의 link가 NULL일때까지 반복
tempPoint = tempPoint->link; // 임시 포인터가 가리키고 있는 다음 노드의 주소 값을 대입
tempPoint->link = newNode; // 마지막 노드가 새로 추가된 노드를 가리키게 한다
}
else { // 노드를 처음 추가하는 것이라면
Head = newNode; // 새로 추가한 노드를 헤드로 지정한다
}
}
..
위의 appendNode 함수는 SLL 클래스 선언 영역에다 집어 넣습니다. 그리고 SLL 클래스의 생성자에 Head를 NULL로 초기화 하는 부분을 만들어주세요. 코드 하나하나 주석을 달아 드렸습니다. 이해가 가지 않는 부분은 덧글로 달아주시면 추가 설명을 달아드리도록 하겠습니다. 이번엔 노드를 추가하는 함수를 만들었으니, 노드를 제거하는 함수를 만들어보도록 합시다.
이 노드를 제거하는 함수는 인자로 넘겨받은 data와 각 노드의 data와 비교하여 일치하면 그 노드를 삭제하는 방식입니다. 한번 보도록 합시다.
..
void deleteNode(string data)
{
Node* tempPoint = Head; // 임시 포인터가 헤드를 가리키게 만든다.
Node* prevNode; // 이전 노드를 가리키게 될 포인터를 선언한다.
// 빈 노드를 발견할 때까지 리스트를 순회한다.
while (tempPoint != NULL)
{
// data와 현재 노드의 데이터(tempPoint->data)가 일치한다면
if (data.compare(tempPoint->data) == 0)
{
// 만약, 삭제할 노드가 헤드 노드라면 새로운 헤드 노드는 기존의 헤드 노드의 다음 노드가 된다.
if (tempPoint == Head) Head = tempPoint->link;
// 헤드 노드가 아니라면, 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 연결한다.
else prevNode->link = tempPoint->link;
delete tempPoint; // 삭제된 노드를 메모리 공간에서 해제시킨다.
break;
}
// prevNode는 현재 tempPoint가 가리키는 노드를 가리키게 한다.
prevNode = tempPoint;
// tempPoint는 그 다음 노드를 가리키게 된다.
tempPoint = tempPoint->link;
}
}
..
이 노드를 삭제하는 함수인 deleteNode를 살펴보면, data를 우선 인자로 받고 넘겨받은 인자인 data를 통해 각 노드의 data와 비교하여 일치하면 그 노드를 리스트에서 제외시킵니다. 이번에는 리스트를 출력하는 함수를 만들어 보도록 합시다.
..
void printNode() {
Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입
// 노드가 하나도 존재하지 않으면 함수를 빠져나옴
if (tempPoint == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
// 노드가 하나만 존재할 경우
if (tempPoint->link == NULL) { cout << tempPoint->data << "->" << "NULL" << endl; }
// 노드가 하나가 아닌 하나 이상 존재할 경우
else {
while (tempPoint != NULL) // 임시 포인터가 NULL이 될때까지 반복
{
cout << tempPoint->data << "->"; // 임시 포인터의 데이터를 출력한다
tempPoint = tempPoint->link; // 임시 포인터의 link의 값을 대입한다
}
cout << "NULL" << endl; // 마지막에는 노드가 없음을 나타내기 위해 NULL 표시/개행
}
}
..
이렇게 노드를 생성하는 함수인 createNode, 노드를 제외시키는 함수인 deleteNode, 리스트의 각 노드의 데이터를 출력시키는 함수인 printNode 함수가 구현되었습니다. 이제 이 세 함수를 통해 노드를 만들고, 출력하고 삭제를 해보도록 합시다.
예>
#include <iostream>
#include <string>
using namespace std;
class Node
{
public:
string data; // 데이터 필드
Node* link; // 다음 노드를 가리키는 포인터
};
class SLL
{
public:
Node* Head; // 리스트의 머리 부분, 처음 부분
SLL()
{
Head = NULL; // 헤드(Head)의 초기화
}
void appendNode(string data)
{
Node* newNode = new Node(); // 새로운 노드를 생성한다.
newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
newNode->link = NULL; // 이 노드의 링크를 NULL로 초기화 시킨다.
Node* tempPoint = Head; // 임시 포인터를 두고 이 포인터에 Head의 주소 값으로 초기화 시킨다.
if (tempPoint != NULL) { // 노드를 처음 추가하는 것이 아니라면
while (tempPoint->link != NULL) // 테일 노드를 구하기 위해 임시 포인터의 link가 NULL일때까지 반복
tempPoint = tempPoint->link; // 임시 포인터가 가리키고 있는 다음 노드의 주소 값을 대입
tempPoint->link = newNode; // 마지막 노드가 새로 추가된 노드를 가리키게 한다
}
else { // 노드를 처음 추가하는 것이라면
Head = newNode; // 새로 추가한 노드를 헤드로 지정한다
}
}
void deleteNode(string data)
{
Node* tempPoint = Head; // 임시 포인터가 헤드를 가리키게 만든다.
Node* prevNode; // 이전 노드를 가리키게 될 포인터를 선언한다.
// 빈 노드를 발견할 때까지 리스트를 순회한다.
while (tempPoint != NULL)
{
// data와 현재 노드의 데이터(tempPoint->data)가 일치한다면
if (data.compare(tempPoint->data) == 0)
{
// 만약, 삭제할 노드가 헤드 노드라면 새로운 헤드 노드는 기존의 헤드 노드의 다음 노드가 된다.
if (tempPoint == Head) Head = tempPoint->link;
// 헤드 노드가 아니라면, 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 연결한다.
else prevNode->link = tempPoint->link;
delete tempPoint; // 삭제된 노드를 메모리 공간에서 해제시킨다.
break;
}
// prevNode는 현재 tempPoint가 가리키는 노드를 가리키게 한다.
prevNode = tempPoint;
// tempPoint는 그 다음 노드를 가리키게 된다.
tempPoint = tempPoint->link;
}
}
void printNode() {
Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입
// 노드가 하나도 존재하지 않으면 함수를 빠져나옴
if (tempPoint == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
// 노드가 하나만 존재할 경우
if (tempPoint->link == NULL) { cout << tempPoint->data << "->" << "NULL" << endl; }
// 노드가 하나가 아닌 하나 이상 존재할 경우
else {
while (tempPoint != NULL) // 임시 포인터가 NULL이 될때까지 반복
{
cout << tempPoint->data << "->"; // 임시 포인터의 데이터를 출력한다
tempPoint = tempPoint->link; // 임시 포인터의 link의 값을 대입한다
}
cout << "NULL" << endl; // 마지막에는 노드가 없음을 나타내기 위해 NULL 표시/개행
}
}
};
int main()
{
SLL List;
List.appendNode("빨강");
List.appendNode("주황");
List.appendNode("노랑");
List.printNode();
List.deleteNode("노랑");
List.deleteNode("주황");
List.deleteNode("빨강");
List.printNode();
return 0;
}
결과>
빨강->주황->노랑->NULL
리스트가 비어 있습니다.
계속하려면 아무 키나 누르십시오 . . .
메인 함수부터 살펴보면, 리스트를 생성하고 노드를 추가하고 출력한 뒤 제거하고 출력하는 순서를 보이고 있습니다. 단순 연결 리스트를 한번 자세하게 살펴보면, 단순 연결 리스트는 어떠한 위치에 있는 노드를 얻기 위해 드는 비용도 크고 속도도 느리다는 단점을 지니고 있습니다. 헤드부터 시작해서 테일까지 차례차례 노드를 탐색하기 때문입니다. 물론, 장점도 존재합니다. 새로운 노드를 추가하려면 추가와 삭제, 삽입이 간편합니다. 이 편에서는 삽입(Insert)에 대해선 언급하진 않았지만 삽입(Insert) 함수를 만든다면 이전 노드의 link를 새로운 노드를 가리키게 하고, 새로운 노드의 link는 그 다음 노드의 link를 가리키게 하면 되겠죠?
1-1 더블 링크드 리스트(Doubly Linked List) 양방향으로 탐색하자!
이번에는 단순 연결 리스트(Singly Linked List: SLL)가 아닌, 이중 연결 리스트(Doubly Linked List: DLL)입니다. 단순 연결 리스트는 헤드부터 시작해서 테일까지 탐색해야 하는 단방향 탐색이었지만, 이중 연결 리스트는 헤드에서 테일, 테일에서 헤드 방향으로 탐색이 가능한 양방향 탐색입니다. 단순 연결 리스트의 노드는 다음 노드를 가리키는 포인터만 있는 반면에, 이중 연결 리스트의 노드는 다음 노드를 가리키는 포인터뿐만 아니라 이전 노드를 가리키는 포인터가 존재합니다.
위의 그림에서 노드를 보시면 이전 노드를 가리키는 포인터(PrevLink)와, 데이터(Data), 그리고 다음 노드를 가리키는 포인터(NextLink)로 구성되어 있습니다. (이미 다 아시겠지만, 제일 앞에있는 노드가 헤드, 마지막에 있는 노드가 테일입니다.) 이중 연결 리스트를 구현하기 전에, 이중 연결 리스트의 노드는 어떻게 생성하는지 살펴봅시다.
class Node
{
public:
string data; // 데이터 필드
Node* NextLink; // 다음 노드를 가리키는 포인터
Node* PrevLink; // 이전 노드를 가리키는 포인터
};
Node 클래스의 멤버 변수가 하나 더 늘어났죠? 단순 연결 리스트와 비교하면 이전 노드를 가리키는 포인터가 새로 생겨났습니다. 곧바로 단순 연결 리스트에서 이중 연결 리스트로 넘어오면서 리스트 클래스가 어떻게 바뀌었는지, 추가와 소멸, 출력 함수는 어떻게 바뀌었는지 같이 살펴보도록 합시다.
class DLL
{
public:
Node* Head; // 리스트의 머리 부분, 처음 부분
Node* Tail; // 리스트의 꼬리 부분, 마지막 부분
};
단순 연결 리스트에선 헤드(Head)만 있던게, 이번에는 테일(Tail)이 추가되었습니다. 역시, DLL 클래스의 생성자에서 Head와 Tail를 NULL로 초기화 해주어야 합니다. 추가 함수를 살펴봅시다.
..
void appendNode(string data)
{
Node* newNode = new Node(); // 새로운 노드를 생성한다.
newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
newNode->NextLink = NULL; // 다음 노드를 이어주는 링크를 NULL로 초기화 시킨다.
newNode->PrevLink = NULL; // 이전 노드를 이어주는 링크를 NULL로 초기화 시킨다.
if (Head != NULL) { // 노드를 처음 추가하는 것이 아니라면
Tail->NextLink = newNode; // 꼬리 노드의 다음 노드를 새로 추가된 노드로 지정한다
newNode->PrevLink = Tail; // 새로 추가된 노드의 이전 노드를 꼬리 노드로 지정한다
Tail = newNode; // 꼬리 노드를 새로 추가된 노드로 지정한다
}
else { // 노드를 처음 추가하는 것이라면
Head = Tail = newNode; // 새로 추가한 노드를 헤드로 지정함과 동시에 테일로도 지정한다
}
}
..
이중 연결 리스트의 appendNode 함수입니다. 단순 연결 리스트와는 달리 이전 노드를 가리키는 포인터도 NULL로 초기화 합니다. 11행을 보시면, 꼬리 노드의 다음에 오는 노드를 추가되는 노드로 지정합니다. 그러고 나서 12행에선, 새로 추가된 노드의 이전에 오는 노드를 현재 꼬리 노드로 지정합니다. 그리고 13행에선, 새로 추가된 노드가 이제부턴 제일 마지막에 위치하는 노드이므로 꼬리 노드를 새로 추가된 노드로 지정합니다. 이번엔 삭제 노드를 살펴보는데, 이전 링크와 다음 링크를 함께 다루다보니 단순 연결 리스트에 비해 삭제 과정이 복잡해졌습니다.
단순 연결 리스트의 삭제 함수는 두개의 포인터를 다루는 반면에, 이중 연결 리스트의 삭제 함수는 네개의 포인터를 다룹니다. 삭제가 어떻게 이루어지는지 함수를 살펴보도록 합시다.
..
void deleteNode(string data)
{
Node* pNode = Head; // 임시 포인터에 헤드의 주소 값으로 초기화 한다
if (pNode == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
else { // 노드가 하나 이상 존재한다면
Node* prevNode; // 이전 노드를 담을 Node 클래스 포인터
Node* nextNode; // 다음 노드를 담을 Node 클래스 포인터
do {
// data와 pNode->data와 비교하여 일치하면 반복문을 빠져 나온다
if (data.compare(pNode->data) == 0) break;
pNode = pNode->NextLink; // 임시 노드에 다음 노드의 주소값을 대입한다.
} while (pNode != NULL); // 임시 포인터의 주소값이 NULL이 될때까지 반복
prevNode = pNode->PrevLink; // 삭제하려는 노드의 이전 노드를 가리킨다
nextNode = pNode->NextLink; // 삭제하려는 노드의 다음 노드를 가리킨다
// 삭제하려는 노드의 이전 노드가 없으면 헤드(Head) 노드이므로 삭제하려는 노드의 다음 노드를 헤드 노드로 지정
if (prevNode == NULL) Head = nextNode;
// 위의 경우가 아니라면 삭제하려는 노드의 이전 노드가 삭제하려는 노드의 다음 노드를 가리키게 한다
else prevNode->NextLink = nextNode;
// 삭제하려는 노드의 다음 노드가 없으면 테일(Tail) 노드이므로 삭제하려는 노드의 이전 노드를 테일 노드로 지정
if (nextNode == NULL) Tail = prevNode;
// 위의 경우가 아니라면 삭제하려는 노드의 다음 노드가 삭제하려는 노드의 이전 노드를 가리키게 한다
else nextNode->PrevLink = prevNode;
delete pNode; // pNode를 메모리 공간에서 해제시킨다
}
}
..
추가된 부분인 17행부터 설명을 진행하도록 하겠습니다. 17, 18행에선 삭제하려는 노드의 이전 노드와 다음 노드를 먼저 구합니다. 그리고 나서 21행에서, 삭제하려는 노드의 이전에 위치하는 노드가 NULL, 즉 비어있을 경우에 이 노드는 헤드(Head, 머리) 노드 이므로 기존의 헤드 노드가 삭제되면 헤드가 비어있기 때문에 삭제하려는 노드의 다음 노드를 가리키게 합니다. 만약 이전 노드가 존재한다면, 이전 노드가 가리키는 다음 노드를 삭제하려는 노드의 다음 노드를 가리키게 합니다. 밑의 테일 노드도 같습니다. 이번에는 출력 함수를 살펴보도록 합시다.
..
void printNode() {
Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입
// 노드가 하나도 존재하지 않으면 함수를 빠져나옴
if (tempPoint == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
// 노드가 하나만 존재할 경우
if (tempPoint->NextLink == NULL) { cout << tempPoint->data << "->" << "NULL" << endl; }
// 노드가 하나가 아닌 하나 이상 존재할 경우
else {
while (tempPoint != NULL) // 임시 포인터가 NULL이 될때까지 반복
{
cout << tempPoint->data << "<->"; // 임시 포인터의 데이터를 출력한다
tempPoint = tempPoint->NextLink; // 임시 포인터의 NextlINK의 값을 대입한다
}
cout << "NULL" << endl; // 마지막에는 노드가 없음을 나타내기 위해 NULL 표시/개행
}
}
..
출력 함수는 살펴보니 바뀐게 없는것 같죠? 네, 없습니다. 헤드에서부터 테일 방향으로 순서대로 출력하는 함수죠. 아래는 이중 연결 리스트 예제의 전체 소스입니다.
예>
#include <iostream>
#include <string>
using namespace std;
class Node
{
public:
string data; // 데이터 필드
Node* NextLink; // 다음 노드를 가리키는 포인터
Node* PrevLink; // 이전 노드를 가리키는 포인터
};
class DLL
{
public:
Node* Head; // 리스트의 머리 부분, 처음 부분
Node* Tail; // 리스트의 꼬리 부분, 마지막 부분
DLL()
{
Head = NULL; // 헤드(Head)의 초기화
Tail = NULL; // 테일(Tail)의 초기화
}
void appendNode(string data)
{
Node* newNode = new Node(); // 새로운 노드를 생성한다.
newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
newNode->NextLink = NULL; // 다음 노드를 이어주는 링크를 NULL로 초기화 시킨다.
newNode->PrevLink = NULL; // 이전 노드를 이어주는 링크를 NULL로 초기화 시킨다.
if (Head != NULL) { // 노드를 처음 추가하는 것이 아니라면
Tail->NextLink = newNode; // 꼬리 노드의 다음 노드를 새로 추가된 노드로 지정한다
newNode->PrevLink = Tail; // 새로 추가된 노드의 이전 노드를 꼬리 노드로 지정한다
Tail = newNode; // 꼬리 노드를 새로 추가된 노드로 지정한다
}
else { // 노드를 처음 추가하는 것이라면
Head = Tail = newNode; // 새로 추가한 노드를 헤드로 지정한다
}
}
void deleteNode(string data)
{
Node* pNode = Head; // 임시 포인터에 헤드의 주소 값으로 초기화 한다
if (pNode == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
else { // 노드가 하나만 존재하는 것이 아니라면
Node* prevNode; // 이전 노드를 담을 Node 클래스 포인터
Node* nextNode; // 다음 노드를 담을 Node 클래스 포인터
do {
// data와 pNode->data와 비교하여 일치하면 반복문을 빠져 나온다
if (data.compare(pNode->data) == 0) break;
pNode = pNode->NextLink; // 임시 노드에 다음 노드의 주소값을 대입한다.
} while (pNode != NULL); // 임시 포인터의 주소값이 NULL이 될때까지 반복
prevNode = pNode->PrevLink; // 삭제하려는 노드의 이전 노드를 가리킨다
nextNode = pNode->NextLink; // 삭제하려는 노드의 다음 노드를 가리킨다
// 삭제하려는 노드의 이전 노드가 없으면 헤드(Head) 노드이므로 삭제하려는 노드의 다음 노드를 헤드 노드로 지정
if (prevNode == NULL) Head = nextNode;
// 위의 경우가 아니라면 삭제하려는 노드의 이전 노드가 삭제하려는 노드의 다음 노드를 가리키게 한다
else prevNode->NextLink = nextNode;
// 삭제하려는 노드의 다음 노드가 없으면 테일(Tail) 노드이므로 삭제하려는 노드의 이전 노드를 테일 노드로 지정
if (nextNode == NULL) Tail = prevNode;
// 위의 경우가 아니라면 삭제하려는 노드의 다음 노드가 삭제하려는 노드의 이전 노드를 가리키게 한다
else nextNode->PrevLink = prevNode;
delete pNode; // pNode를 메모리 공간에서 해제시킨다
}
}
void printNode() {
Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입
// 노드가 하나도 존재하지 않으면 함수를 빠져나옴
if (tempPoint == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
// 노드가 하나만 존재할 경우
if (tempPoint->NextLink == NULL) { cout << tempPoint->data << "->" << "NULL" << endl; }
// 노드가 하나가 아닌 하나 이상 존재할 경우
else {
while (tempPoint != NULL) // 임시 포인터가 NULL이 될때까지 반복
{
cout << tempPoint->data << "<->"; // 임시 포인터의 데이터를 출력한다
tempPoint = tempPoint->NextLink; // 임시 포인터의 NextlINK의 값을 대입한다
}
cout << "NULL" << endl; // 마지막에는 노드가 없음을 나타내기 위해 NULL 표시/개행
}
}
};
int main()
{
DLL List;
List.appendNode("빨강");
List.appendNode("주황");
List.appendNode("노랑");
List.printNode();
List.deleteNode("노랑");
List.deleteNode("주황");
List.deleteNode("빨강");
List.printNode();
return 0;
}
결과:
빨강<->주황<->노랑<->NULL
리스트가 비어 있습니다.
계속하려면 아무 키나 누르십시오 . . .
위의 예제에서의 메인 함수는 SLL이 DLL로 바뀐 것 말고는 다른게 없습니다. 단순 연결 리스트만 완벽히 이해하고 계시면, 이중 연결 리스트를 구현하는 것도 크게 어렵지 않게 구현하실 수 있습니다. 이 예제의 함수에는 추가, 삭제, 출력같은 기본적인 함수밖에 존재하지 않지만, 좌측 삽입, 우측 삽입, 노드의 수를 구하는 함수도 한번 만들어보세요.
1-2 환형 링크드 리스트(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] <->주황[007BBE50-007BBED8] <->노랑[007BBED8-007B9E90]
빨강[007B9E90-007B9E90]
리스트가 비어 있습니다.
계속하려면 아무 키나 누르십시오 . . .
어떤 노드가 또다른 노드를 가리키는지 쉽게 알도록 노드의 데이터 옆에 노드의 주소값과, 다음 노드의 주소값을 함께 출력하였습니다. 결과의 2번째 줄을 보시면 노랑, 주황이란 데이터를 가진 노드가 삭제되고 빨강이란 데이터를 가진 노드가 혼자 남았는데, 이 노드의 주소 값과 다음을 가리키는 노드의 주소값이 같습니다. 더블 링크드 리스트에선 노드가 혼자 남았을 경우에는 그 노드가 가리키는 다음 노드는 존재하지 않았죠. 이런 원형 이중 연결 리스트는 테일 노드에 쉽게 접근할 수 있고, 추가 함수를 좀더 개선시킬 수 있게되는 등 여러가지 장점을 지니고 있습니다.
여기까지 리스트란 자료구조에 대해 알아보았습니다. 읽느라 수고하셨고, 다음 편에는 스택(Stack)이란 자료구조에 대해 다루도록 하겠습니다.
'알고리즘, 자료구조' 카테고리의 다른 글
| 자료구조 4강. 트리(Tree) (4) | 2013.01.23 |
|---|---|
| 자료구조 3강. 큐(Queue) (4) | 2013.01.15 |
| 자료구조 2강. 스택(Stack) (8) | 2013.01.09 |
| 비주얼베이직6 움직임에 관한 수학공식 정리 (4) | 2012.10.03 |
| 알고리즘 1-1강. 정렬 (16) | 2012.05.27 |