Doubly Linked Circular List ใน C++

ภาพรวม Doubly Linked Circular List

Doubly Linked Circular List เป็นโครงสร้างข้อมูลที่รวมคุณสมบัติของ:

• Doubly Linked List - โหนดมี Pointer ไปทั้ง Next และ Previous
• Circular List - โหนดสุดท้ายชี้กลับมาหาโหนดแรก และโหนดแรกชี้ย้อนกลับไปหาโหนดสุดท้าย

โครงสร้างโหนด

struct Node {
    int data;
    int key;       // Optional: สำหรับค้นหา
    Node* next;
    Node* prev;
};

การเชื่อมโยงแบบ Circular

head->prev = last;   // Head ชี้ย้อนกลับไป Last
last->next = head;   // Last ชี้ไป Head

อัลกอริทึมหลัก

1. Insert First (แทรกหน้า)

INSERT_FIRST(key, data):
    newNode = createNode(key, data)
    IF list is EMPTY:
        head = last = newNode
        newNode->next = newNode->prev = newNode
    ELSE:
        newNode->next = head
        newNode->prev = last
        head->prev = newNode
        last->next = newNode
        head = newNode

2. Insert Last (แทรกท้าย)

INSERT_LAST(key, data):
    newNode = createNode(key, data)
    IF list is EMPTY:
        head = last = newNode
        newNode->next = newNode->prev = newNode
    ELSE:
        newNode->next = head
        newNode->prev = last
        last->next = newNode
        head->prev = newNode
        last = newNode

3. Insert After (แทรกหลัง Key ที่กำหนด)

INSERT_AFTER(targetKey, newKey, data):
    current = head
    WHILE current->key != targetKey:
        current = current->next
        IF current == head: RETURN FALSE  // Not found
    
    newNode = createNode(newKey, data)
    newNode->next = current->next
    newNode->prev = current
    current->next->prev = newNode
    current->next = newNode
    
    IF current == last:
        last = newNode
    RETURN TRUE

4. Delete First

DELETE_FIRST():
    IF EMPTY: RETURN NULL
    temp = head
    IF head == last:  // Only one node
        head = last = NULL
    ELSE:
        head = head->next
        head->prev = last
        last->next = head
    RETURN temp

5. Delete Last

DELETE_LAST():
    IF EMPTY: RETURN NULL
    temp = last
    IF head == last:
        head = last = NULL
    ELSE:
        last = last->prev
        last->next = head
        head->prev = last
    RETURN temp

6. Delete by Key

DELETE_KEY(key):
    IF EMPTY: RETURN NULL
    current = head
    WHILE current->key != key:
        current = current->next
        IF current == head: RETURN NULL  // Not found
    
    IF current == head: RETURN DELETE_FIRST()
    IF current == last: RETURN DELETE_LAST()
    
    current->prev->next = current->next
    current->next->prev = current->prev
    RETURN current

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
using namespace std;

struct Node {
    int data;
    int key;
    Node* next;
    Node* prev;
    
    Node(int k, int d) : key(k), data(d), next(nullptr), prev(nullptr) {}
};

class DoublyCircularList {
private:
    Node* head;
    Node* last;
    
public:
    DoublyCircularList() : head(nullptr), last(nullptr) {}
    
    bool isEmpty() { return head == nullptr; }
    
    void insertFirst(int key, int data) {
        Node* newNode = new Node(key, data);
        if (isEmpty()) {
            head = last = newNode;
            newNode->next = newNode->prev = newNode;
        } else {
            newNode->next = head;
            newNode->prev = last;
            head->prev = newNode;
            last->next = newNode;
            head = newNode;
        }
    }
    
    void insertLast(int key, int data) {
        Node* newNode = new Node(key, data);
        if (isEmpty()) {
            head = last = newNode;
            newNode->next = newNode->prev = newNode;
        } else {
            newNode->next = head;
            newNode->prev = last;
            last->next = newNode;
            head->prev = newNode;
            last = newNode;
        }
    }
    
    bool insertAfter(int targetKey, int newKey, int data) {
        if (isEmpty()) return false;
        
        Node* current = head;
        do {
            if (current->key == targetKey) break;
            current = current->next;
        } while (current != head);
        
        if (current->key != targetKey) return false;
        
        Node* newNode = new Node(newKey, data);
        newNode->next = current->next;
        newNode->prev = current;
        current->next->prev = newNode;
        current->next = newNode;
        
        if (current == last) last = newNode;
        return true;
    }
    
    Node* deleteFirst() {
        if (isEmpty()) return nullptr;
        Node* temp = head;
        if (head == last) {
            head = last = nullptr;
        } else {
            head = head->next;
            head->prev = last;
            last->next = head;
        }
        temp->next = temp->prev = nullptr;
        return temp;
    }
    
    Node* deleteLast() {
        if (isEmpty()) return nullptr;
        Node* temp = last;
        if (head == last) {
            head = last = nullptr;
        } else {
            last = last->prev;
            last->next = head;
            head->prev = last;
        }
        temp->next = temp->prev = nullptr;
        return temp;
    }
    
    Node* deleteKey(int key) {
        if (isEmpty()) return nullptr;
        
        Node* current = head;
        do {
            if (current->key == key) break;
            current = current->next;
        } while (current != head);
        
        if (current->key != key) return nullptr;
        
        if (current == head) return deleteFirst();
        if (current == last) return deleteLast();
        
        current->prev->next = current->next;
        current->next->prev = current->prev;
        current->next = current->prev = nullptr;
        return current;
    }
    
    void displayForward() {
        if (isEmpty()) { cout << "List is empty\n"; return; }
        Node* current = head;
        cout << "[ ";
        do {
            cout << "(" << current->key << "," << current->data << ") ";
            current = current->next;
        } while (current != head);
        cout << "]\n";
    }
    
    void displayBackward() {
        if (isEmpty()) { cout << "List is empty\n"; return; }
        Node* current = last;
        cout << "[ ";
        do {
            cout << "(" << current->key << "," << current->data << ") ";
            current = current->prev;
        } while (current != last);
        cout << "]\n";
    }
};

int main() {
    DoublyCircularList list;
    
    cout << "=== Doubly Circular Linked List Demo ===\n\n";
    
    // Insert First: 1,10 → 2,20 → 3,30 → 4,1 → 5,40 → 6,56
    list.insertFirst(1, 10);
    list.insertFirst(2, 20);
    list.insertFirst(3, 30);
    list.insertFirst(4, 1);
    list.insertFirst(5, 40);
    list.insertFirst(6, 56);
    
    cout << "List (Forward): ";
    list.displayForward();
    
    cout << "List (Backward): ";
    list.displayBackward();
    
    cout << "\nDelete First:\n";
    Node* del = list.deleteFirst();
    if (del) { cout << "Deleted: (" << del->key << "," << del->data << ")\n"; delete del; }
    list.displayForward();
    
    cout << "\nDelete Last:\n";
    del = list.deleteLast();
    if (del) { cout << "Deleted: (" << del->key << "," << del->data << ")\n"; delete del; }
    list.displayForward();
    
    cout << "\nInsert After key 4 (new key 7, data 13):\n";
    list.insertAfter(4, 7, 13);
    list.displayForward();
    
    cout << "\nDelete Key 4:\n";
    del = list.deleteKey(4);
    if (del) { cout << "Deleted: (" << del->key << "," << del->data << ")\n"; delete del; }
    list.displayForward();
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

=== Doubly Circular Linked List Demo ===

List (Forward): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Backward): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]

Delete First:
Deleted: (6,56)
List (Forward): [ (5,40) (4,1) (3,30) (2,20) (1,10) ]

Delete Last:
Deleted: (1,10)
List (Forward): [ (5,40) (4,1) (3,30) (2,20) ]

Insert After key 4 (new key 7, data 13):
List (Forward): [ (5,40) (4,1) (7,13) (3,30) (2,20) ]

Delete Key 4:
Deleted: (4,1)
List (Forward): [ (5,40) (7,13) (3,30) (2,20) ]

ความซับซ้อนของอัลกอริทึม

ประยุกต์ใช้งานจริง

• Music Playlist - เล่นวนรอบ, Next/Previous, Add/Remove เพลง
• Browser History - Back/Forward, Circular Buffer
• Round Robin Scheduling - Process Queue วนรอบ
• Cache Implementation - LRU Cache (ด้วย Hash Map)
• Game Development - Entity Management, Turn-based Systems

ข้อได้เปรียบเหนือ Singly Circular

• ท่องได้ 2 ทิศทาง (Forward/Backward)
• Delete โดยไม่ต้อง Traverse หา Previous Node
• Insert Before ได้ง่าย (แค่ Insert After Previous)
• เหมาะกับ Application ที่ต้องการ Navigation ย้อนกลับ