【數據結構之鏈表】詳細圖文教你花樣玩鏈表
【系列文章推薦閱讀】
- 【數據結構之隊列】詳細圖解！在學習隊列？看這一篇就夠了！
- 【數據結構之棧】用詳細圖文把「棧」搞明白（原理篇）
- 【數據結構之鏈表】看完這篇文章我終於搞懂鏈表了
- 如何掌握 C 語言的一大利器——指針？
- 【數據結構之順序表】用圖和程式碼讓你搞懂順序結構線性表
0. 提要鉤玄
文章【數據結構之鏈表】看完這篇文章我終於搞懂鏈表了已經介紹了鏈式存儲結構，介紹了鏈式存儲結構的最基本（簡單）實現——單向鏈表。
單向鏈表，顧名思義，它是單向的。
因為單鏈表的每個結點只有一個數據域和一個指針域，而該指針域只存儲了下一個結點的地址，所以我們只能通過某結點找到其直接後繼結點，卻不能通過某節點找到其直接前驅結點。
此外，由於單鏈表到尾結點（鏈表的最後一個結點）結束，所以尾結點的指針域是 NULL，以此來表示鏈表的終止，這就導致我們遍歷到尾結點的時候，如果想再次遍歷，只能手動回到頭結點再開始遍歷。
為了彌補單鏈表的上面兩個缺點，下面介紹兩種鏈表，它們都是單鏈表的變形，如果你理解了單鏈表，那麼會很容易理解這兩種變形。
1. 單向循環鏈表
1.1. 結構
單鏈表的尾結點的指針域是 NULL，所以單鏈表到此終止。如果我們使用單鏈表的尾結點的指針域存儲頭結點的地址，即尾結點的直接後繼結點為頭結點，如此一來，單鏈表就構成了一個環（循環），稱之為單項循環鏈表。
1.2. 實現思路
單向循環鏈表是由單鏈表進化而來的，算是單鏈表的「兒子」，所以單鏈表的那一套結構對於單向循環鏈表來說完全適用，從上圖你也可以看出，結構並無較大改變，二者所不同只在尾結點，所以我們只需要在尾結點和與尾結點相關的操作上下功夫就行了。
因此，單向循環鏈表的結構體和單鏈表的結構體相同。
/*單向循環鏈表的結點的結構體*/
typedef struct _Node {
int data; //數據域：存儲數據
struct _Node *next; //指針域：存儲直接後繼結點的地址
} Node;
為了統一對空鏈表和非空鏈表的操作，我們使用帶頭結點的鏈表來實現它。
1.3. 空鏈表及初始化
一個空鏈表如圖所示，只有一個頭指針和頭結點：
頭結點的指針域指向其本身構成一個循環，我們可以藉此來判斷鏈表是否為空。
if (head->next == head) {
printf("空鏈表。\n");
}
想要初始化一個空鏈表很簡單，創造頭結點，使頭結點的 next 指針指向其自身即可：
Node *create_node(int elem)
{
Node *new = (Node *) malloc(sizeof(Node));
new->data = elem;
new->next = NULL;
return new;
}
/**
* 初始化鏈表
* p_head: 指向頭指針的指針
*/
void init(Node **p_head)
{
//創建頭結點
Node *head_node = create_node(0);
//頭指針指向頭結點
*p_head = head_node;
//頭結點的next指針指向其本身，構成環
head_node->next = head_node;
}
1.4. 插入操作
這裡只演示頭插法和尾插法
【頭插法】
因為帶頭結點，所以不需要考慮是否為空鏈表。下圖是向空鏈表中頭插兩個元素的過程：
/**
* 頭插法，新結點為頭結點的直接後繼
* p_head: 指向頭指針的指針
* elem: 新結點的數據
*/
void insert_at_head(Node **p_head, int elem)
{
Node *new = create_node(elem);
Node *head_node = *p_head; //頭結點
//新結點插入頭結點之後
new->next = head_node->next;
head_node->next = new;
}
【尾插法】
因為為了盡量簡單，所以我們並沒有設置指向尾結點的尾指針，所以在尾插之前，需要先藉助某個指針，遍歷至尾結點，然後再插入。
/**
* 尾插法：新插入的結點始終在鏈表尾
* p_head: 指向頭指針的指針
* elem: 新結點的數據
*/
void insert_at_tail(Node **p_head, int elem)
{
Node *new = create_node(elem);
Node *head_node = *p_head; //頭結點
Node *tail = head_node; //tail指針指向頭結點
while (tail->next != head_node) { //tail遍歷至鏈表尾
tail = tail->next;
}
//尾插
new->next = tail->next;
tail->next = new;
}
1.5. 刪除操作
刪除的本質是「跳過」待刪除的結點，所以我們要找到待刪除結點的直接前驅結點，然後讓其直接前驅結點的 next 指針指向其直接後繼結點，以此來「跳過」待刪除結點，最後保存其數據域，釋放結點，即完成刪除。
這裡只演示頭刪法。
因為刪除的是頭結點的直接後繼結點，所以我們不必再費力尋找待刪除結點的直接前驅結點了。
/**
* 頭刪法：刪除頭結點之後的結點
* p_head: 指向頭指針的指針
* elem: 指向保存數據變數的指針
*/
void delete_from_head(Node **p_head, int *elem)
{
Node *head_node = *p_head; //頭結點
if (head_node->next == head_node) {
printf("空鏈表，無元素可刪。\n");
return;
}
Node *first_node = head_node->next; //首結點：頭結點的下一個結點
*elem = first_node->data; //保存被刪除結點的數據
head_node->next = first_node->next; //刪除結點
free(first_node); //釋放
}
1.6. 遍歷操作
我們可以一圈又一圈地循環遍歷鏈表，下面是循環列印 20 次結點地程式碼：
/**
* 循環列印20次結點
*/
void output_20(Node *head)
{
if (head->next == head) {
printf("空鏈表。\n");
return;
}
Node *p = head->next;
for (int i = 0; i <= 20; i++) {
if (p != head) { //不列印頭結點
printf("%d ", p->data);
}
p = p->next;
}
printf("\n");
}
2. 雙向鏈表
2.1. 結構
顧名思義，雙向鏈表，就是有兩個方向，一個指向前，一個指向後。這樣我們就彌補了單鏈表的某個結點只能找到其直接後繼的缺陷。如圖所示：
2.2. 實現思路
為了實現能指前和指後的效果，只靠 next 指針肯定是不夠的，所以我們需要再添加一個指針 —— prev，該指針指向某結點的直接前驅結點。
/*雙向鏈表的結點結構體*/
typedef struct _Node {
int data; //數據域
struct _Node *prev; //指向直接前驅結點的指針
struct _Node *next; //指向直接後繼結點的指針
} Node;
2.3. 空鏈表及初始化
雙向鏈表的空鏈表如圖所示：
要初始化一個這樣的空鏈表，需要創造出頭結點，然後將兩個指針域置空即可：
Node *create_node(int elem)
{
Node *new = (Node *)malloc(sizeof(Node));
new->data = elem;
new->prev = NULL;
new->next = NULL;
return new;
}
void init(Node **p_head)
{
//創建頭結點
Node *head_node = create_node(0);
//頭指針指向頭結點
*p_head = head_node;
}
2.4. 插入操作
這裡只演示頭插法，過程如下：
程式碼如下：
/**
* 頭插法，新結點為頭結點的直接後繼
* p_head: 指向頭指針的指針
* elem: 新結點的數據
*/
void insert_at_head(Node **p_head, int elem)
{
Node *new = create_node(elem);
Node *head_node = *p_head; //頭結點
if (head_node->next != NULL) { //不為空鏈表
Node *first_node = head_node->next; //首結點：頭結點的下一個結點
//首結點的prev指針指向new結點
first_node->prev = new;
//new結點的next指針指向首結點
new->next = first_node;
}
//new結點的prev指針指向頭結點
new->prev = head_node;
//頭結點的next指針指向new結點
head_node->next = new;
}
2.5. 刪除操作
這裡只演示頭刪法。下圖是將一個有兩個元素結點的雙向鏈表頭刪為空鏈表的過程：
程式碼如下：
/**
* 頭刪法
* p_head: 指向頭指針的指針
* elem: 指向保存變數的指針
*/
void delete_from_head(Node **p_head, int *elem)
{
Node *head_node = *p_head; //頭結點
Node *first_node = head_node->next; //待刪除的首結點：頭結點的下一個結點
if (head_node->next == NULL) { //判空
printf("空鏈表，無元素可刪。\n");
return;
}
*elem = first_node->data; //保存數據
if (first_node->next != NULL) {
first_node->next->prev = first_node->prev;
}
first_node->prev->next = first_node->next;
free(first_node);
}
2.6. 遍歷操作
有了 next 指針域，我們可以一路向後遍歷；有了 prev 指針域，我們可以一路向前遍歷。
這裡不再展示程式碼了。
3. 總結
了解了單向循環鏈表和雙向鏈表，就像拿搭積木一樣，我們還可以創造出來雙向循環鏈表。這裡就不再演示了，讀者可以自行嘗試。只要你搞懂上面三種鏈表，這絕非難事。
以上就是鏈表的花樣玩法部分內容，以後還會繼續更新。
如有錯誤，還請指正。
如果覺得寫的不錯，可以點個贊和關注。後續會有更多數據結構和演算法相關文章。
