---

---

二、鏈表

暫時到這一步你就理解為：假如一個節點斷了，其實就連不上了。

2.1 鏈表初始化

#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化鏈表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}int main(int argc, char const *argv[]){Node *list = initList();return 0;
}

解釋上述代碼：

typedef struct node{ElemType data;struct node *next;
}Node;

首先這是一個結構體，并且還使用了關鍵字typedef。
ElemType data; 表示的是data是一個int類型，用來存儲該節點的數據，

最關鍵的就是struct node * next; 這是什么意思？
這是一個指針，指向的是一個類型為struct node類型的指針，并且這里必須是一個指針，因為若直接包含結構體本身（而非指針），會導致邏輯矛盾：

// 錯誤寫法！編譯失敗
typedef struct node {ElemType data;struct node next;  // 直接包含自身類型
} Node;

存在的問題?：結構體 node 內部又包含一個完整的 node，后者再包含另一個 node……形成無限嵌套，內存大小無法確定。

解決辦法?：改用指針 struct node *next。
→ ?指針的本質是地址?（固定占4或8字節），僅存儲下一個節點的內存起始位置，而非完整節點內容。
→ 物理上節點分散在內存各處，邏輯上通過指針串聯成鏈。

需要注意的是為什么內部要用 struct node 而非 Node？
這是因為在結構體定義內部，別名 Node ?尚未生效?（編譯器按順序解析）
**使用完整結構體名 struct node *next，明確告知編譯器這是一個指向相同結構類型的指針。
結構體自引用?：結構體內部用 struct node *next 聲明指針（而非 Node *next），因類型別名 Node 在結構體定義后才生效

struct node *next 的核心意義

• 功能?：作為“鏈”，指向下一個同類型節點，實現動態連接。
• ?必要性?：
  • 避免結構體無限嵌套 → 用指針代替自身類型。
  • 確保類型安全 → 必須指向 struct node 類型。
• ?操作優勢?：插入/刪除節點只需修改指針，無需移動數據（數組的劣勢）。

這個其實就產生了聯系，因為這個地方存儲的是一個指針，表示的就是下一個節點的其實位置，因此就逐漸串聯起來了。

接下來就看這個鏈表初始化：

Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}

Node* initList() 表示的是這個函數返回的是一個指針類型變量，該指針類型變量是Node* 類型，而Node* 類型又是什么類型指針變量，
Node*: 是一個結構體，鏈表結構體，返回值類型為 Node*（指向節點的指針），即返回鏈表的頭節點地址。
此函數無需外部參數，僅通過內部邏輯創建頭節點。

頭節點

• 作用?：頭節點是鏈表的起點，?不存儲有效數據?（其 data 字段常作為預留位置或存儲鏈表長度）。
• ?指針域?：head->next = NULL 表示鏈表初始為空，無后續節點

這個函數不僅分配了頭結點的內存地址，還完成了以下關鍵操作：

1. ?內存分配?：malloc(sizeof(Node)) 動態申請了一個節點所需的內存空間
2. ?數據初始化?：設置頭結點的數據域為固定值 0（頭結點通常不存儲用戶數據）
3. ?指針初始化?：明確將頭結點的 next 指針設為 NULL，表示空鏈表狀態
4. ?返回頭指針?：將初始化后的頭結點地址返回給調用方

這實現了鏈表的"哨兵節點"設計模式：頭結點作為固定存在的哨兵節點，簡化后續操作（插入/刪除時無需特殊處理鏈表為空的情況）。

2.2 單鏈表

2.2.1 單鏈表—頭插法

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化鏈表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//頭插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}int main(int argc, char const *argv[])
{Node *list = initList();insertHead(list, 10);insertHead(list, 20);return 0;
}

使用頭插法，一定要注意的是，創建的新的節點一定要先把他指向的內容給確定了，他指向的內容就是原本頭節點指向的下一個節點，為什么要這樣？
首先我們可以假設一下，如果我們先將頭節點指向我們插入的節點，這個很簡單，因為我們新的節點的地址很容易就能知道，這是我們這一行代碼

Node *p = (Node*)malloc(sizeof(Node));

我們使用的是malloc在堆內存里面申請一個空間，因此直接在申請的時候就能指導，那么我們其實要做的就是直接將這個地址，賦值給原本藍色塊里面存放地址的那個指針變量，但是需要注意的是我們會直接覆蓋點原本藍色塊存儲的指向70這個數據的地址（這是因為我們沒有用變量保存這個地址），這樣我們在想給新創建的這個數據里面的存放70這個數據的地址是沒有辦法的，因為我們找不到了，被覆蓋了。因此為了避免這種情況，我們可以使用一個變量進行保存，但是這樣就會很麻煩。那么我們可以換一個思路，那就是將順序改變，我們先從藍色快里面存儲的地址給復制到新創建數據節點存儲地址的指針變量，這樣相較于第一種思路我們就減少了一個保存地址的環節，接著我們在將新創建的地址在復制給藍色塊里面存放地址的那個指針變量，這樣就完成了頭插法。

所以一定要牢記，一定是新的節點，先指向原本頭節點指向的那個節點，然后再讓頭節點指向這個新的節點。

2.2.2 單鏈表—單鏈表遍歷

void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d　", p->data);p = p->next;}printf("\n");
}

對于剛接觸鏈表可能有一點繞，因為逐行看這一段代碼，

Node *p = L->next;

表示的是這個鏈表的頭節點（就是不存儲實際數據的節點）賦值給我們創建的一個中間指針變量（該指針變量的類型就是節點類型的結構體），那么我們首先要看看這個頭節點鏈接了下一個數據節點，如果沒有連接，那么里面的指針變量就是NULL，相反如果鏈接了就不是NULL，那么就會進入while循環，

printf("%d　", p->data);
p = p->next;

此時我們指導，指針p存儲的就是當前第一個節點（存儲有效數據節點）存儲的數據，

接著就是

p = p->next;

這一步理解起來就是相當于for循環里面的變量 i，就是將p里面現在存儲的下一個節點地址在賦值給p，循環使用這個p，就像循環使用變量 i 一樣，只不過這個地方的是指針，看起來要繞一點或者是難以理解一點，這是因為剛開始結束，因此就顯得有點繞，但是問題不大，隨著長時間對指針的使用這種就會形成固化的思路，就會簡單很多。

• Node *p = L->next;
  • L 是頭節點指針?（通常不存儲實際數據）
  • L->next 指向鏈表的第一個實際數據節點?
  • p 被賦值為第一個實際節點的地址
• while(p != NULL) 循環：
  • 循環條件檢查 p 是否指向有效節點
  • 當 p 指向第一個節點時，執行的是 printf("%d　", p->data)
  • 因此輸出的是第一個實際節點的數據，而非頭節點的數據

頭節點 [L] → 指向第一個實際節點
↓
實際節點1 [p] → 實際節點2 → … → NULL
↓
data (被打印)

值得注意的是：
頭插法的順序和排列的順序是相反的。

2.2.3 單鏈表—尾插法

其實尾插法的總體思路和頭插法思路是一樣的，但是我們需要找到鏈表的最后一個數據，怎么找到這個數據，截止到目前，我能想到的其實還是使用遍歷的思想。

頭插法是很容易找到頭的，這是因為我們給的就是鏈表的頭節點，這是本身的結構決定了頭插法速度很快，這是因為我們天然的就可以獲取到鏈表頭節點的地址，從而完成對應的數據插入。

但是尾插法不一樣，因為我們不是太容易找到鏈表的最后一個數據，找到最后一個節點儲存地址的指針變量里面存儲的是一個NULL指針。

void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d　", p->data);p = p->next;}printf("\n");
}

上述是遍歷的思路，我們可以在這個基礎上進行使用。

void listNode(Node* L)
{Node *p = L->next;while(p != NULL){p = p->next;}/* 接著進行相關尾插相關操作 */
}

對于以上就是我本人的思路，我想當然的就在這個函數里面直接就處理了關于尾插法的一些操作，這個思路固然是沒有錯的，但是我們忘記了一件事，那就是我們在開發過程中有一個原則，那就是：一個函數僅完成一件功能。如果一個函數實現多個功能給開發、使用、維護都帶來很大的困難。將沒有關聯或者關聯很弱的語句放到同一函數中，會導致函數職責不明確，難以理解，難以測試和改動。
另一個原因我們忘記了C語言中return的使用。

基于上述的原則，我們要明確一個函數就干一個事情，例如上述的函數我們的目的就是找到尾節點，因此我們就需要保證這個函數的功能就是找尾節點，為什么吶，這是因為在其他地方或者是多個鏈表的時候，可能有時候只需要找到尾節點就行了，因為我們要把這個函數的功能給獨立出來。

這個地方其實也是自己在梳理開發思路，因為開發過程中邏輯很復雜，我們要抽絲剝繭的去分解任務，分解相關邏輯，那其實就是將一個應用分解為無數個功能模塊，而每一個功能模塊又要分解為不同的任務函數，只需要在對應的函數預留出對應的接口，這樣才是多人協同工作效率最高的辦法，這也是我們所追求的。

以下是我用AI搜到的關于在嵌入式軟件工程師招聘過程中要求較強的文檔編寫能力解釋：
在嵌入式開發領域，“較強的文檔編寫能力”并不僅僅指會寫文字，而是指能夠通過專業、系統、清晰的文檔將技術方案、設計決策、接口規范等關鍵信息結構化地沉淀下來，確保項目可維護、可協作、可追溯。這種能力是嵌入式工程師技術素養的重要體現，也是團隊協作和產品質量的保障。下

工程師如何提升文檔能力？

1. ?復用模板?：
   • 需求文檔 → 參考中的功能/非功能需求結構
   • 設計文檔 → 采用的模塊化描述框架
2. ?工具協同?：
   • 用Doxygen自動生成代碼接口文檔
   • 使用PlantUML繪制狀態機/時序圖嵌入文檔
3. ?語言技巧?：
   • 多用被動語態（“數據被采集”而非“我們采集數據”）
   • 動詞明確（“配置”“校驗”“觸發”替代“處理”“操作”）

以上僅作為一個參考，帶有個人的主管臆測。

回歸正題，那么關于獲取尾節點正確的寫法就是

Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}

其實這一快最不習慣的就是

Node*  get_tail(Node  *L)

因為我們一般會使用

int get_tail(Node  *L) 等等

但是關于這種指針變量，并且還是使用typedef關鍵字給重新命名的指針變量還需要進一步習慣和固化。

2.2.4 單鏈表—在指定位置插入數據

==這里就跟頭插法分析的一樣，一定不能搞錯指向順序，==
**一定是先把70這個節點存儲的80節點地址賦值給新的節點存儲下一個節點地址的變量。雖然有點繞，但是這個很關鍵的因素。這是插入的核心思想，一定不能錯。牢記于心！！！！！！**

int insertNode(Node *L, int pos, ElemType e)
{//用來保存插入位置的前驅節點Node *p = L;int i = 0;//遍歷鏈表找到插入位置的前驅節點while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}//要插入的新節點Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}

Node *p = L;

這個地方就是將頭結點先給p，也就是只有找到鏈表的其實位置才能進行查找依次查找嘛，畢竟鏈表是開始。

還有就是我們需要明白的是我們插入的位置，如果是想在位置5插入，那么我們就需要知道位置4節點結構體里面存儲下一個節點的地址，因此在while循環的時候，其實就是找的就是前一個節點。

Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);listNode(list);insertNode(list, 3, 15);listNode(list);return 0;

原本是：10 20 30
我想在第二個位置插入15，其實就是10和20之間
需要說明的是：

• 若鏈表有頭結點，則：
  • 頭結點 → 位置1（10） → 位置2（20） → 位置3（30）
  • ?在第二個位置插入? = 在 10 和 20 之間插入。
• 若鏈表無頭結點，則：
  • 位置1（10） → 位置2（20） → 位置3（30）
  • ?在第二個位置插入? = 在 10 和 20 之間插入。
    可以看出不管是有沒有頭結點，我們都把有效存儲數據的節點成為第一個位置。

2.2.5 單鏈表—刪除指定位置節點

其實可以看出來道理是相同的，但是需要注意的是我們一定要釋放內存。

因為這個里面的都是在堆內存中，找到的位置，如果刪除，就一定要釋放。

找到要刪除節點的前置節點 p
用指針 q記錄要刪除的節點
通過改變 p的后繼節點實現刪除
釋放刪除節點的空間

//刪除節點int deleteNode(Node *L, int pos)
{//要刪除節點的前驅Node *p = L;int i = 0;//遍歷鏈表，找到要刪除節點的前驅。while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要刪除的位置錯誤\n");return 0;}//q指向要刪除的節點Node *q = p->next;//讓要刪除節點的前驅指向要刪除節點的后繼p->next = q->next;//釋放要刪除節點的內存空間free(q);return 1;
}

同樣可以看出如果想刪除，一定也要找到刪除節點的前一個節點。

我們p節點里面的存儲的節點指針其實就是我們即將刪除的節點信息，因此需要先將這個信息找一個中間量，將這個刪除節點里面的信息給保存下來，注意這個指針變量一定要聲明稱和節點保持一致，如果不一樣就這個指針就不能保存這個刪除節點的信息，那么就會導致無法連接后面沒有刪除的節點。

因此吶，我們就將這個節點信息保存給q，同事我們緊接著就是將q里面存儲的指向寫一個節點的信息給存儲到我們找到的前一個位置節點p里面，這樣節點p就完成了后續節點的連接，讓這個鏈表給連接起來了。

最后就是使用 free(q); 進行內存釋放。

2.2.6 單鏈表—獲取鏈表長度

//獲取鏈表長度int listLength(Node *L){Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;}

較為簡單不需要詳細降解。

2.2.7 單鏈表—釋放鏈表

//釋放鏈表void freeList(Node *L){Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}

釋放鏈表，但是頭結點是不釋放的，這個一定要注意！！！！！！！！！

指針 p指向頭節點后的第一個節點

判斷指針 p 是否指向空節點

如果 p不為空，用指針q記錄指針p的后繼節點。

釋放指針 p指向的節點

指針 p和指針p指向同一個節點，循環上面的操作。

其實這些指針看起來還是不是那么自在這是因為不熟悉指針的使用。

next在結構體里面是一直是下一個的地址

這個地方還是想多說幾句，就是我們一定要理解，next存放的是下一個節點的結構體的地址，因此我們的這三行代碼

        q = p->next;free(p);p = q;

邏輯如下：
首先我將現在p里面指向下一個節點的地址給取出來，存在q里面，這個q現在存儲的是一個結構體指針變量，接下來我就先釋放q，最后我在將q這個結構體地址給賦值給p，然后進行一個循環，因為此時的p又變成了一個結構體，因此可以使用 q = p->next;

在這里釋放內存，就是釋放原來這個地方內存。

---

區別于順序表
鏈表在插入數據、刪除數據快速。 但是讀取速度慢，因為需要遍歷，通過指向進行逐個循環。
順序表：找東西很快，相當于是數組。

---

文章源碼獲取方式：
如果您對本文的源碼感興趣，歡迎在評論區留下您的郵箱地址。我會在空閑時間整理相關代碼，并通過郵件發送給您。由于個人時間有限，發送可能會有一定延遲，請您耐心等待。同時，建議您在評論時注明具體的需求或問題，以便我更好地為您提供針對性的幫助。

【版權聲明】
本文為博主原創文章，遵循 CC 4.0 BY-SA 版權協議。這意味著您可以自由地共享（復制、分發）和改編（修改、轉換）本文內容，但必須遵守以下條件：
署名：您必須注明原作者（即本文博主）的姓名，并提供指向原文的鏈接。
相同方式共享：如果您基于本文創作了新的內容，必須使用相同的 CC 4.0 BY-SA 協議進行發布。

感謝您的理解與支持！如果您有任何疑問或需要進一步協助，請隨時在評論區留言。