詳解|寫完這篇文章我終於搞懂鏈表了

• 2021 年 3 月 10 日
• 筆記
• 數據結構和算法

一覽：本文從零介紹鏈式存儲結構的線性表——單鏈表。包括以下內容：

• 什麼是鏈式存儲存儲結構？
• 單鏈表的結構
• 辨析頭結點、頭指針等易混淆概念
• 基本的增刪改查操作（不帶頭結點和帶頭結點）
• 單鏈表與順序表的對比

線性表的鏈式存儲結構

在【順序表詳解】一文中我們介紹了一種「用曲線連接」的線性表，「曲線」是一種形象化的語言，實際上並不會存在所謂「曲線」的這種東西。

所謂「曲線連接」即鏈式存儲，那什麼是鏈式存儲呢？

在【順序表詳解】一文中介紹順序存儲結構時舉了一個例子：

比如，一群孩子肩並肩地站成一排，佔據一定的連續土地。這群孩子的隊伍非常整齊劃一。

這個例子反映在內存中，即為順序存儲結構。

現在孩子們覺得肩並肩站隊太過於約束，於是便散開了，想站在哪裡就站在哪裡，但是隊伍不能中斷啊。所以他們便手拉着手來保持隊伍不斷開。

現在孩子們佔據的不是連續的土地了，而是任意的某塊土地。

這個例子反映在內存中，就是數據元素任意出現，佔據某塊內存。

上面兩張圖放在一塊對比，就可以看出問題了：

• 直線 VS 曲線
• 整齊劃一 VS 雜亂無章
• 連續內存空間 VS 任意內存空間
• 順序存儲 VS 鏈式存儲

在【順序表詳解】一文中提到過，線性表的特點之一是元素之間有順序。順序存儲結構靠連續的內存空間來實現這種「順序」，但鏈式存儲結構的元素是「任意的」，如何實現「順序」呢？

「任意」和「順序」乍一看很像反義詞，但並不矛盾。小孩子們為了不讓隊伍中斷便「手拉手」，我們要實現「順序」，就靠那根「像鏈條一樣的曲線」來把元素鏈接起來，這樣就有了順序。

這就是鏈式存儲。

在【順序表詳解】一文中提到過「順序存儲結構是使用一段連續的內存單元分別存儲線性表中的數據的數據結構」。我們照貓畫虎，就可以得到「鏈式存儲結構是使用一組任意的、不連續的內存單元來分別存儲線性表中的數據的數據結構」的結論。

那我偏就使用連續的內存單元來存數據，可不可以？當然可以。

下圖直觀地畫出了線性表的元素以鏈式存儲的方式存儲在內存中。

為了方便畫圖，我們將表示順序的曲線人為地拉直，將任意存儲的元素人為地排列整齊，形成下圖中的邏輯關係：

這種鏈式存儲結構的線性表，簡稱為鏈表。

上圖的鏈表之間用一個單向箭頭相連，從一個指向另一個，這樣整個鏈表就有了一個方向，我們稱之為單鏈表。

總結一下特點：

1. 用一組任意的存儲單元來存儲線性表的數據元素，這組存儲單元可以是連續的（1和3），也可以是不連續的；
2. 這組任意的存儲單元用「一根鏈子」串起來，所以雖然在內存上是亂序的，但是在邏輯上卻仍然是線性的；
3. 單鏈表的方向是單向的，只能從前往後，不能從後往前；

單鏈表的實現思路

因為單鏈表是任意的內存位置，所以數組肯定不能用了。

因為要存儲一個值，所以直接用變量就行。

因為單鏈表在物理內存上是任意存儲的，所以表示順序的箭頭（小孩子的手臂）必須要用代碼實現出來。

而箭頭的含義就是，通過 1 能找到 2。

又因為我們使用變量來存儲值，所以，換句話說，我們要通過一個變量找到另一個變量。

變量找變量？怎麼做到？

C 語言剛好有這個機制——指針。如果你對指針還不清楚，可以移步到文章【如何掌握 C 語言的一大利器——指針？】。

現在萬事俱備，只差結合。

一個變量用來存值，一個指針用來存其直接後繼的地址，把變量和指針綁在一塊構成一個數據元素，啪的一下，就成了。

由於指針中存了其直接後繼的地址，這就相當於用一個有向箭頭指向了其直接後繼。

先明確幾個名詞：

• 用來存數據的變量叫做數據域
• 用來存「直接後繼元素的地址」的 指針 叫做指針域
• 數據域和指針域構成的數據元素叫做 結點 (node)

總結一下，一個單鏈表 (SinglyLinkedList) 的結點 (Node) 由以下幾部分組成：

• 用來存數據的數據域——data
• 用來存直接後繼結點的的地址的指針域——next

結點的具體實現

可以使用 C 語言的結構體來實現結點：

為了說明問題簡單，我們這裡的結點只存儲整數。

//結點
typedef struct Node {
    int data; //數據域：存儲數據
    struct Node *next; //指針域：存儲直接後繼結點的地址
} Node;

這樣的一個結構體就能完美地表示一個結點了，許多結點連在一塊就能構成鏈表了。

單鏈表的結構

單鏈表由若干的結點單向鏈接組成，一個單鏈表必須要有頭有尾，因為計算機很「笨」，不像人看一眼就知道頭在哪尾在哪。所以我們要用代碼清晰地表示出一個單鏈表的所有結構。

頭指針

請先注意 「頭」 這個概念，我們在日常生活中拿繩子的時候，總喜歡找「繩子頭」，此「頭」即彼「頭」。

然後再理解 「指針」 這個概念（如不清楚指針，請移步至請移步至文章【如何掌握 C 語言的一大利器——指針？】），指針裏面存儲的是地址。

那麼，頭指針即存儲鏈表的第一個結點的內存地址的指針，也即頭指針指向鏈表的第一個結點。

下圖是一個由三個結點構成的單鏈表：

（為了方便理解鏈表的結構，我會給出每個結點的地址以及指針域的值）

指針 head 中保存了第一個結點 1 的地址，head 即為頭指針。有了頭指針，我們就可以找到第一個結點的位置，就可以找到整個鏈表。通常，頭指針的名字就是鏈表的名字。

即，head（頭指針）在手，鏈表我有。

值為 3 的結點是該鏈表的「尾」，所以它的指針域中保存的值為 NULL，用來表示整個鏈表到此為止。

我們用頭指針表示鏈表的開始，用 NULL 表示鏈表的結束。

頭結點

在上面的鏈表中，我們可以在值為 1 的結點前再加一個結點，稱其為頭結點。見下圖：

頭結點的指針域中一般不存放數據（可以存放如結點數等無關緊要的數據），從這點看，頭結點是不同於其他結點的「假結點」。

此時頭指針指向頭結點，因為現在頭結點才是第一個結點。

為什麼要設立頭結點呢？這可以方便我們對鏈表的操作，後面你將會體會到這一點。

當然，頭結點不是鏈表的必要結構之一，他可有可無，僅憑你的喜好。

有無頭結點的單鏈表

既然頭結點不是鏈表的必要結構，這就意味着可以有兩種鏈表：

• 帶頭結點的單鏈表
• 不帶頭結點的單鏈表

再加上頭指針，初學鏈表時，「我們的頭」很容易被「鏈表的頭」搞暈。

別暈，看下面兩幅圖：

記住以下幾條：

• 頭指針很重要，沒它不行。
• 雖然頭結點可以方便我們的一些操作，但是有沒有都行。
• 無論帶頭結點與否，頭指針都指向鏈表的第一個結點。

（後面的操作我們將討論不帶頭結點和帶頭結點兩種情況）

空鏈表

不帶頭結點

下圖是一個不帶頭結點的空鏈表：

即頭指針中存儲的地址為 NULL。

帶頭結點

下圖是一個帶頭結點的空鏈表：

此時頭指針中存儲的是第一個結點——頭結點的地址，頭結點的指針域中存儲的是 NULL 。

（後面的圖示將不再給出內存地址）

創造結點

至此，關於單鏈表的基本概念、實現思路、結點的具體實現我們都已經了解了，但這些還都停留我們的腦子裡。下面要做的就是把我們腦子裡的東西，以內存喜聞樂見的形式搬到內存中去。

因為鏈表是由結點組成的，所以我們先來創造結點。

/**
 * 創造結點，返回指向該結點的指針
 * elem : 結點的數據域的值
 * return : 指向該結點的指針（該結點的地址）
 */
Node *create_node(int elem)
{
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = elem;
    node->next = NULL;
    return node;
}

注意：我們要使用 malloc 函數給結點申請一塊內存，然後才能對該結點的數據域進行賦值，而由於該結點此時是一個獨立的結點，沒有直接後繼結點，所以其指針域為 NULL。

初始化鏈表

初始化鏈表即初始化一個空鏈表，詳見本文【空鏈表】一節中的兩幅圖。

不帶頭結點

要初始化一個不帶頭節點的鏈表，我們直接創建一個可以指向結點的空指針即可，該空指針即為頭指針：

Node *head = NULL;

帶頭結點

帶頭結點的單鏈表的特點是多了一個不存儲數據的頭結點，所以我們初始化鏈表時，要將其創建出來。

但是在創建之前，我們先來搞清楚三個問題，分別是：

1. 鏈表的頭指針

2. 指向【指向結點的指針】的指針

3. 函數參數的值傳遞和地址傳遞

簡單解釋：

1. 頭指針是鏈表一定要有的，找到頭指針才能找到整個鏈表，否則整個鏈表就消失在「茫茫內存」之中了。所以無論進行何種操作，頭指針一定要像我們攥緊繩子頭一樣「被攥在我們手中」。
2. 指針中保存了別人的地址，它也有自己地址。如果一個指針中保存了別的指針的地址，該指針就是「指向指針的指針」。因為頭指針是指向鏈表第一個結點的指針，所以我們找到頭指針也就找到了整個鏈表（這句話啰嗦太多遍了）。而為了能找到頭指針，我們就需要知道頭指針的地址，也即將頭指針的地址保存下來，換句話說，用一個指針來指向頭指針。
3. 函數的值傳遞改變的是形參（實參的一份拷貝），影響不了實參。所以在一些情況下，我們需要傳給函數的是地址，函數使用指針來直接操作該指針指向的內存。

如果以上內容還不清楚，說明對指針的掌握還不夠熟練，請移步至文章【如何掌握 C 語言的一大利器——指針？】。

下面畫一張比較形象的圖：

上圖中頭指針和鏈表像不像一根帶手柄的鞭子？

比如下面這個我小時候經常玩的遊戲

/**
 * 初始化鏈表
 * p_head: 指向頭指針的指針
 */
void init(Node **p_head)
{
    //創建頭結點
    Node *node = (Node *) malloc(sizeof(Node));
    node->next = NULL;
    //頭指針指向頭結點
    *p_head = node;
}

遍歷操作

所謂遍歷，就是從鏈表頭開始，向鏈表尾一個一個結點進行遍歷，我們通常藉助一個輔助指針來進行遍歷。

不帶頭結點

不帶頭結點的鏈表從頭指針開始遍歷，所以輔助指針的初始位置就是頭指針，這裡我們以獲取鏈表的長度為例：

int get_length(Node *head)
{
    int length = 0;
    Node *p = head;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

使用 for 循環能使代碼看起來更精簡些。

帶頭結點

帶頭結點的鏈表需要從頭結點開始遍歷，所以輔助指針的初始位置是頭結點的後繼結點：

int get_length(Node *head)
{
    int length = 0;
    Node *p = head->next;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

插入操作

基本思想

我們在前面舉了「小孩子手拉手」這個例子來描述單鏈表。

孩子 A 和 B 手拉手鏈接在一起，現在有個孩子 C 想要插到他們之間，怎麼做？

C 拉上 B 的手 => A 鬆開 B 的手（虛線表示鬆開） => A 拉上 C 的手

A 鬆開 B 的手 => A 拉上 C 的手 => C 拉上 B 的手

同樣地，在鏈表中，我們也是類似的操作：

寫成代碼就是：

new->next = current;
previous->next = new;

或這換一下順序：

previous->next = new;
new->next = current;

這兩句就是插入操作的核心代碼，也是各種情況下插入操作的不變之處，搞明白這兩句，就可以以不變應萬變了。

其中 previous 、 current 和 new 是三個指向結點的指針， new 指向要插入的結點， previous 、 current 一前一後，在進行插入操作之前的關係為：

current = previous->next;

事實上， current 指針不是必需的，只有一個 previous 也可以做到插入操作，原因就是 current = previous->next，這種情況下的核心代碼變為：

new->next = previous->next;
previous->next = new;

但請注意，在這種情況下兩句代碼是有順序的，你不能寫成：

// 錯誤代碼
previous->next = new;
new->next = previous->next;

我們可以從兩個角度來理解為什麼這兩句會有順序：

【角度一】

因為 current 指針的作用就是用來保存 previous 的直接後繼結點的地址的，所以在我們斷開 previous 和 current 聯繫後，我們仍能找到 current 及其以後的結點。「鏈子」就算暫時斷開了，由於斷開處兩側都有標記，我們也能接上去。。

但是現在沒了 current 之後，一旦斷開， current 及其以後的結點就消失在茫茫內存中，這就關鍵時刻掉鏈子了。

所以我們要先把 new 和 previous->next（ previous 的直接後繼結點）連起來，這樣一來，指針 new 就保存了它所指向的及其以後的結點，

【角度二】

直接看代碼，previous->next = new 執行完後 new->next = previous->next 就相當於 new->next = new ，自己指自己，這顯然不正確。

總之，把核心代碼理解到位，剩下的就在於如何準確的找到 previous 和 current 的位置。

指定位置插入

不帶頭結點

我們需要考慮兩種情況：

1. 在第一個元素前插入
2. 在其他元素前插入

/**
 * 指定插入位置
 * p_head: 指向頭指針的指針
 * position: 指定位置 (1 <= position <= length + 1)
 * elem: 新結點的數據
 */ 
void insert(Node **p_head, int position, int elem)
{
    Node *new = create_node(elem);
    Node *current = *p_head;
    Node *previous = NULL;
    int length = get_length(*p_head);
    if (position < 1 || position > length + 1) {
        printf("插入位置不合法\n");
        return;
    }
    for (int i = 0; current != NULL && i < position - 1; i++) {
        previous = current;
        current = current->next;
    }
    new->next = current;
    if (previous == NULL)
        *p_head = new;
    else
        previous->next = new;
}

帶頭結點

由於帶了一個頭結點，所以在第一個元素前插入和在其他元素前插入時的操作是相同的。

/**
 * 指定插入位置
 * p_head: 指向頭指針的指針
 * position: 指定位置 (1 <= position <= length + 1)
 * elem: 新結點的數據
 */
void insert(Node **p_head, int position, int elem)
{
    Node *new = create_node(elem);
    Node *previous = *p_head;
    Node *current = previous->next;
    int length = get_length(*p_head);
    if (position < 1 || position > length + 1) {
        printf("插入位置不合法\n");
        return;
    }
    for (int i = 0; current != NULL && i < position - 1; i++) {
        previous = current;
        current = current->next;
    }
    new->next = current;
    previous->next = new;
}

頭插法

不帶頭結點

不帶頭結點的頭插法，即新插入的節點始終被頭指針所指向。

/**
 * 頭插法：新插入的節點始終被頭指針所指向
 * p_head: 指向頭指針的指針
 * elem: 新結點的數據
 */
void insert_at_head(Node **p_head, int elem)
{
    Node *new = create_node(elem);
    new->next = *p_head;
    *p_head = new;
}

帶頭結點

帶頭結點的頭插法，即新插入的結點始終為頭結點的直接後繼。

/**
 * 頭插法，新結點為頭結點的直接後繼
 * p_head: 指向頭指針的指針
 * elem: 新結點的數據
 */
void insert_at_head(Node **p_head, int elem)
{
    Node *new = create_node(elem);
    new->next = (*p_head)->next;
    (*p_head)->next = new;
}

注意：多了一個頭結點，所以代碼有所變化。

尾插法

尾插法要求我們先找到鏈表的最後一個結點，所以重點在於如何遍歷到最後一個結點。

不帶頭結點

/**
 * 尾插法：新插入的結點始終在鏈表尾
 * p_head: 指向頭指針的指針
 * elem: 新結點的數據
 */
void insert_at_tail(Node **p_head, int elem)
{
    Node *new = create_node(elem);
    Node *p = *p_head;
    while (p->next != NULL)   //從頭遍歷至鏈表尾
        p = p->next;
    p->next = new;
}

帶頭結點

/**
 * 尾插法：新插入的結點始終在鏈表尾
 * p_head: 指向頭指針的指針
 * elem: 新結點的數據
 */
void insert_at_tail(Node **p_head, int elem)
{
    Node *new = create_node(elem);
    Node *p = (*p_head)->next;
    while (p->next != NULL)
        p = p->next;
    p->next = new;
}

刪除操作

基本思想

刪除操作是將要刪除的結點從鏈表中剔除，和插入操作類似。

previous 和 current 為指向結點的指針，現在我們要刪除結點 current，過程如下：

核心代碼為：

previous->next = current->next;
free(current);

free() 操作將要刪除的結點給釋放掉。

current 指針不是必需的，沒有它也可以，代碼寫成這樣：

previous->next = previous->next->next;

但此時我們已經不能釋放要刪除的那個結點了，因為我們沒有一個指向它的指針，它已經消失在茫茫內存中了。

指定位置刪除

知道了核心代碼，剩下的工作就在於我們如何能夠正確地遍歷到要刪除的那個結點。

如你所見，previous 指針是必需的，且一定是要刪除的那個結點的直接前驅，所以要將 previous 指針遍歷至其直接前驅結點。

不帶頭結點

/**
 * 刪除指定位置的結點
 * p_head: 指向頭指針的指針
 * position: 指定位置 (1 <= position <= length + 1)
 * elem: 使用該指針指向的變量接收刪除的值
 */
void delete(Node **p_head, int position, int *elem)
{
    Node *previous = NULL;
    Node *current = *p_head;
    int length = get_length(*p_head);
    if (length == 0) {
        printf("空鏈表\n");
        return;
    }
    if (position < 1 || position > length) {
        printf("刪除位置不合法\n");
        return;
    }
    for (int i = 0; current->next != NULL && i < position - 1; i++) {
        previous = current;
        current = current->next;
    }
    *elem = current->data;
    if (previous == NULL)
        *p_head = (*p_head)->next;
    else
        previous->next = current->next;
    free(current);
}

帶頭結點

/**
 * 刪除指定位置的結點
 * p_head: 指向頭指針的指針
 * position: 指定位置 (1 <= position <= length + 1)
 * elem: 使用該指針指向的變量接收刪除的值
 */
void delete(Node **p_head, int position, int *elem)
{
    Node *previous = *p_head;
    Node *current = previous->next;
    int length = get_length(*p_head);
    if (length == 0) {
        printf("空鏈表\n");
        return;
    }
    if (position < 1 || position > length) {
        printf("刪除位置不合法\n");
        return;
    }
    for (int i = 0; current->next != NULL && i < position - 1; i++) {
        previous = current;
        current = current->next;
    }
    *elem = current->data;
    previous->next = current->next;
    free(current);
}

通過 insert 和 delete函數，我們就能體會到不帶頭結點和帶頭結點的差別了，對於插入和刪除操作，不帶頭結點需要額外考慮在第一個元素前插入和刪除第一個元素的特殊情況，而帶頭結點的鏈表則將對所有元素的操作統一了。

還有特殊的刪頭法和刪尾法，這裡不再給出代碼了

查找和修改操作

查找本質就是遍歷鏈表，使用一個輔助指針，將該指針正確的遍歷到指定位置，就可以獲取該結點了。

修改則是在查找到目標結點的基礎上修改其值。

代碼很簡單，這裡不再列出。詳細代碼文末獲取。

單鏈表的優缺點

通過以上代碼，可以體會到：

優點：

• 插入和刪除某個元素時，不必像順序表那樣移動大量元素。
• 鏈表的長度不像順序表那樣是固定的，需要的時候就創建，不需要了就刪除，極其方便。

缺點：

• 單鏈表的查找和修改需要遍歷鏈表，如果要查找的元素剛好是鏈表的最後一個，則需要遍歷整個單鏈表，不像順序表那樣可以直接存取。

如果插入和刪除操作頻繁，就選擇單鏈表；如果查找和修改操作頻繁，就選擇順序表；如果元素個數變化大、難以估計，則可以使用單鏈表；如果元素個數變化不大、可以預估，則可以使用順序表。

總之，單鏈表和線性表各有其優缺點，沒必要踩一捧一。根據實際情況靈活地選擇數據結構，從而更優地解決問題才是我們學習數據結構和算法的最終目的。

【推薦閱讀】

• 詳解順序表
• 如何掌握 C 語言的一大利器——指針？

完整代碼請移步至 GitHub | Gitee 獲取。

如有錯誤，還請指正。

如果覺得寫的不錯可以關注一下我。