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

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

線性表的鏈式存盤結構

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

所謂“曲線連接”即鏈式存盤，那什么是鏈式存盤呢？

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

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

這個例子反映在記憶體中，即為順序存盤結構，

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

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

這個例子反映在記憶體中，就是資料元素任意出現，占據某塊記憶體，

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

• 直線 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 = https://www.cnblogs.com/xingrenguanxue/p/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 獲取，

如有錯誤，還請指正，

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

標籤：其他

上一篇：繼人人都是產品經理后又一力作

下一篇：三種方法求解最大子區間和：DP、前綴和、分治