[C++] 더블 링크드 리스트 (Double Linked List)

1. Why

만약, 배열에 데이터가 있을 때, 중간에 삭제하게 되면, 삭제한 부분을 어떻게 메꿔야 할까?
만약, 배열의 시작 지점(arr[0]) 앞에 데이터를 삽입할 경우가 생긴다면 어떻게 해야할까?
이러한 문제를 해결 할 수는 없을까?

 

2. What / How

순차적으로 하나씩 입력이 가능한 배열이다.
리스트의 장점은 중간에 새로운 데이터를 삽입할 때,
기존 데이터를 전부 다 뒤로 한칸씩 미룰 필요가 없다.
(이유는 포인터로 주소값을 가지기 때문)

링크드 리스트 비용

	삽입 (Insert)	삭제 (Remove)	탐색 (contains or search)
링크드 리스트	O(1)	O(n)	O(n)

각 함수의 설명은 코드로 대신하겠습니다.

void init(int size);
void insert(Type value);
void insert(Type value, Type position);
bool remove(Type value);
bool contains(Type value);

 

3. 샘플코드

참고로 편의상 다 public 으로 선언했는데, head, tail, size, MAX 는 숨기는 게 설계상 맞다.

public 과 private의 구분이 왜 필요한지 간략하게 설명하면, 이 클래스를 사용하는 입장에서 굳이 몰라도 되는 것들을 가리는 것이다.
하지만 알고리즘 공부할 때는 어차피 혼자 다 구현하고, 서비스간 복잡도도 계산할 필요없으니, 그딴 건 일도 없어~

#include <iostream>
using namespace std;

template <typename Type>
class Node {
public:
    Type value;
    Node *next;
    Node *prev;
};

template <typename Type>
class LinkedList {
public:
    Node<Type> *head;
    Node<Type> *tail;
    int size;
    int MAX;

    LinkedList();
    ~LinkedList();

    void init(int size);
    void insert(Type value); // insert a data(value) at the rear of the list
    void insert(Type value, Type position); // insert a data(value) after the position.
    bool remove(Type value);
    bool contains(Type value);
};

template <typename Type>
LinkedList<Type>::LinkedList() {
    size = 0;
    head = new Node<Type>;
    tail = new Node<Type>;
    head->next = head;
    head->prev = tail;
    tail->next = head;
    tail->prev = tail;
}

template <typename Type>
LinkedList<Type>::~LinkedList() {
    Node<Type> *current = tail;
    while (current != current->next) {
        current = current->next;
        Node<Type> *temp = current;
        delete temp;
    }
}

template <typename Type>
void LinkedList<Type>::init(int size) {
    MAX = size;
}

template <typename Type>
void LinkedList<Type>::insert(Type value) {
    if (size + 1 == MAX) {
        return;
    }
    Node<Type> *prev = head->prev;
    Node<Type> *newNode = new Node<Type>;
    newNode->value = value;
    newNode->next = head;
    newNode->prev = prev;
    prev->next = newNode;
    head->prev = newNode;
    size++;
}

template <typename Type>
void LinkedList<Type>::insert(Type value, Type position) {
    if (size + 1 == MAX) {
        return;
    }
    Node<Type> *current = tail;
    while (current != current->next) {
         if (current->value == value) {
            Node<Type> *next = current->next;
            Node<Type> *newNode = new Node<Type>;
            newNode->value = value;
            newNode->next = next;
            newNode->prev = current;
            current->next = newNode;
            next->prev = newNode;
            size++;
            break;
         }
    }
}

template <typename Type>
bool LinkedList<Type>::remove(Type value) {
    if (size == 0) {
        return false;
    }
    Node<Type> *current = tail;
    while (current != current->next) {
        current = current->next;
        if (current->value == value) {
            Node<Type> *prev = current->prev;
            Node<Type> *next = current->next;
            delete current;
            prev->next = next;
            next->prev = prev;
            size--;
            return true;
        }
        
    }
    return false;
}

template <typename Type>
bool LinkedList<Type>::contains(Type value) {
    Node<Type> *current  = tail;
    while(current != current->next) {
        current = current->next;
        if (current->value == value) {
            return true;
        }
    }
    return false;
}

int main() {
    LinkedList<int> linkedList;
    linkedList.init(4);
    for (int i = 1; i <= 5; ++i) {
        linkedList.insert(i);
    }
    cout << "contains 0: " << linkedList.contains(0) << endl; // 1
    cout << "contains 3: " << linkedList.contains(3) << endl; // 1
    cout << "contains 4: " << linkedList.contains(4) << endl; // 0
    cout << "remove 2: " << linkedList.remove(2) << endl; //1
    cout << "contains 1: " << linkedList.contains(1) << endl; // 0
}

 

이 코드에 void push(Type value), Type pop()만 잘 구현하면, 스택(Stack)이랑 큐(Queue) 쌉파써블.