本節重要性#
因為單鏈表是非常基礎的鏈式結構，所以當你學會了用 C 語言描述單鏈表的時，後面的堆、棧、雙向鏈表、哈希表等用 C 描述將不在話下。
如果你是一名初學者，強烈建議自己敲一遍代碼。
單鏈表的節點#
如圖所示，單鏈表的節點分為數據域和指針域，可以將它們視為一個整體，稱之為節點，稍後我們會用結構體來表示節點。
數據域，顧名思義，就是存放數據的地方。
指針域，是用來存放指針變量的地方，指針指向下一個節點的地址。
單鏈表的表示#
單鏈表是線性表的鏈式表示和實現。把節點鏈接起來，就形成了單鏈表。
定義表示節點的結構體#
如何用 C 語言描述節點？這裡我們用到了struct。
struct node {
/* 後繼節點 */
struct node *next;
/* 值 */
int data;
};
首先我們定義了一個結構體，結構體的標記為node。
其次，它具有兩個屬性，一個是int類型的data，也就是上文提到的數據域。還有一個是指針域。
如何理解struct node *next呢？
要知道，指針域是存放指針變量的，這個變量名叫做 next，又因為這個指針是指向下一個節點的地址的，換句話說，這個指針指向的是一個我們定義的用來表示節點的結構體。所以這個指針變量的類型為 struct node。星號*表示它是指針變量。所以合起來就是struct node *next。
最後，為了方便，我們可以使用typedef關鍵字為struct node取一個別名。
typedef struct node {
/* 後繼節點 */
struct node *next;
/* 值 */
int data;
}list;
這樣，在後面的代碼書寫中，list就等價於struct node了。
比如我們使用這個結構體創建一個新的節點， list *new_node就等價於struct node *new_node。
單鏈表的創建#
list * create_list()
{
/* 創建一個新的節點，由於使用了typedef關鍵字，此處 node *head與struct node *head等價 */
list *head = (list *)malloc(sizeof(list));
if(head==NULL) return NULL;
/* 初始化節點 */
head->data = 0; // 頭結點數據域，我們用來表示鏈表長度
head->next = NULL;
return head;
}
此函數會創建一個單鏈表，並返回頭指針。
頭指針是指向頭結點地址的指針，和節點中指向下一個節點的指針是相同類型。
首先，我們用malloc函數開辟了一塊list大小的內存，並返回了指向該內存塊首地址的指針，同時將此指針賦值給頭指針變量。
接著，判斷此指針是否為空，為空，則說明內存申請失敗（一般不會）。
然後，對該節點進行初始化。
最後，函數返回頭指針，結束。
為什麼設置頭節點？
頭節點的數據域一般無意義，這裡為了方便後面的插入和刪除操作而設置，頭節點並非鏈表所必須。
頭節點後面的第一個元素節點，稱為首元節點。
單鏈表的插入#
試想如下情況，一個新的節點n，要插入到x節點後。
圖中虛線表示斷開連接，下同。
按照一般思路可能是:
x->next = n;
n->next = x->next;
顯然，這是錯誤的，因為執行x->next = n之後，n->next = x->next等價於n->next = n ，所以正確的做法應該是這樣；
n->next = x->next;
x->next = n;
完整版插入函數：
插入函數接受三個參數，被插入節點的鏈表的指針head，新結點的數據data，和要插入的位置pos；
list * list_insert_node(list *head, int data, int pos)
{
int i;
list *curr = head;
/* 如果要插入的位置比鏈表長，則屬於非法操作 */
if(pos > curr->data) return NULL;
/* 創建一個節點，並初始化 */
list *node = (list *)malloc(sizeof(list));
if(node==NULL) return NULL;
node->data = data;
node->next = NULL;
/* 遍歷鏈表，找到要插入的位置 */
for(i=0;i<pos;i++){
curr = curr->next;
}
/* 插入 */
node->next = curr->next;
curr->next = node;
/* 鏈表長度+1 */
head->data++;
return head;
}
可以在 main 函數中調用測試：
list *l = create_list();
printf("當前鏈表長度：%d\n", l->data);
list_insert_node(l, 1, 0);
printf("當前鏈表長度：%d\n", l->data);
使用 gcc 編譯:
gcc -fsanitize=address -fno-omit-frame-pointer -g linked_list.c && ./a.out
輸出正常且無內存報錯信息：
當前鏈表長度：0
當前鏈表長度：1
單鏈表的遍歷#
較為簡單，不再解釋
/* 打印鏈表數據，但不包括頭結點的數據*/
void print_list(list *head)
{
list *curr = head->next;
while (curr)
{
printf("%d \t", curr->data);
curr = curr->next;
}
printf("\n");
}
單鏈表的刪除#
假設要刪除 head 後的節點，那麼直接讓head->next = head->next->next即可，但不要忘記釋放被刪除的節點。
基於此思路：
list *list_delete_data(list *head, int pos)
{
int i;
list *curr = head;
/* 如果要刪除的位置比鏈表長，則屬於非法操作 */
if(pos > curr->data) return NULL;
/* 遍歷鏈表，找到要刪除的節點的前一個節點的指針 */
for(i=0;i<pos;i++){
curr = curr->next;
}
// 臨時記錄將被刪除的節點
list *temp = curr->next;
// 刪除節點
curr->next = curr->next->next;
//釋放掉被刪除節點的內存
free(temp);
head->data--;
return head;
}
單鏈表的測試#
這樣，一個基礎的鏈表就寫好了，可以在main函數中測試。
int main()
{
int i;
list *l = create_list();
// 多次插入數據
for(i=0;i<5;i++){
list_insert_node(l, i, 0);
print_list(l);
}
list_delete_data(l, 0);
print_list(l);
return 0;
}
編譯與輸出：
# gcc -fsanitize=address -fno-omit-frame-pointer -g linked_list.c && ./a.out
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0
3 2 1 0
完整代碼#
完整代碼，詳見代碼清單。
https://github.com/austin2035/learn-data-structures