단일연결리스트(Singly Linked Lists) - C++

개요

여러 언어에서 기본적으로 제공하는 자료구조인 배열은 특정 순서로 무언가 저장하기에 좋고 간단하지만 단점이 있습니다. 배열은 유연하지 않습니다. 예를 들어, 배열의 크기를 미리 지정해야 하며, 프로그램의 동작 중에 그것을 수정하는 것은 매우 어렵습니다. (이 단점은 C++의 표준 템플릿 라이브러리(STL, Standard Template Library)인 벡터(Vector)에서 해결됩니다.) 또한 요소의 삽입 및 삭제가 어렵습니다. 삽입을 위한 공간을 확보하거나 삭제 후 빈 공간을 채우기 위해 나머지 요소를 좌/우로 이동해야 합니다.

이번 포스트에서는 연결리스트(Linked List)라고 하는 중요한 자료구조의 구현을 살펴보겠습니다. 가장 간단한 형태의 연결 리스트는 한 방향으로 연결된 리스트로 리스트를 구성하는 각 노드는 리스트 내의 다음 노드에 대한 정보를 함께 저장하고 있습니다.

단일연결리스트

연결 리스트의 가장 첫 번째 노드와 가장 마지막 노드는 특별히 head와 tail이라 이름을 붙여 놓습니다.

연결 리스트를 구성하는 요소는 노드라고 부르며 노드에 포함된 다음 노드에 대한 정보를 바탕으로 연결 리스트를 구성하는 모든 요소를 탐색할 수 있습니다.

구현

#include <string>
#include <iostream>

using namespace std;

class StringNode {
    private:
        string elem;
        StringNode* next;

        friend class StringLinkedList;
};

class StringLinkedList {
    public:
        StringLinkedList();
        ~StringLinkedList();
        string fnGet(int idx);
        void fnInsert(int idx, const string& e);
        void fnRemove(int idx);
    private:
        StringNode* head;
};

삽입

삽입은 두 가지 경우가 존재할 수 있습니다.

첫번째 요소로 삽입(head를 교체)하는 경우 :

(a) 새로운 요소를 생성합니다.

(b) 새로운 요소의 next가 현재 head 값을 가르키도록 합니다.

(c) head 변수가 새로 생성한 요소를 가르키도록 합니다.

첫 번째 이후의 요소로 삽입하는 경우 :

(a) 새로운 요소를 생성합니다. 새로운 요소가 위치할 자리의 이전 요소(prv)를 찾습니다.

(b) 새로운 요소의 next 값이 prv의 다음 요소를 가르키도록 합니다.

(c) prv 의 next 값이 새로 생성한 요소를 가르키도록 합니다.

이를 고려하여 구현하면 다음과 같이 됩니다.

void StringLinkedList::fnInsert(int idx, const string& e) {
    StringNode* v = new StringNode;    
    v->elem = e;
    v->next = NULL;

    if (head == NULL) {
        if (idx != 0) {
            return;
        } else {
            head = v;
        }
    } else {
        StringNode* prv = head;
        if (idx == 0) {
            v->next = prv;
            head = v;
        } else {
            while (idx>1) {
                prv = prv->next;
                idx--;
            }
            v->next = prv->next;
            prv->next = v;
        }
    }
}

삭제

삭제 역시 두 가지 경우로 나눌 수 있습니다.

첫 번째 요소를 삭제하는 경우 :

(a) 현재 head를 임의의 변수(old)에 저장합니다.

(b) head를 기존 head의 다음요소로 변경합니다.

(c) 기존 head인 old를 삭제합니다.

 

첫 번째 이후의 요소를 삭제하는 경우 :

(a) 삭제하고자 하는 요소 이전 요소를 찾습니다. (prv)

(b) 삭제할 요소는 prv의 다음요소로 저장합니다.

(c) prv 의 다음요소에 target 의 다음요소를 저장한 후, target 은 삭제합니다.

이를 종합하여 구현한 결과는 다음고 같습니다.

void StringLinkedList::fnRemove(int idx) {
    if (head == NULL) {
        return;
    } else {
        if (idx == 0) {
            StringNode* old = head;
            head = old->next;
            delete old;
        } else {
            StringNode* prv = head;
            while(idx>1) {
                prv = prv->next;
                idx--;
            }
            StringNode* target = prv->next;
            prv->next = target->next;
            delete target;
        }
    }
}

동작확인

화면 출력을 위한 코드 및 연결리스트 사용

const string& StringLinkedList::fnGet(int idx) const {
    StringNode* v = head;
    while(idx>0) {
        v = v->next;
        idx--;
    }
    return v->elem;
}

int main (void) {
    StringLinkedList* SL = new StringLinkedList();

    SL->fnInsert(0, "3");
    SL->fnInsert(1, "5");
    SL->fnInsert(2, "8");
    SL->fnInsert(3, "10");

    // 3 -> 5 -> 8 -> 10
    for (int i=0;i<4;i++) {
        cout << SL->fnGet(i) << " ";
    }
    cout << endl;

    // 3 -> 5 -> 11 -> 8 -> 10
    SL->fnInsert(2, "11");
    for (int i=0;i<5;i++) {
        cout << SL->fnGet(i) << " ";
    }
    cout << endl;

    SL->fnRemove(0);

    // 5 -> 11 -> 8 -> 10
    for (int i=0;i<4;i++) {
        cout << SL->fnGet(i) << " ";
    }
    cout << endl;

    SL->fnRemove(3);

    // 5 -> 11 -> 8
    for (int i=0;i<3;i++) {
        cout << SL->fnGet(i) << " ";
    }
    cout << endl;

    return EXIT_SUCCESS;
    // 실행결과
    // 3 5 8 10 
    // 3 5 11 8 10 
    // 5 11 8 10 
    // 5 11 8
}