🔗 連結串列學習指南

什麼是連結串列？

連結串列（Linked List）是一種線性資料結構，由一系列節點組成，每個節點包含資料和指向下一個節點的指標。

與陣列不同，連結串列的節點不需要連續的記憶體空間。

連結串列的類型

• 單向連結串列（Singly Linked List）：每個節點只有指向下一個節點的指標
• 雙向連結串列（Doubly Linked List）：每個節點有指向前後兩個節點的指標
• 循環連結串列（Circular Linked List）：最後一個節點指向第一個節點，形成環

時間複雜度

* 需要維護尾指標

程式碼範例

C++ 單向連結串列

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
    
public:
    LinkedList() : head(nullptr) {}
    
    // 插入到頭部
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }
    
    // 插入到尾部
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* curr = head;
        while (curr->next) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
    
    // 刪除指定值
    void deleteNode(int val) {
        if (!head) return;
        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        Node* curr = head;
        while (curr->next && curr->next->data != val) {
            curr = curr->next;
        }
        if (curr->next) {
            Node* temp = curr->next;
            curr->next = temp->next;
            delete temp;
        }
    }
    
    // 顯示串列
    void display() {
        Node* curr = head;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "NULL" << endl;
    }
    
    ~LinkedList() {
        Node* curr = head;
        while (curr) {
            Node* temp = curr;
            curr = curr->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList list;
    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtHead(1);
    list.insertAtTail(4);
    list.display();  // 1 -> 2 -> 3 -> 4 -> NULL
    
    list.deleteNode(2);
    list.display();  // 1 -> 3 -> 4 -> NULL
    
    return 0;
}

Java 雙向連結串列

class DoublyLinkedList {
    private Node head;
    private Node tail;
    
    private class Node {
        int data;
        Node prev;
        Node next;
        
        Node(int d) { data = d; }
    }
    
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }
    
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }
    
    public void printForward() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " <-> ");
            curr = curr.next;
        }
        System.out.println("NULL");
    }
    
    public void printBackward() {
        Node curr = tail;
        while (curr != null) {
            System.out.print(curr.data + " <-> ");
            curr = curr.prev;
        }
        System.out.println("NULL");
    }
}

優缺點比較

優點

• 動態大小：可隨時增減節點
• 高效插入刪除：頭部操作 O(1)
• 記憶體彈性：不需要連續空間

缺點

• 無法隨機存取，需要遍歷
• 額外記憶體開銷（指標）
• 快取效能較差（非連續記憶體）