[DS] 링크드 리스트 - Linked List (개념 및 구현)

이미지 출처 : Pixabay

앞서 구현한 스택과 큐는 모두 배열을 기반으로 작성되었습니다.

배열은 메모리 공간에서 연속적이며, 임의 접근(Random access)가 가능한 장점이 있지만 고정된 크기를 가지고 있으며 연속된 배열 중간의 원소를 삽입/삭제하는데 걸리는 시간이 크다는 단점을 가지고 있습니다.

이러한 단점을 해결하기 위하여 등장한 것이 '연결 리스트 (혹은 링크드 리스트) Linked List' 자료구조입니다.

링크드 리스트는 배열과 달리 원소뿐만 아니라 다음 원소가 어디 있는지에 대한 위치정보를 포함하고 있습니다. 이러한 데이터 덩어리를 '노드 Node' 라고 부릅니다. 링크드 리스트는 메모리 공간에서 연속적이지 않아도 되며 노드들 가운데 새로운 노드를 삽입하거나 삭제하는 것이 배열보다 용이하고 가변적인 크기를 가지고 있습니다. 하지만 링크드 리스트는 임의 접근이 불가능하며, 첫 노드부터 포인터들을 따라 순차 접근(Sequencial access)만 가능합니다. (단, 링크드 리스트를 기저로 작성된 다른 자료구조에서는 이진 탐색(Binary search)과 같은 탐색 알고리즘이 사용될 수 있습니다.) 

배열과 링크드 리스트

링크드 리스트의 가장 첫번째 노드를 head, 마지막 노드를 tail 이라고 부르며, 위와 같이 Head에서 Tail로 이어지는 한 방향 흐름의 포인터들을 가지는 방법으로 링크드 리스트를 구현한 것을 '단일 링크드 리스트 Singly linked list'라고 부릅니다. 단일 링크드 리스트의 Tail 노드는 next로 null을 가리키도록 작성합니다. 단일 링크드 리스트는 Head 부분에 원소의 삽입과 삭제를 상수 시간 내에 수행할 수 있습니다. 하지만 Tail 부분에 원소의 삽입과 삭제를 수행하려면 링크드 리스트 원소의 갯수 n만큼 탐색을 수행한 다음에야 삽입과 삭제를 수행할 수 있습니다. 이를 해결하기 위해 등장한 개념이 '이중 링크드 리스트 Doubly linked list'입니다. 

단일 링크드 리스트와 이중 링크드 리스트

단일 링크드 리스트는 임의의 원소를 삭제할 때, 그 원소의 이전 노드의 *pNext를 삭제할 노드의 다음 노드로 옮겨주어야 합니다. 하지만 노드에는 이전 노드에 대한 정보가 없기 때문에 한 번에 노드를 삭제하는 것이 불가능합니다.

이증 링크드 리스트에서는 경우 해당 노드에 포함된 *pNext와 *pPrev 정보를 활용하여 임의의 노드를 삭제할 수 있습니다. (삽입, 삭제, 정렬 시 단일 링크드 리스트에 비하여 수행해야 할 연산이 조금 더 늘어납니다.)

 

구현에 앞서 예외 처리 클래스는 이전 글에서 작성한 RuntimeException 클래스를 상속받아 작성합니다.

[DS] 스택 - Stack (개념 및 배열로 스택 구현하기)

#include "runtime_exception.h"

class ListOutOfIndexException : public RuntimeException {
public:
	ListOutOfIndexException(const string& error_message) : RuntimeException(error_message) {}
};

class ListEmptyException : public RuntimeException {
public:
	ListEmptyException(const string& error_message) : RuntimeException(error_message) {}
};

다음은 C++을 사용하여 단일 링크드 리스트에 사용될 Node 클래스를 구현한 것입니다.

template<typename Object>
class Node {
    private:
    Object* value_;
    Node<Object> * next_;

    public:
    Node() {
        value_ = nullptr;
        next_ = nullptr;
    }
    Node(Object& value) {
        value_ = &value;
        next_ = nullptr;
    }
    Object& value() {
        return *value_;
    }
    void set_value(Object& value) {
        value_ = &value;
    }
    Node<Object>* next() {
        return next_;
    }
    void set_next(Node<Object> * next) {
        next_ = next;
    }
};

위 노드를 멤버 변수로 가지는 단일 링크드 리스트 클래스는 다음과 같습니다 : 

template<typename Object>
class SinglyLinkedList {
private:
    Node<Object>* head_;
    int size_;

public:
    SinglyLinkedList() {
        head_ = new Node<int>();
        size_ = 0;
    }

    int size() {
        return size_;
    }

    Object& Front() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        return head_->next()->value();
    }

    Object& Back() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        Node<Object> *temp = head_;
        while(temp->next() != nullptr) {
            temp = temp->next();
        }
        return temp->value();
    }


    void PushFront(Object& object) {
        if(head_->next() == nullptr) {
            head_->set_next(new Node<Object>(object));
            size_++;
            return;
        }
        Node<Object> * temp = new Node<Object>(object);
        temp->set_next(head_->next());
        head_->set_next(temp);
        size_++;
    }

    Object& PopFront() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        Node<Object> *temp = head_->next();
        Object& value = temp->value();
        head_->set_next(temp->next());
        delete temp;
        size_--;
        return value;
    }

    void PushBack(Object& object) {
        Node<Object> * temp = head_;
        while(true) {
            if(temp->next() == nullptr) {
                temp->set_next(new Node<Object>(object));
                break;
            }
            temp = temp->next();
        }
        size_++;
    }

    Object& PopBack() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        Node<Object> *temp = head_;
        while(true) {
            if(temp->next()->next() != nullptr) {
                temp = temp->next();
                continue;
            }
            Object& value = temp->next()->value();
            delete temp->next();
            temp->set_next(nullptr);
            size_--;
            return value;
        }
    }

    void InsertAt(Object& object, int index) throw(ListOutOfIndexException) {
        if(index > size_) {
            throw ListOutOfIndexException("Out of Index!\n");
        } else if(index == 0) {
            PushFront(object);
        } else if(index == size_) {
            PushBack(object);
        } else {
            Node<Object> * temp = head_;
            for(int i = 0; i<index; i++) {
                temp = temp->next();
            }
            Node<Object> * new_node = new Node<Object>(object);
            new_node->set_next(temp->next());
            temp->set_next(new_node);
            size_++;
        }
    }

    Object& RemoveAt(int index) throw(ListOutOfIndexException) {
        if(index > size_) {
            throw ListOutOfIndexException("Out of Index!\n");
        } else if(index == 0) {
            return PopFront();
        } else if(index == size_) {
            return PopBack();
        } else {
            Node<Object> * temp = head_;
            for(int i = 0; i<index; i++) {
                temp = temp->next();
            }
            Node<Object> * target_node = temp->next();
            temp->set_next(temp->next()->next());
            Object& value = target_node->value();
            delete target_node;
            size_--;
            return value;
        }
    }
};

각각의 함수는 다음 동작을 수행합니다 : 

Front() : 링크드 리스트의 맨 앞에 위치한 원소를 반환합니다.
Back() : 링크드 리스트의 마지막에 위치한 원소를 반환합니다.
PushFront() : 링크드 리스트의 맨 앞에 원소를 삽입합니다.
PopFront() : 링크드 리스트의 맨 앞에 위치한 원소를 삭제하고 반환합니다.
PushBack() : 링크드 리스트의 마지막 위치에 원소를 삽입합니다.
PopBack() : 링크드 리스트의 마지막 원소를 삭제하고 반환합니다.
InsertAt() : 링크드 리스트의 특정 위치에 원소를 삽입합니다.
RemoveAt() : 링크드 리스트의 특정 위치에 있는 원소를 삭제하고 반환합니다.

이제 이중 링크드 리스트 작성을 위하여 위에서 작성한 노드에 previous 포인터를 추가합니다.

template<typename Object>
class Node {
    private:
    Object* value_;
    Node<Object> * next_;
    Node<Object> * previous_;

    public:
    Node() {
        value_ = nullptr;
        next_ = nullptr;
        previous_ = nullptr;
    }
    Node(Object& value) {
        value_ = &value;
        next_ = nullptr;
        previous_ = nullptr;
    }
    Object& value() {
        return *value_;
    }
    void set_value(Object& value) {
        value_ = &value;
    }
    Node<Object>* next() {
        return next_;
    }
    void set_next(Node<Object> * next) {
        next_ = next;
    }
    Node<Object>* previous() {
        return previous_;
    }
    void set_previous(Node<Object> * previous) {
        previous_ = previous;
    }
};

이중 링크드 리스트는 head 노드 뿐만 아니라 tail 노드에 대한 정보도 가지고 있어야 하며, 초기화 시 head 노드의 next 포인터를 tail로, previous 포인터를 nullptr로 설정해 주어야 하며 마찬가지로 tail 노드의 next 포인터를 nullptr로, previous 포인터를 head로 설정해 줍니다. 또한 삽입/삭제시 next노드와 previous 노드를 동시에 업데이트 해 주어야 합니다.

다음은 위 노드 클래스를 사용하여 구현한 DoublyLinkedList 클래스입니다.

template<typename Object>
class DoublyLinkedList {
private:
    Node<Object>* head_;
    Node<Object>* tail_;
    int size_;

public:
    DoublyLinkedList() {
        head_ = new Node<int>();
        tail_ = new Node<int>();
        head_->set_next(tail_);
        tail_->set_previous(head_);
        size_ = 0;
    }

    int size() {
        return size_;
    }

    Object& Front() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        return head_->next()->value();
    }

    Object& Back() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        return tail_->previous()->value();
    }

    void PushFront(Object& object) {
        Node<Object> * temp = new Node<Object>(object);
        temp->set_next(head_->next());
        head_->next()->set_previous(temp);
        temp->set_previous(head_);
        head_->set_next(temp);
        size_++;
    }

    Object& PopFront() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        Node<Object> *temp = head_->next();
        Object& value = temp->value();
        head_->set_next(temp->next());
        temp->next()->set_previous(head_);
        delete temp;
        size_--;
        return value;
    }

    void PushBack(Object& object) {
        Node<Object> * temp = new Node<Object>(object);
        tail_->previous()->set_next(temp);
        temp->set_previous(tail_->previous());
        temp->set_next(tail_);
        tail_->set_previous(temp);
        size_++;
    }

    Object& PopBack() throw(ListEmptyException){
        if(size_ == 0) {
            throw ListEmptyException("List is Empty!\n");
        }
        Node<Object> *temp = tail_->previous();
        Object& value = temp->value();
        temp->previous()->set_next(tail_);
        tail_->set_previous(temp->previous());
        delete temp;
        size_--;
        return value;
    }

    void InsertAt(Object& object, int index) throw(ListOutOfIndexException) {
        if(index > size_) {
            throw ListOutOfIndexException("Out of Index!\n");
        } else if(index == 0) {
            PushFront(object);
        } else if(index == size_) {
            PushBack(object);
        } else {
            Node<Object> * temp;
            if(index < (size_/2)) {
                temp = head_;
                for(int i = 0; i <= index; i++) {
                    temp = temp->next();
                }
            } else {
                temp = tail_;
                for(int i = 0; i < (size_ - index); i++) {
                    temp = temp->previous();
                }
            }
            Node<Object> * new_node = new Node<Object>(object);
            new_node->set_next(temp);
            temp->previous()->set_next(new_node);
            new_node->set_previous(temp->previous());
            temp->set_previous(new_node);
            size_++;
        }
    }

    Object& RemoveAt(int index) throw(ListOutOfIndexException) {
        if(index > size_) {
            throw ListOutOfIndexException("Out of Index!\n");
        } else if(index == 0) {
            return PopFront();
        } else if(index == size_) {
            return PopBack();
        } else {
            Node<Object> * temp;
            if(index < (size_/2)) {
                temp = head_;
                for(int i = 0; i <= index; i++) {
                    temp = temp->next();
                }
            } else {
                temp = tail_;
                for(int i = 0; i < (size_ - index); i++) {
                    temp = temp->previous();
                }
            }
            temp->next()->set_previous(temp->previous());
            temp->previous()->set_next(temp->next());
            Object& value = temp->value();
            delete temp;
            size_--;
            return value;
        }
    }
};

단일 링크드 리스트와 달리 앞 뒤 노드의 포인터들을 모두 조작해 주어야 해 추가적인 연산이 요구되는 것을 확인할 수 있습니다.