[자료구조] 이중 연결 리스트

이중 연결 리스트

---

이중 연결 리스트(Doubly linked list)는 각 노드가 두 개의 링크 필드를 가지며 이 링크 필드를 통해 양방향으로 움직일 수 있도록 만든 리스트입니다.

단순 연결 리스트의 각 노드는 일반적으로 세 부분으로 구성됩니다.

 

1. 데이터(Data): 노드에 저장된 실제 정보.
2. 다음 포인터(Next Pointer): 다음 노드를 가리키는 참조. 마지막 노드의 다음 포인터는 보통 null로 설정됩니다.
3. 이전 포인터(Previous Pointer): 이전 노드를 가리키는 참조. 첫 번째 노드의 이전 포인터는 보통 null로 설정됩니다.

 

특징

---

• 노드 추가 및 제거의 용이성: 리스트의 중간에 노드를 추가하거나 제거할 때, 이전 노드를 추적할 필요가 없으므로 삽입 및 삭제 작업이 상대적으로 간단하고 효율적입니다.
• 이중 연결 리스트의 어떤 노드든 한 번 접근하고 나면, 그 노드를 기준으로 리스트를 양방향(시작 또는 끝 쪽으로)으로 새롭게 순회할 수 있습니다.
• 첫 번째 노드(헤드)와 마지막 노드(테일)는 순회 없이 즉시 접근할 수 있습니다. 
• 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에 뒤쪽 자료들을 유실한다는 단점이 있습니다.
• 탐색할 때 노드의 순서대로 접근해야 하므로 시간 복잡도가 O(n)입니다.

 

주요 연산

---

1. 삽입
   • 맨 앞에 삽입: 새로운 노드를 리스트의 맨 앞에 추가합니다.
   • 중간에 삽입: 새로운 노드를 리스트의 맨 뒤에 추가합니다.
   • 맨 끝에 삽입: 특정 위치에 새로운 노드를 추가합니다.
2. 삭제
   • 맨 앞의 노드 삭제: 리스트의 맨 앞에 있는 노드를 제거합니다.
   • 맨 뒤의 노드 삭제: 리스트의 맨 뒤에 있는 노드를 제거합니다.
   • 중간 노드 삭제: 특정 위치의 노드를 제거합니다.
3. 탐색
   • 앞에서부터 탐색 : 리스트의 맨 앞에서 시작하여 특정 값을 가진 노드를 찾습니다.
   • 뒤에서부터 탐색 : 리스트의 맨 뒤에서 시작하여 특정 값을 가진 노드를 찾습니다

구현

---

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node* prev;

    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};

// 이중 연결 리스트
class DoublyLinkedList {
private:
    Node* head;
    Node* tail;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // 맨 앞에 삽입
    void insertFront(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    // 맨 뒤에 삽입
    void insertEnd(int value) {
        Node* newNode = new Node(value);
        if (tail == nullptr) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
    }

    // 중간에 삽입
    void insertAtPosition(int value, int position) {
        if (position <= 0) {
            insertFront(value);
            return;
        }

        Node* newNode = new Node(value);
        Node* current = head;
        for (int i = 0; current != nullptr && i < position - 1; ++i) {
            current = current->next;
        }

        if (current == nullptr) {
            insertEnd(value);
            delete newNode;
        } else {
            newNode->next = current->next;
            if (current->next != nullptr) {
                current->next->prev = newNode;
            } else {
                tail = newNode;
            }
            current->next = newNode;
            newNode->prev = current;
        }
    }

    // 맨 앞 노드 삭제
    void deleteFront() {
        if (head == nullptr) {
            return;
        }
        Node* temp = head;
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        } else {
            tail = nullptr;
        }
        delete temp;
    }

    // 맨 뒤 노드 삭제
    void deleteEnd() {
        if (tail == nullptr) {
            return;
        }
        Node* temp = tail;
        tail = tail->prev;
        if (tail != nullptr) {
            tail->next = nullptr;
        } else {
            head = nullptr;
        }
        delete temp;
    }

    // 중간 노드 삭제
    void deleteAtPosition(int position) {
        if (position < 0 || head == nullptr) {
            return;
        }

        if (position == 0) {
            deleteFront();
            return;
        }

        Node* current = head;
        for (int i = 0; current != nullptr && i < position; ++i) {
            current = current->next;
        }

        if (current == nullptr) {
            return;
        }

        if (current->next != nullptr) {
            current->next->prev = current->prev;
        } else {
            tail = current->prev;
        }
        if (current->prev != nullptr) {
            current->prev->next = current->next;
        }

        delete current;
    }

    // 앞에서 부터 탐색
    Node* searchFromFront(int value) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    // 뒤에서 부터 탐색
    Node* searchFromEnd(int value) {
        Node* current = tail;
        while (current != nullptr) {
            if (current->data == value) {
                return current;
            }
            current = current->prev;
        }
        return nullptr;
    }

    ~DoublyLinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};