C++ 鏈表從入門到精通：內存佈局、手動實現、插入刪除與 STL 選擇指南

為什麼需要鏈表？

結論：頻繁中間插刪、數據量不可預估、不需要隨機訪問 → 選鏈表；其餘多數場景 Vector 更優。

節點結構與最小實現

struct Node {
    int val;
    Node* next;
    Node(int v = 0) : val(v), next(nullptr) {}
};

三種構建方式對比

// 1. 栈上構建（僅教學演示）
Node n1(1), n2(2); n1.next = &n2;

// 2. 堆上逐個 new（頭插法，逆序）
Node* head = new Node(15);
for (int i = 0; i < 10; ++i) {
    Node* cur = new Node(i);
    cur->next = head;
    head = cur;
}

// 3. 尾插法（保持輸入順序）
Node *head = nullptr, *tail = nullptr;
for (int x : data) {
    Node* cur = new Node(x);
    if (!head) head = tail = cur;
    else { tail->next = cur; tail = cur; }
}

遍歷、插入、刪除核心邏輯

遍歷

for (Node* p = head; p; p = p->next) 
    cout << p->val << ' ';

在節點 cur 後插入 ins

ins->next = cur->next;
cur->next = ins;

刪除 cur 後的節點（需保留前驅 pre）

Node* del = cur->next;
cur->next = del->next;
delete del;

完整可運行 Demo

#include 
using namespace std;

struct Node { int val; Node* next; Node(int v=0):val(v),next(nullptr){} };

int main() {
    // 建表：1→2→3→4→5
    Node *head = nullptr, *tail = nullptr;
    for (int i = 1; i <= 5; ++i) {
        Node* cur = new Node(i);
        if (!head) head = tail = cur;
        else { tail->next = cur; tail = cur; }
    }
    // 在 3 後插入 99
    for (Node* p = head; p; p = p->next)
        if (p->val == 3) { 
            Node* ins = new Node(99);
            ins->next = p->next; 
            p->next = ins; 
            break; 
        }
    // 刪除 99
    for (Node *pre = nullptr, *cur = head; cur; pre = cur, cur = cur->next)
        if (cur->val == 99) { pre->next = cur->next; delete cur; break; }
    // 打印
    for (Node* p = head; p; p = p->next) cout << p->val << ' '; // 1 2 3 4 5
    // 釋放
    while (head) { Node* t = head; head = head->next; delete t; }
}

進階話題

• 雙向鏈表：prev 指針使反向遍歷、任意節點刪除均為 O(1) —— STL list 即此實現。
• 循環鏈表：尾節點指向頭，適用於循環調度、Josephus 問題。
• 跳表：多層索引實現 O(log N) 查找，Redis 有序集合底層結構。

STL 實戰建議

#include 
list lst = {1,2,3};
lst.insert(next(lst.begin()), 99);  // O(1) 插入
lst.erase(next(lst.begin()));       // O(1) 刪除
for (int x : lst) cout << x << ' '; // 範圍 for 遍歷

掌握手動實現原理後，實際項目優先使用 std::list 或 std::forward_list，避免手動管理內存導致洩漏/野指針。