โปรแกรม C++ สร้าง Singly Linked List (ลิงค์ลิสต์เดี่ยว)

Singly Linked List เป็นโครงสร้างข้อมูลพื้นฐานที่ประกอบด้วย Node ต่อกันเป็นโซ่ แต่ละ Node มี:

• data - ข้อมูล
• next - จุดชี้ไป Node ถัดไป (NULL ถ้าเป็น Node สุดท้าย)

โครงสร้าง Node

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

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

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

#include <iostream>
using namespace std;

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

Node* head = nullptr;

// เพิ่มที่หน้า (Insert at Front) - O(1)
void insert(int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = head;
    head = newNode;
}

// เพิ่มที่ท้าย (Append) - O(n)
void append(int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = nullptr;
    
    if (head == nullptr) {
        head = newNode;
        return;
    }
    
    Node* ptr = head;
    while (ptr->next != nullptr)
        ptr = ptr->next;
    ptr->next = newNode;
}

// เพิ่มหลัง Node ที่กำหนด (Insert After) - O(n)
void insertAfter(int key, int newData) {
    Node* ptr = head;
    while (ptr != nullptr && ptr->data != key)
        ptr = ptr->next;
    
    if (ptr == nullptr) {
        cout << "Key not found" << endl;
        return;
    }
    
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = ptr->next;
    ptr->next = newNode;
}

// ลบ Node แรก (Delete Front) - O(1)
void deleteFront() {
    if (head == nullptr) return;
    Node* temp = head;
    head = head->next;
    delete temp;
}

// ลบ Node ตามค่า (Delete by Value) - O(n)
void deleteValue(int key) {
    if (head == nullptr) return;
    
    if (head->data == key) {
        deleteFront();
        return;
    }
    
    Node* ptr = head;
    while (ptr->next != nullptr && ptr->next->data != key)
        ptr = ptr->next;
    
    if (ptr->next == nullptr) {
        cout << "Value not found" << endl;
        return;
    }
    
    Node* temp = ptr->next;
    ptr->next = ptr->next->next;
    delete temp;
}

// ค้นหาข้อมูล (Search) - O(n)
bool search(int key) {
    Node* ptr = head;
    while (ptr != nullptr) {
        if (ptr->data == key) return true;
        ptr = ptr->next;
    }
    return false;
}

// แสดงข้อมูล (Display) - O(n)
void display() {
    if (head == nullptr) {
        cout << "List is empty" << endl;
        return;
    }
    
    Node* ptr = head;
    cout << "Linked List: ";
    while (ptr != nullptr) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
    cout << endl;
}

// หาขนาดลิสต์ (Size) - O(n)
int size() {
    int count = 0;
    Node* ptr = head;
    while (ptr != nullptr) {
        count++;
        ptr = ptr->next;
    }
    return count;
}

// ทำความสะอาดหน่วยความจำ
void clear() {
    while (head != nullptr)
        deleteFront();
}

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    
    cout << "Initial List:" << endl;
    display();
    cout << "Size: " << size() << endl;
    
    append(99);
    cout << "After append(99):" << endl;
    display();
    
    insertAfter(7, 55);
    cout << "After insertAfter(7, 55):" << endl;
    display();
    
    deleteValue(7);
    cout << "After deleteValue(7):" << endl;
    display();
    
    cout << "Search 55: " << (search(55) ? "Found" : "Not Found") << endl;
    cout << "Search 100: " << (search(100) ? "Found" : "Not Found") << endl;
    
    clear();
    return 0;
}

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

Initial List:
Linked List: 9 2 7 1 3
Size: 5
After append(99):
Linked List: 9 2 7 1 3 99
After insertAfter(7, 55):
Linked List: 9 2 7 55 1 3 99
After deleteValue(7):
Linked List: 9 2 55 1 3 99
Search 55: Found
Search 100: Not Found

สรุป Complexity

ข้อดีและข้อเสีย

เมื่อไหร่ควรใช้ Linked List แทน Array/Vector?

• Insert/Delete ที่หน้าบ่อยมาก
• ไม่รู้ขนาดล่วงหน้า และอาจใหญ่มาก
• ต้องการความยืดหยุ่นสูงสุด
• ไม่ต้องการ Random Access