鏈表

內(nèi)存空間是所有程序的公共資源，在一個復(fù)雜的系統(tǒng)運行環(huán)境下，空閑的內(nèi)存空間可能散落在內(nèi)存各處。我們知道，存儲數(shù)組的內(nèi)存空間必須是連續(xù)的，而當數(shù)組非常大時，內(nèi)存可能無法提供如此大的連續(xù)空間。此時鏈表的靈活性優(yōu)勢就體現(xiàn)出來了。

「鏈表 linked list」是一種線性數(shù)據(jù)結(jié)構(gòu)，其中的每個元素都是一個節(jié)點對象，各個節(jié)點通過“引用”相連接。引用記錄了下一個節(jié)點的內(nèi)存地址，通過它可以從當前節(jié)點訪問到下一個節(jié)點。

鏈表的設(shè)計使得各個節(jié)點可以被分散存儲在內(nèi)存各處，它們的內(nèi)存地址是無須連續(xù)的。

圖 4-5   鏈表定義與存儲方式

觀察圖 4-5 ，鏈表的組成單位是「節(jié)點 node」對象。每個節(jié)點都包含兩項數(shù)據(jù)：節(jié)點的“值”和指向下一節(jié)點的“引用”。

• 鏈表的首個節(jié)點被稱為“頭節(jié)點”，最后一個節(jié)點被稱為“尾節(jié)點”。
• 尾節(jié)點指向的是“空”，它在 Java、C++ 和 Python 中分別被記為 null、nullptr 和 None 。
• 在 C、C++、Go 和 Rust 等支持指針的語言中，上述的“引用”應(yīng)被替換為“指針”。

如以下代碼所示，鏈表節(jié)點 ListNode 除了包含值，還需額外保存一個引用（指針）。因此在相同數(shù)據(jù)量下，鏈表比數(shù)組占用更多的內(nèi)存空間。

/* 鏈表節(jié)點結(jié)構(gòu)體 */
struct ListNode {
    int val;         // 節(jié)點值
    ListNode *next;  // 指向下一節(jié)點的指針
    ListNode(int x) : val(x), next(nullptr) {}  // 構(gòu)造函數(shù)
};

鏈表常用操作

1.   初始化鏈表

建立鏈表分為兩步，第一步是初始化各個節(jié)點對象，第二步是構(gòu)建引用指向關(guān)系。初始化完成后，我們就可以從鏈表的頭節(jié)點出發(fā)，通過引用指向 next 依次訪問所有節(jié)點。

linked_list.cpp

/* 初始化鏈表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節(jié)點
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// 構(gòu)建引用指向
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

數(shù)組整體是一個變量，比如數(shù)組 nums 包含元素 nums[0] 和 nums[1] 等，而鏈表是由多個獨立的節(jié)點對象組成的。我們通常將頭節(jié)點當作鏈表的代稱，比如以上代碼中的鏈表可被記做鏈表 n0 。

2.   插入節(jié)點

在鏈表中插入節(jié)點非常容易。如圖 4-6 所示，假設(shè)我們想在相鄰的兩個節(jié)點 n0 和 n1 之間插入一個新節(jié)點 P ，則只需要改變兩個節(jié)點引用（指針）即可，時間復(fù)雜度為 O(1) 。

相比之下，在數(shù)組中插入元素的時間復(fù)雜度為 O(n) ，在大數(shù)據(jù)量下的效率較低。

圖 4-6   鏈表插入節(jié)點示例

linked_list.cpp

/* 在鏈表的節(jié)點 n0 之后插入節(jié)點 P */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

3.   刪除節(jié)點

如圖 4-7 所示，在鏈表中刪除節(jié)點也非常方便，只需改變一個節(jié)點的引用（指針）即可。

請注意，盡管在刪除操作完成后節(jié)點 P 仍然指向 n1 ，但實際上遍歷此鏈表已經(jīng)無法訪問到 P ，這意味著 P 已經(jīng)不再屬于該鏈表了。

圖 4-7   鏈表刪除節(jié)點

linked_list.cpp

/* 刪除鏈表的節(jié)點 n0 之后的首個節(jié)點 */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 釋放內(nèi)存
    delete P;
}

4.   訪問節(jié)點

在鏈表訪問節(jié)點的效率較低。如上節(jié)所述，我們可以在 O(1) 時間下訪問數(shù)組中的任意元素。鏈表則不然，程序需要從頭節(jié)點出發(fā)，逐個向后遍歷，直至找到目標節(jié)點。也就是說，訪問鏈表的第 i 個節(jié)點需要循環(huán) i?1 輪，時間復(fù)雜度為 O(n) 。

linked_list.cpp

/* 訪問鏈表中索引為 index 的節(jié)點 */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}

5.   查找節(jié)點

遍歷鏈表，查找鏈表內(nèi)值為 ?target? 的節(jié)點，輸出節(jié)點在鏈表中的索引。此過程也屬于線性查找。

linked_list.cpp

/* 在鏈表中查找值為 target 的首個節(jié)點 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

 數(shù)組 VS 鏈表

表 4-1 總結(jié)對比了數(shù)組和鏈表的各項特點與操作效率。由于它們采用兩種相反的存儲策略，因此各種性質(zhì)和操作效率也呈現(xiàn)對立的特點。

表 4-1   數(shù)組與鏈表的效率對比

4.2.3   常見鏈表類型

如圖 4-8 所示，常見的鏈表類型包括三種。

• 單向鏈表：即上述介紹的普通鏈表。單向鏈表的節(jié)點包含值和指向下一節(jié)點的引用兩項數(shù)據(jù)。我們將首個節(jié)點稱為頭節(jié)點，將最后一個節(jié)點稱為尾節(jié)點，尾節(jié)點指向空 None 。
• 環(huán)形鏈表：如果我們令單向鏈表的尾節(jié)點指向頭節(jié)點（即首尾相接），則得到一個環(huán)形鏈表。在環(huán)形鏈表中，任意節(jié)點都可以視作頭節(jié)點。
• 雙向鏈表：與單向鏈表相比，雙向鏈表記錄了兩個方向的引用。雙向鏈表的節(jié)點定義同時包含指向后繼節(jié)點（下一個節(jié)點）和前驅(qū)節(jié)點（上一個節(jié)點）的引用（指針）。相較于單向鏈表，雙向鏈表更具靈活性，可以朝兩個方向遍歷鏈表，但相應(yīng)地也需要占用更多的內(nèi)存空間。

/* 雙向鏈表節(jié)點結(jié)構(gòu)體 */
struct ListNode {
    int val;         // 節(jié)點值
    ListNode *next;  // 指向后繼節(jié)點的指針
    ListNode *prev;  // 指向前驅(qū)節(jié)點的指針
    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // 構(gòu)造函數(shù)
};

圖 4-8   常見鏈表種類

鏈表典型應(yīng)用

單向鏈表通常用于實現(xiàn)棧、隊列、哈希表和圖等數(shù)據(jù)結(jié)構(gòu)。

• 棧與隊列：當插入和刪除操作都在鏈表的一端進行時，它表現(xiàn)出先進后出的的特性，對應(yīng)棧；當插入操作在鏈表的一端進行，刪除操作在鏈表的另一端進行，它表現(xiàn)出先進先出的特性，對應(yīng)隊列。
• 哈希表：鏈地址法是解決哈希沖突的主流方案之一，在該方案中，所有沖突的元素都會被放到一個鏈表中。
• 圖：鄰接表是表示圖的一種常用方式，在其中，圖的每個頂點都與一個鏈表相關(guān)聯(lián)，鏈表中的每個元素都代表與該頂點相連的其他頂點。

雙向鏈表常被用于需要快速查找前一個和下一個元素的場景。

• 高級數(shù)據(jù)結(jié)構(gòu)：比如在紅黑樹、B 樹中，我們需要訪問節(jié)點的父節(jié)點，這可以通過在節(jié)點中保存一個指向父節(jié)點的引用來實現(xiàn)，類似于雙向鏈表。
• 瀏覽器歷史：在網(wǎng)頁瀏覽器中，當用戶點擊前進或后退按鈕時，瀏覽器需要知道用戶訪問過的前一個和后一個網(wǎng)頁。雙向鏈表的特性使得這種操作變得簡單。
• LRU 算法：在緩存淘汰算法（LRU）中，我們需要快速找到最近最少使用的數(shù)據(jù)，以及支持快速地添加和刪除節(jié)點。這時候使用雙向鏈表就非常合適。

循環(huán)鏈表常被用于需要周期性操作的場景，比如操作系統(tǒng)的資源調(diào)度。

• 時間片輪轉(zhuǎn)調(diào)度算法：在操作系統(tǒng)中，時間片輪轉(zhuǎn)調(diào)度算法是一種常見的 CPU 調(diào)度算法，它需要對一組進程進行循環(huán)。每個進程被賦予一個時間片，當時間片用完時，CPU 將切換到下一個進程。這種循環(huán)的操作就可以通過循環(huán)鏈表來實現(xiàn)。
• 數(shù)據(jù)緩沖區(qū)：在某些數(shù)據(jù)緩沖區(qū)的實現(xiàn)中，也可能會使用到循環(huán)鏈表。比如在音頻、視頻播放器中，數(shù)據(jù)流可能會被分成多個緩沖塊并放入一個循環(huán)鏈表，以便實現(xiàn)無縫播放。