โปรแกรม C++ สร้าง Doubly Linked List (ลิงค์ลิสต์สองทิศทาง)

Doubly Linked List เป็นโครงสร้างข้อมูลที่แต่ละ Node มี 3 ส่วน:

• data - ข้อมูล
• prev - จุดชี้ไป Node ก่อนหน้า
• next - จุดชี้ไป Node ถัดไป

โครงสร้าง Node

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

Node* head = nullptr;  // จุดเริ่มต้นของลิสต์

โค้ดโปรแกรม Doubly Linked List

#include <iostream>
using namespace std;

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

Node* head = nullptr;

// เพิ่มข้อมูลที่หัวลิสต์ (Insert at Front)
void insert(int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->prev = nullptr;
    newNode->next = head;
    
    if (head != nullptr)
        head->prev = newNode;  // node เก่าชี้กลับมาที่ node ใหม่
    
    head = newNode;  // head ชี้ไป node ใหม่
}

// แสดงข้อมูลจากหน้าไปหลัง (Forward)
void displayForward() {
    Node* ptr = head;
    cout << "Forward: ";
    while (ptr != nullptr) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
    cout << endl;
}

// แสดงข้อมูลจากหลังมาหน้า (Backward)
void displayBackward() {
    if (head == nullptr) {
        cout << "List is empty" << endl;
        return;
    }
    
    // หา tail ก่อน
    Node* ptr = head;
    while (ptr->next != nullptr)
        ptr = ptr->next;
    
    cout << "Backward: ";
    while (ptr != nullptr) {
        cout << ptr->data << " ";
        ptr = ptr->prev;
    }
    cout << endl;
}

// เพิ่มข้อมูลที่ท้ายลิสต์ (Append)
void append(int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = nullptr;
    
    if (head == nullptr) {
        newNode->prev = nullptr;
        head = newNode;
        return;
    }
    
    Node* ptr = head;
    while (ptr->next != nullptr)
        ptr = ptr->next;
    
    ptr->next = newNode;
    newNode->prev = ptr;
}

// ลบข้อมูล (Delete by value)
void deleteNode(int key) {
    if (head == nullptr) return;
    
    Node* ptr = head;
    
    // หา node ที่ต้องการลบ
    while (ptr != nullptr && ptr->data != key)
        ptr = ptr->next;
    
    if (ptr == nullptr) {
        cout << "Value not found" << endl;
        return;
    }
    
    // ปรับ pointer
    if (ptr->prev != nullptr)
        ptr->prev->next = ptr->next;
    else
        head = ptr->next;  // ลบ head
    
    if (ptr->next != nullptr)
        ptr->next->prev = ptr->prev;
    
    delete ptr;
    cout << key << " deleted." << endl;
}

int main() {
    // เพิ่มข้อมูลที่หัว
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    
    cout << "Doubly Linked List:" << endl;
    displayForward();
    displayBackward();
    
    // เพิ่มที่ท้าย
    append(99);
    cout << "After append(99):" << endl;
    displayForward();
    
    // ลบข้อมูล
    deleteNode(7);
    cout << "After delete(7):" << endl;
    displayForward();
    displayBackward();
    
    return 0;
}

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

Doubly Linked List:
Forward: 9 2 7 1 3
Backward: 3 1 7 2 9
After append(99):
Forward: 9 2 7 1 3 99
Backward: 99 3 1 7 2 9
After delete(7):
Forward: 9 2 1 3 99
Backward: 99 3 1 2 9

การดำเนินการหลักและ Complexity

ข้อดีเทียบ Singly Linked List

• เดินได้ 2 ทิศทาง (Forward/Backward)
• ลบ Node ได้ง่ายกว่า (มี prev pointer)
• Reverse traversal ไม่ต้อง reverse list ก่อน

ข้อเสีย

• ใช้หน่วยความจำมากกว่า (มี pointer เพิ่ม)
• โค้ดซับซ้อนกว่า (ต้องจัดการ prev และ next)