링크드 리스트(Linked List)

데이터의 목록을 다루는 자료구조

리스트(List)

리스트(List)는 데이터의 목록을 다루는 구조가 단순한 자료구조입니다. 구조가 단순하면서도, 가장 널리 쓰이며 리스트는 다른 자료구조들을 이해하는데 필요한 기초를 제공합니다. 이 리스트란 자료구조는 데이터를 순차적으로 저장하며, 이 때문에 선형 구조를 띕니다. 여기서 선형 구조란 데이터가 순차적으로 저장되기 때문에 끊어지지 않으며, 한 줄로 계속되기 때문에 마치 선과 같은 형태를 띤다 하여 선형 구조라고 하는 것입니다.

링크드 리스트(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; // 임시 포인터에 헤드의 주소 값으로 초기화 한다

    if (tempPoint == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
    if (tempPoint->link == NULL) { // 노드가 하나만 존재한다면 그 노드만 삭제한다
        delete tempPoint; // tempPoint를 메모리 공간에서 해제시킨다
        Head = NULL; // Head를 아무 것도 가리키지 않게 한다
    }
    else 
    { // 노드가 하나만 존재하는 것이 아니라면
        Node *prevNode; // 이전 노드를 담을 Node 클래스
        do {
            // data와 tempPoint->data와 비교하여 일치하면 반복문을 빠져 나온다
            
            if (data.compare(tempPoint->data) == 0) break;
            prevNode = tempPoint; // 이전 노드에다 임시 포인터의 주소값을 대입한다
            tempPoint = tempPoint->link; // 임시 노드에 다음 노드의 주소값을 대입한다.
        } while (tempPoint != NULL); // 임시 포인터의 주소값이 NULL이 될때까지 반복 

        prevNode->link = tempPoint->link; // 이전 노드의 link에 임시 포인터의 link를 대입한다.
        // 즉, 이전 노드가 삭제되는 노드의 다음을 가리키게 한다.
        delete tempPoint; // tempPoint를 메모리 공간에서 해제시킨다
    }
}

이 노드를 삭제하는 함수인 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; // 임시 포인터에 헤드의 주소 값으로 초기화 한다
        if (tempPoint == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
        if (tempPoint->link == NULL) { // 노드가 하나만 존재한다면 그 노드만 삭제한다
            delete tempPoint; // tempPoint를 메모리 공간에서 해제시킨다
            Head = NULL; // Head를 아무 것도 가리키지 않게 한다
        }
        else { // 노드가 하나만 존재하는 것이 아니라면
            Node *prevNode; // 이전 노드를 담을 Node 클래스
            do {
                // data와 tempPoint->data와 비교하여 일치하면 반복문을 빠져 나온다
                if (data.compare(tempPoint->data) == 0) break;
                prevNode = tempPoint; // 이전 노드에다 임시 포인터의 주소값을 대입한다
                tempPoint = tempPoint->link; // 임시 노드에 다음 노드의 주소값을 대입한다.
            } while (tempPoint != NULL); // 임시 포인터의 주소값이 NULL이 될때까지 반복 
            prevNode->link = tempPoint->link; // 이전 노드의 link에 임시 포인터의 link를 대입한다.
            // 즉, 이전 노드가 삭제되는 노드의 다음을 가리키게 한다.
            delete tempPoint; // tempPoint를 메모리 공간에서 해제시킨다
        }
    }

    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를 가리키게 하면 되겠죠?