鏈表

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

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

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

圖 4-5   鏈表定義與存儲(chǔ)方式

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

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

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

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

鏈表常用操作

1.   初始化鏈表

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

linked_list.cpp

/* 初始化鏈表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個(gè)節(jié)點(diǎn)
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ù)組整體是一個(gè)變量，比如數(shù)組 nums 包含元素 nums[0] 和 nums[1] 等，而鏈表是由多個(gè)獨(dú)立的節(jié)點(diǎn)對(duì)象組成的。我們通常將頭節(jié)點(diǎn)當(dāng)作鏈表的代稱(chēng)，比如以上代碼中的鏈表可被記做鏈表 n0 。

2.   插入節(jié)點(diǎn)

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

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

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

linked_list.cpp

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

3.   刪除節(jié)點(diǎn)

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

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

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

linked_list.cpp

/* 刪除鏈表的節(jié)點(diǎn) n0 之后的首個(gè)節(jié)點(diǎn) */
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.   訪(fǎng)問(wèn)節(jié)點(diǎn)

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

linked_list.cpp

/* 訪(fǎng)問(wèn)鏈表中索引為 index 的節(jié)點(diǎn) */
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é)點(diǎn)

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

linked_list.cpp

/* 在鏈表中查找值為 target 的首個(gè)節(jié)點(diǎn) */
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é)對(duì)比了數(shù)組和鏈表的各項(xiàng)特點(diǎn)與操作效率。由于它們采用兩種相反的存儲(chǔ)策略，因此各種性質(zhì)和操作效率也呈現(xiàn)對(duì)立的特點(diǎn)。

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

4.2.3   常見(jiàn)鏈表類(lèi)型

如圖 4-8 所示，常見(jiàn)的鏈表類(lèi)型包括三種。

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

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

圖 4-8   常見(jiàn)鏈表種類(lèi)

鏈表典型應(yīng)用

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

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

雙向鏈表常被用于需要快速查找前一個(gè)和下一個(gè)元素的場(chǎng)景。

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

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

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