[자료구조] 2. 연결 리스트(Linked List)

연결 리스트

연결 리스트(Linked List)는 배열과 유사하게 리스트를 표현하는 자료구조입니다. 연결 리스트는 여러 개의 노드로 이루어져 있으며, 각 노드에 데이터가 저장됩니다.

 

각 노드는 값(value)을 저장하는 공간과 다음 노드를 가리키는 포인터로 구성되어 있습니다. 이때 노드가 다음 노드를 가리키는 포인터 1개 만을 가진다면 singly linked list(단일 연결 리스트), 다음 노드뿐만 아니라 자신의 이전 노드를 가리키는 포인터도 가지면. doubly linked list(이중 연결 리스트)라고 합니다.

Head와 Tail

다음은 단일 연결 리스트의 모습입니다.

연결 리스트는 첫 번째 노드를 가리키는 head 포인터와 마지막 노드를 가리키는 tail 포인터를 가지고 있습니다.

이때 노드가 하나뿐이라면 해당 노드가 Head와 Tail을 겸하게 되며, 노드가 없다면 Head와 Tail은 nullptr가 됩니다.

 

위와 같이 head포인터와 tail포인터 방식을 사용하면 노드가 2개 이상일 때, 1개일 때, 0개일 때에 대하여 모두 예외 처리를 해주어야 해서 구현이 복잡합니다. 이러한 단점을 해결한방식이 header와 tailer를 이용하는 방식입니다.

우선 더미 노드를 만들어서 header와 tailer로 명명합니다. 이때 실제 첫 번째 노드는 header->next가 가리키며, 마지막 노드는 tailer->prev가 가리키게 됩니다. 이러한 방식의 장점은 삽입과 삭제가 간편해지며, 리스트가 비어있을 때의 상태를 다루기가 용이하다는 점입니다. 만약 이러한 header와 tailer를 사용하지 않는다면, 리스트가 비어있을 때 예외 처리를 신경 써줘야 합니다. 또한, header와 tailer를 사용하면 메모리의 지역성이 향상되는데, 이는 메모리 캐시의 성능을 향상할 수 있습니다. 이를 사용하지 않으면 head와 tail의 위치가 계속 변경될 수 있습니다.

ADT

연결 리스트는 리스트의 구현체이고, 리스트에서 자신의 사이즈와 비었는지 여부를 체크하는 기능은 유용합니다.

int getSize()
bool isEmpty()

연결 리스트에서 저장하고 있는 것은 처음 head와 tail의 정보이기에 head와 tail에 데이터를 추가하거나 삭제하는 시간은 O(1)로 매우 짧습니다(이중 연결 리스트일 때 경우로, 단일 연결 리스트일 경우에는 tail에서의 접근이 느릴 수 있습니다). 그리하여 리스트의 양쪽 끝에서 데이터를 삽입/삭제하는 것에 유용합니다. 이는 이후 소개할 큐/덱 자료구조와 유사한데, 이런 특성으로 연결 리스트는 큐/덱의 구현체로도 사용할 수 있습니다.

// typename T
void addHead(T element) // element값을 리스트 처음에 삽입
void addTail(T element) // element값을 리스트 마지막에 삽입
T removeHead() // 리스트 처음의 요소 삭제후 값 반환
T removeTail() // 리스트 마지막의 요소 삭제후 값 반환

연결 리스트는 노드 탐색에 O(n)의 시간이 소요되기에 매번 노드를 탐색해야 하는 작업에는 비효율적입니다. 그렇기에 연결 리스트는 매번 탐색하는 대신 노드의 위치를 기억해 두었다가 사용할 때 유용합니다.

T* getHead()
T* getTail()
void insert(T* position, element) // position 노드의 다음 위치에 요소를 삽입한다
T remove(T* position)

반복문 사용 시에는 for(T* cur=getHead(); cur=cur->next(); cur!=getTail()) 식으로 iterator로 사용됩니다.

구현

다음 C++ 코드는 header, tailer를 사용한 Doubly Linked List의 C++ 구현입니다.

class Node {
  public:
    int data;
    Node *next;
    Node *prev;
};

class DoublyLinkedList {
  private:
    Node *header;
    Node *tailer;
    int listSize;

    void _add(Node *idx, int data) {
        // Add new node after given node
        Node *newNode = new Node;
        newNode->data = data;
        newNode->next = idx->next;
        newNode->prev = idx;
        idx->next = newNode;
        newNode->next->prev = newNode;
        listSize++;
    }
    int _remove(Node *idx) {
        int temp;
        temp = idx->data;
        idx->next->prev = idx->prev;
        idx->prev->next = idx->next;
        delete idx;
        listSize--;
        return temp;
    }

  public:
    DoublyLinkedList() {
        header = new Node();
        tailer = new Node();
        header->next = tailer;
        tailer->prev = header;
        listSize = 0;
    }
    ~DoublyLinkedList() {
        while (!isEmpty())
            removeHead();
        delete header;
        delete tailer;
    }
    bool isEmpty() { return (listSize == 0); }
    int getSize() { return listSize; }
    void addHead(int data) { _add(header, data); }
    void addTail(int data) { _add(tailer->prev, data); }
    int removeHead() {
        if (isEmpty())
            return -1;
        return _remove(header->next);
    }
    int removeTail() {
        if (isEmpty())
            return -1;
        return _remove(tailer->prev);
    }
    void insert(int idx, int data) {
        // to add on first place -> insert(0, n)
        if (idx > listSize || idx < 0) {
            return;
        }
        _add(getNodeByIndex(idx)->prev, data);
    }
    void update(int idx, int data) {
        if (idx >= listSize || idx < 0)
            return;
        getNodeByIndex(idx)->data = data;
    }
    int remove(int idx) {
        // to remove first node -> remove(0)
        if (idx >= listSize || idx < 0) {
            return -1;
        }
        Node *cur = getNodeByIndex(idx);
        int ret = cur->data;
        _remove(cur);
        return ret;
    }
};

배열과 비교한 연결 리스트의 특징

장점

배열과 비교한 연결 리스트의 장점은 값의 삽입/삭제가 빠르다는 것입니다. 삽입/삭제 시에 포인터만 변경해 주면 되기 때문에 O(1)에 삽입/삭제가 가능합니다.

단점

단점은 탐색이 배열에 비해 느리다는 것입니다. 배열은 연속된 위치에 값이 있기에, n번째 값을 얻기 위해 단순히 메모리 값을 계산해서 접근하면 되지만, 연결 리스트는 값이 무작위적으로 위치할 수 있어 처음부터 계속 포인터를 따라가며 확인해야 합니다. 그렇기에 O(n) 시간이 소요됩니다.