0. 前言

上一章的順序表底層是數組，封裝了增刪查改的功能接口成為了順序表。存儲順序表的空間是連續的，順序表非常大時，內存可能無法提供這么大的連續空間，由此，鏈表就被創造了。在一個復雜的系統中，空閑的內存空間散落在內存各處，而鏈表通過指針很好的鏈接起了各個分散的內存空間。

如圖：

內存空間分配并不連續，但是指針稱為維系各個空間的橋梁

鏈表(linked list) 是一種線性數據結構，每個元素是一個節點對象，各個節點通過指針（或引用）相連接，指針（或引用）記錄了下一個節點的內存地址，通過它可以從當前節點訪問到下一個節點

1. 鏈表的分類

鏈表有多種結構，以下情況組合起來有$2^3$種：

1. 單項或雙向

2. 帶頭或不帶頭

3. 循環或不循環

這八種結構種，最常用的是最簡單和最復雜的兩種結構：

單鏈表（無頭單項不循環鏈表）：結構簡單，一般作為其他數據結構的子結構

雙向鏈表（帶頭雙向循環鏈表）：結構最復雜，實際使用中基本都是此結構，操作簡單

注意：我們把這個帶頭的頭稱為哨兵位，哨兵位不存儲有效數據（有些時候可能存儲鏈表節點個數），位于鏈表第一個有效節點（頭節點） 的前面。

現在我們來實現一下單鏈表和雙向鏈表

2. 單鏈表的實現

2.1 鏈表的基本結構——節點（Node）

鏈表的最小單元是節點，C++用結構體或類定義，鏈表的一個節點包含指針域和數據域，指針域保存該節點指向下一個結點的地址，數據域保存該節點的有效值。還有一個頭指針的概念：頭指針是鏈表的門把手，指向鏈表頭節點的指針變量，是鏈表的入口

// 節點結構體，存儲數據和指向下一個結點的指針
struct Node {T _value; // 數據域Node* _next; // 指針域// 節點構造函數 確保新節點創建時_next處于安全狀態Node(const T& val) : _value(val), _next(nullptr) {}
};

然后我們將節點放入類中，加入單鏈表的基本信息：頭指針、節點個數

template <typename T>
class single_list{
private:// 節點結構體，存儲數據和指向下一個結點的指針struct Node {T _value;Node* _next;// 節點構造函數 確保新節點創建時_next處于安全狀態Node(const T& val) : _value(val), _next(nullptr) {}};Node* _head; // 頭指針，指向鏈表的第一個節點size_t _count; // 節點數量
}；

我們引入類模板，能使鏈表的數據類型更多樣化，需要什么樣的類型我們就可以顯式實例化什么類型的鏈表結構

2.2 核心操作詳解

2.2.1 構造和析構

single_list() : _head(nullptr), _count(0) {}

利用初始化列表將鏈表初始化為空鏈表，方便后續操作

~single_list() { clear();}

調用清空函數刪除所有節點，該函數在下文實現

2.2.2 插入操作

1. 頭插

// 頭插 O(1)
void push_front(const T& val) {// 創建新節點Node* new_node = new Node(val);new_node->_next = _head;_head = new_node;++_count;
}

創建新的節點，新節點的指針指向原先的頭節點，然后更新頭指針的指向

2. 尾插

// 尾插 O(n)
void push_back(const T& val) {Node* new_node = new Node(val);// 如果是空鏈表 new_node就是新的頭節點if (!_head) {_head = new_node;}else {// 創建臨時變量開始找尾節點Node* cur = _head;while (cur->_next != nullptr)  cur = cur->_next;cur->_next = new_node;}++_count;
}

空鏈表要做單獨處理，新節點就是頭節點了；鏈表非空，則要創建臨時變量遍歷整個鏈表找尾，一定不能用頭指針遍歷，使用頭指針遍歷會丟失頭節點的數據

3. 指定位置插入節點

// 插入指定位置 O(n)
void insert(int pos, const T& val) {// 確保pos的合法性// pos能取到_count，取到相當于尾插assert(pos >= 0 && pos <= _count);if (pos == 0) return push_front(val);// 創建臨時變量找pos位置的節點Node* cur = _head;// 找到pos的前一個節點 cur最終指向pos-1的位置for (size_t i = 0; i < pos - 1; i++)// 循環pos - 1次{cur = cur->_next;}Node* new_node = new Node(val);new_node->_next = cur->_next;cur->_next = new_node;++_count;
}

對于用戶輸入的pos要做檢查，pos的值代表索引，從0開始。pos == 0，可以復用頭插法，而pos == _count則代表尾插，在下面的循環邏輯中，是找到pos的前一個節點，所以pos的邊界判斷都可以取到。然后更新指針指向即可

2.2.3 刪除操作

空鏈表不能執行刪除操作

1. 頭刪

// 頭刪 O(1)
void pop_front() {// 空鏈表不能刪除assert(_head);// 非空鏈表Node* tmp = _head;_head = tmp->_next;delete tmp;--_count;
}

2. 尾刪

// 尾刪 0(n)
void pop_back() {// 空鏈表不能刪除assert(_head);// 非空鏈表  先找尾節點的先驅節點// 如果只有一個節點 刪除即可if (_head->_next == nullptr) {delete _head;_head = nullptr;}else {Node* cur = _head;while (cur->_next->_next) cur = cur->_next;delete cur->_next;cur->_next = nullptr;}--_count;
}

3. 刪除指定位置節點

// 刪除指定位置
void erase(int pos) { // 確保pos合法性assert(pos >= 0 && pos < _count); // pos == 0 頭刪if (pos == 0) {pop_front();return;}Node* cur = _head;for (size_t i = 0; i < pos - 1; i++) {cur = cur->_next;}Node* tmp = cur->_next; // 保存要刪除的節點cur->_next = cur->_next->_next;delete tmp; --_count;
}

2.3.4 其他操作

size_t size() {return _count;
}bool empty() {return _count == 0;
}void clear() {while (_head) {Node* tmp = _head;_head = _head->_next;delete tmp;}_count = 0;
}void Print()
{if (!_head) { // 空鏈表處理std::cout << "nullptr" << std::endl;return;}Node* cur = _head;while (cur) { // 遍歷所有節點std::cout << cur->_value; if (cur->_next) {std::cout << "->";}cur = cur->_next;}std::cout << "->nullptr" << std::endl;
}

2.4 總結

操作	實現邏輯	時間復雜度
頭插（push_front）	新節點指向原頭節點，更新頭指針	$O(1)$
尾插（push_back）	遍歷至尾節點，將其指針指向新節點	$O(n)$
指定位置pos前插入（insert）	找到目標位置前一個節點，插入新節點	$O(n)$
頭刪（pop_front）	保存原頭節點，頭指針后移，釋放原節點	$O(1)$
尾刪（pop_back）	遍歷至尾節點前一個節點，釋放尾節點	$O(n)$
指定位置刪除（erase）	找到目標位置前一個節點，釋放目標節點	$O(n)$
清空（clear）	從頭部開始，逐個釋放所有節點	$O(n)$

• 優點：

1. 動態內存分配： 無需預先指定大小，按需分配內存
2. 頭部操作高效： 頭刪頭插都是$O(1)$
3. 插入刪除靈活： 不用像順序表一樣挪動大量數據，只需要修改指針

• 缺點：

1. 不支持隨機訪問： 訪問第n個元素需要從頭遍歷
2. 尾部操作效率低： 尾插尾刪需要遍歷到尾部
3. 指針管理復雜： 容易出現野指針、空指針問題
4. 額外內存開銷： 每個節點需要額外空間存儲指針

• 使用場景

1. 需要頻繁進行頭部插入刪除操作
2. 數量不確定，需要動態調整大小
3. 內存有限，不適合順序表使用的場景
4. 不需要隨機訪問元素

3. 雙向鏈表的實現

3.1 基本結構設計

雙向鏈表是帶頭雙向循環鏈表的簡稱，結合了三種思路：

• **雙向：**每個節點有前驅指針_prev和后繼指針_next，方便前后遍歷
• **循環：**鏈表尾節點_next指回哨兵位，哨兵位的_prev指向尾節點，整個鏈表形成一個環
• **帶頭（帶哨兵位）：**用一個特殊節點_sentinel作為表頭，不存儲有效數據，只起到占位、邊界作用

這樣做的優點是：

• 統一了插入和刪除的邏輯，不用判別頭和尾
• 空鏈表和非空鏈表的處理方式一致，封裝性更好
• 代碼更簡潔，出錯率低

我們先設計一個內部節點結構Node：

template <typename T>
struct Node {T _value;Node* _prev;Node* _next;Node(const T& val) : _value(val),_prev(nullptr),_next(nullptr){}
};

再設計鏈表類：double_list:

• _sentinel：哨兵節點，始終存在。
• _count：鏈表中有效節點的個數。

class double_list {
private:struct Node {T _value;Node* _prev;Node* _next;Node(const T& val) : _value(val),_prev(nullptr),_next(nullptr){}};Node* _sentinel; // 哨兵位size_t _count;
};

3.2 基本操作

3.2.1 初始化與銷毀

double_list() : _count(0) {// 初始化哨兵位 _prev  _next都指向自己_sentinel = new Node(T()); //不存儲有效數據_sentinel->_next = _sentinel;_sentinel->_prev = _sentinel;
}~double_list() { clear(); delete _sentinel; }

3.2.2 插入與刪除的核心邏輯

1. 在指定位置前插入

// 在pos節點前插入new_node
void insert_node(Node* pos, Node* new_node) {// 先確定好new_node的位置new_node->_prev = pos->_prev;new_node->_next = pos;// 這里順序不能反了pos->_prev->_next = new_node;pos->_prev = new_node;++_count;
}

處理指針指向順序不能顛倒，要先考慮原有節點存在，這里詳細講一下，后續不再贅述。

對任意相鄰三點 A <-> B <-> C：

• A->_next == B
• B->_prev == A
• B->_next == C
• C->_prev == B

做插入/刪除時，不要提前破壞老的不變量，要么先把新節點“準備好”，要么先把“鄰居接好”，保證任何時刻都能從 S 沿 _next 或 _prev 找回環，不會丟失鏈。所以，在 pos 前插入 new_node 的正確順序為：設：B = pos A = B->_prev

安全順序（推薦）：

1. 先給新節點“自報家門”（只寫新節點，不動舊鏈）

   new_node->_prev = A;
   new_node->_next = B;
   

2. 再接左邊的_next

   A->_next = new_node;
   

3. 最后接右邊的_prev

   B->_prev = new_node;
   

這套順序的邏輯是：

• 第1步只動 new_node，不破壞原有結構；
• 第2步把 A 指向新節點，此時從左側走到 new_node 沒問題；
• 第3步把 B 的前驅改為新節點，完成閉合；
• 全程不會出現“鏈斷掉一截找不回來的窗口期”。

為什么不能顛倒？一個典型反例：

// ? 先改 B->_prev，再去用 pos->_prev
B->_prev = new_node;
B->_prev->_next = new_node; // 此時 B->_prev 已是 new_node，這行等價 new_node->_next = new_node，鏈炸

如果沒有緩存 A（而是反復寫 pos->_prev），一旦你先把 B->_prev 改成了 new_node，再通過 pos->_prev 想找到老的 A 就晚了——你拿到的是 new_node，從而把 new_node->_next 錯誤地指向 new_node 自己，造成環路破壞。

結論：如果你不緩存 A，就必須按先寫 new_node 的 _prev/_next，再寫 A->_next，最后寫 B->_prev的順序。
如果你緩存了：Node* A = B->_prev;，則可以適當調換 2、3 兩步的先后（先改 B->_prev 或先改 A->_next 都行），因為 A 已經固定，不會丟。

2. 刪除指定節點

// 刪除指定節點
void erase_node(Node* pos) {pos->_prev->_next = pos->_next;pos->_next->_prev = pos->_prev;delete pos;--_count;
}

還是用這條鏈路舉例子：A <-> B <-> C

設：B = pos A = B->_prev C = B->_next

安全順序（必須這樣）：

1. 先把鄰居接好，繞過 B

   A->_next = C;
   C->_prev = A;
   

2. 再釋放 B

   delete B;
   

為什么？

• 如果你先 delete B，隨后再去訪問 B->_prev 或 B->_next 來接回鄰居，就會解引用野指針，是未定義行為。
• 先把 A 和 C 直接連起來，保證環不斷；最后才安全釋放 B。

常見錯誤：

delete B;              // ? 提前釋放
A->_next = B->_next;   // 立刻野指針解引用

有了這兩個基礎操作，頭插、尾插、頭刪、尾刪都能用它們實現。所以這兩個操作可以封裝到private中，僅供類自己使用。

3.2.3 常用操作

1. 頭插&尾插

// 頭插 在哨兵位后插入
void push_front(const T& val) {insert_node(_sentinel->_next, new Node(val));
}// 尾插 在哨兵位前插入
void push_back(const T& val) {insert_node(_sentinel, new Node(val));  
}

2. 頭刪&尾刪

// 頭刪 哨兵位的next
void pop_front() {if(empty()) throw std::out_of_range("List empty");erase_node(_sentinel->_next);
}// 尾刪 哨兵位的prev
void pop_back() {if (empty()) throw std::out_of_range("List empty");erase_node(_sentinel->_prev);
}

3. 訪問指定位置

// 訪問指定位置節點 用索引
T& at(int pos) {if(pos < 0 || pos >= _count) throw std::out_of_range("Index out of range");//創建臨時節點訪問鏈表// 哨兵位的next索引是0Node* cur = _sentinel->_next;for (size_t i = 0; i < pos; i++){cur = cur->_next;}return cur->_value;}

4. 指定位置插入&刪除

// 在pos位置節點前插入新節點
void insert(int pos, const T& val) {if(pos < 0 || pos > _count) throw std::out_of_range("Insert position out of range");// 要在pos前插入 就從哨兵位走Node* cur = _sentinel;for (size_t i = 0; i < pos; i++){cur = cur->_next;}insert_node(cur, new Node(val));}// 刪除pos位置的節點
void erase(int pos) {if(pos < 0 || pos >= _count) throw std::out_of_range("Erase position out of range");// 找pos位置 從索引為零的位置開始Node* cur = _sentinel->_next;for (size_t i = 0; i < pos; i++){cur = cur->_next;}erase_node(cur);
}

3.3 其他輔助函數

打印鏈表

void Print() {std::cout << "_sentinel->";Node* cur = _sentinel->_next;while (cur != _sentinel) {std::cout << cur->_value << "->";cur = cur->_next;}std::cout << "_sentinel" << std::endl;
}

清空鏈表

// 清空鏈表 保留哨兵位
void clear() {Node* cur = _sentinel->_next;while (cur != _sentinel) {Node* tmp = cur;cur = cur->_next;delete tmp;}_sentinel->_next = _sentinel;_sentinel->_prev = _sentinel;_count = 0;
}

判斷鏈表是否為空

bool empty() const { return _count == 0; }

返回鏈表長度

size_t size() const { return _count; }

3.4 總結

操作	說明	時間復雜度
push_front(val)	頭插，在哨兵后插入新節點	$O(1)$
push_back(val)	尾插，在哨兵前插入新節點	$O(1)$
insert(pos, val)	在第 pos 個位置前插入新節點（需遍歷到 pos）	$O(n)$
insert_node	已知節點 pos 前插入 new_node，只改指針	$O(1)$
pop_front()	頭刪，刪除第一個節點	$O(1)$
pop_back()	尾刪，刪除最后一個節點	$O(1)$
erase(pos)	刪除第 pos 個節點（需遍歷到 pos）	$O(n)$
erase_node	刪除已知節點指針	$O(1)$
at(pos)	按索引訪問第 pos 個節點	$O(n)$

• 優點

1. 帶哨兵節點：_sentinel 作為頭尾的“標志”，統一了邊界條件，避免空鏈表、頭刪、尾刪的特殊情況。
2. 循環結構： 遍歷時不用判斷 nullptr，走到 _sentinel 就說明一圈結束。
3. 雙向鏈表： 已知某個節點指針時，刪除/插入只需改前后兩個指針，操作 $O(1)$。
4. 動態存儲： 不需要連續內存，比數組更靈活。

• 缺點

1. 訪問效率低：at、insert、erase 都需要順序遍歷， $O(n)$。
2. 額外空間開銷大 每個節點需要兩個指針 _prev 和 _next，比單鏈表開銷更高。
3. 實現復雜： 插入/刪除時要維護兩個方向的指針，順序稍有不慎就會出現 bug（比如斷鏈、死循環）。

4. 與順序表對比

4.1 時間復雜度對比

操作	數組 (順序表)	單向鏈表	雙向循環鏈表（帶頭）
按下標訪問	$O(1)$	$O(n)$	$O(n)$
按值查找	$O(n)$	$O(n)$	$O(n)$
頭插	$O(n)$（需要整體移動）	$O(1)$	$O(1)$
尾插問	$O(1)$（有容量時）	$O(1)$	$O(1)$
中間插入	$O(n)$（移動元素）	$O(n)$（遍歷到位置）	$O(n)$（遍歷到位置）
頭刪	$O(n)$（整體移動）	$O(1)$	$O(1)$
尾刪問	$O(1)$	$O(n)$（需找前驅）	$O(1)$
刪除已知節點指針	O(1)（僅數組下標已知時）	$O(n)$（需找前驅）	$O(1)$
空間使用	連續空間，高效	每節點額外 1 個指針	每節點額外 2 個指針
遍歷	$O(n)$	$O(n)$	$O(n)$

4.2優缺點總結

順序表

• 優點：支持隨機訪問 $O(1)$，內存利用率高，局部性好。
• 缺點：插入/刪除開銷大（需要整體移動），容量固定或擴容開銷高。
• 適用場景：頻繁訪問、較少插入刪除。

單鏈表

• 優點：插入/刪除高效，內存分配靈活。
• 缺點：不能快速找到前驅，刪除已知節點需 $O(n)$，訪問慢。
• 適用場景：需要頻繁插入/刪除，但多在鏈表頭部操作。

雙向鏈表(帶頭循環)

• 優點：
  • 插入/刪除效率高，尤其是頭尾操作 $O(1)$。
  • 已知節點指針時，刪除/插入 $O(1)$。
  • 帶頭哨兵，邏輯統一，不需要處理特殊情況。
• 缺點：
  • 空間開銷更大，每節點要兩個指針。
  • 隨機訪問仍是 $O(n)$。
  • 實現復雜，指針操作容易出錯。
• 適用場景：需要頻繁在任意位置插入/刪除的場景