Data Structure in C++ - Linked List

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다. 

앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. 

 

| 두 번째 순서는 링크드 리스트이다. 

링크드 리스트 또한 배열과 마찬가지로 Sequential 한 자료구조 중 하나이며, 선형으로 나열된 item들이 서로 연결된 구조이다. 이 구조를 보통 chain이라고 하며 chain의 한쪽 끝 부분만 알고 있으면 모든 Data를 탐색할 수 있다.

그렇다면 링크드 리스트와 배열의 차이는 무엇일까? 만약 size가 빈번하게 변경되는 시나리오라면 배열과 링크드 리스트 중 어떤 자료구조를 사용하는 것이 좋을까? 데이터를 random 하게 접근하지 않는 한 배열을 사용하는 것은 매우 불리하다. 왜냐하면 size의 확장은 축소 연산을 따로 구현하지 않는 한 데이터를 옮기는데(새로운 배열로 copy 하는 데에) 필요한 시간과 더 많은 메모리를 사용하기 때문이다.

 

즉, 빈번한 크기 변동과 순차적 접근에 유리한 자료구조가 필요할 때에는 링크드 리스트가 주로 고려된다. 

아래는 링크드 리스트의 구현예시이다. 

 

using namespace std;

template <typname T>
class Node
{
public:
    T value;
    Node *next;
    Node *previous;

    Node (T value)
    {
        this->value = vlaue;
    }
};

template <typename T>
class LinkedList
{
private:
    int size_;
    Node<T> *head_ = nullptr;
    Node<T> *tail_ = nullptr;
    Node<T> *itr_ = nullptr;

public:
    LinkedList() {
        this->size_ = 0;
    }
    
    void append(T value) {
        if (this->head_ == nullptr) {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        } else {
            this->tail_->next = new Node<T>(value);
            this->tail_->next->previous = this->tail_;
            this->tail_ = this->tail_->next;
        }
        this->size_ += 1;
    }

    void prepend(T value) {
        if(this->head_ == nullptr) {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        } else {
            this->head_->previous = new Node<T>(value);
            this->head_->previous->next = this->head_;
            this->head_ = this->head_->previous;
        }
        this->size_ += 1;
    }

    Node<T> * iterate() {
        if (this->itr_ == NULL) {
            this->itr_ = this->head;
        } else {
            this->itr_ = this->itr_->next;
        }
        return this->itr_;
    }

    T ptr() {
        return this->itr_->value;
    }

    void resetIterator() {
        this->tail_ = NULL;
    }
};

링크들 리스트의 각 item들을 Node라는 구조로 구현하였다. 이 Node는 item의 값과 다음 노드와 이전 노드를 가리키는 포인터로 구성된다.
이렇게 앞과 뒤를 가르키는 링크드 리스트를 더블 링크드 리스트, 쌍방향 링크드 리스트라고도 한다. 
사실 링크드리스트를 구현할 때는 단순히 다음 노드를 가리키는 것으로 충분하지만, 쌍방향으로 가리키게 구현한다면 앞뒤로 리스트를 추가하는데 시간 복잡도 O(1)이면 충분하다. 
append는 tail 즉 리스트의 맨 뒤에 Node를 추가하는 것이고, prepend는 리스트의 맨 앞에 Node를 추가하는 것이다. 

추가로 iteration을 위한 함수와 아이템의 값을 가져오는 함수도 구현하였다. 필수인 것은 아니라 메인 코드에서 따로 구현해주어도 된다. 
위의 코드에는 이해를 돕기 위해 단순한 형태로 구현하여 메모리를 삭제하는 코드가 없다. 하지만 메모리 누수를 방지하기 위해  별도의 소멸자를 구현해주는 것이 좋다. 아래는 소멸자 예시이다.

~LinkedList()
{
    Node<T> *curr = head;

    while(curr != nullptr){
        Node<T> *next = curr->next;
        delete curr;
        curr = next;
    }

    head = tail = itr = nullptr;
}

reference : https://towardsdatascience.com/data-structures-in-c-part-1-b64613b0138d