?

前言

數據結構篇其二實現了一個簡單的單鏈表，鏈表的概念，單鏈表具體實現已經說明，如下：
單鏈表
事實上，前面的單鏈表本質上是無頭單向不循環鏈表。此篇說明的雙向鏈表可以說完全反過來了了。無論是之前的單鏈表還是雙向鏈表，本質都是鏈表家族的兩位成員。
主題一：鏈表分類
詳細說說鏈表的特征，以及這些特征組合的鏈表種類。
主題二：雙向鏈表的實現
像上次實現單鏈表一樣，這次也試著獨立實現雙向鏈表吧。
學習收獲：十分鐘手搓一個鏈表

為什么學習雙向鏈表？
因為雖然字面上雙向鏈表好像還難一點，結構雖然復雜，但是實現起來特別簡單。應用場景有顯著的優勢。

鏈表的分類

• 單向與雙向

鏈表的單向與雙向：這說明節點與節點之間的聯系。單向鏈表節點的指針一路往后。雙向鏈表節點指針指前指后。

可見，從定義上，雙向鏈表天生應該有兩個指針，所以在單鏈表的基礎上，我們可以推出雙向鏈表的定義。

//雙向鏈表的定義
typedef int LTDataType;
typedef struct ListNode {LTDataType data;//數據域struct ListNode* prev;//前驅指針struct ListNode* next;//后繼指針
}ListNode;

鏈表雙向和單向決定了它節點指針的數量

• 帶頭與不帶頭

為了方便對鏈表進行操作，我們會在鏈表的第一個節點前附帶一個頭節點（哨兵位），注意頭節點不是第一個節點，第一個節點存儲的是有效數據。
頭節點的數據域不存儲有效的數據，指針域next指向第一個節點，若是雙向的話，則前驅指針指向尾結點。
需注意這個時候頭指針就指向頭節點，而不是第一個節點了。

• 循環非循環

若鏈表的尾結點指向頭節點而不是NULL，則鏈表閉合形成了一個環，可以循環了，就稱為循環鏈表。反之，則為不循環鏈表。

1. 以上就是鏈表的三大特征，每種特征又分兩種情況。組合起來一共8種，所以鏈表種類一共8種。
2. 下面介紹雙向鏈表，來熟悉一下雙向，帶頭，循環的鏈表吧。

雙向鏈表的實現

下面實現這些函數

// 創建返回鏈表的頭結點.
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(ListNode* plist);
// 雙向鏈表打印
void ListPrint(ListNode* plist);
// 雙向鏈表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* plist);
// 雙向鏈表頭插
void ListPushFront(ListNode * plist, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* plist);

前面已經給出了雙向鏈表的定義。但下圖只體現了雙向，循環和帶頭還要我們具體實現。

typedef int LTDataType;
typedef struct ListNode {LTDataType data;//數據域struct ListNode* prev;//前驅指針struct ListNode* next;//后繼指針
}ListNode;

開局一個頭指針，能這樣做嗎？

int main() {ListNode* plist = NULL;return 0;
}

這個是帶頭的鏈表，起碼有頭節點吧，所以先創建一個頭節點。
其次，這個是循環鏈表，頭節點的前驅指針和后繼指針應該都指向自己吧。

節點創建

ListNode* ListCreate(LTDataType x) {ListNode* phead = (ListNode*)malloc(sizeof(ListNode));//判斷動態空間是否開辟失敗。if (phead == NULL) {perror("malloc fail");exit(-1);}phead->data = x;//頭節點數據隨便賦值phead->next = phead;//前驅，后繼指針指向自己phead->prev = phead;return phead;
}

雙向鏈表初始化

ListNode* ListInit() {return ListCreate(-1);//頭節點的數據域隨便給值。
}

還沒有元素啊，那就先插入節點吧

雙向鏈表的尾插

1. 保證每個節點的兩個指針有明確的指向。

2. 尾插操作的節點有三個，頭節點，尾結點，新節點。

3. 按照上面圖片的步驟寫代碼。

4. 后面請自行畫圖分析，多創建臨時變量，良好的命名習慣。寫完一個函數去測試一下。

void ListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = ListCreate(x);//創建新節點ListNode* tail = phead->prev;//記錄尾結點//執行尾插操作phead->prev = newnode;newnode->next = phead;tail->next = newnode;newnode->prev = tail;
}

打印函數

void ListPrint(ListNode* phead) {assert(phead);ListNode* pcur = phead->next;printf("head->");while (pcur!= phead) {printf("%d->", pcur->data);pcur = pcur->next;}pcur = NULL;printf("return\n");
}

雙鏈表的頭插

void ListPushFront(ListNode* phead,LTDataType x) {assert(phead);ListNode* newnode = ListCreate(x);ListNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

雙向鏈表的尾刪

//尾刪函數
void ListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tailprev = tail->prev;phead->prev = tailprev;tailprev->next = phead;if(phead->prev!=phead)//判斷是否為空表，哨兵位不能釋放了。free(tail);tail = NULL;}

雙向鏈表的頭刪

/頭刪函數
void ListPopFront(ListNode* phead) {assert(phead);ListNode* first = phead->next;ListNode* second = first->next;phead->next = first->next;second->prev = phead;if (phead != first)//哨兵位不能釋放{free(first);}first = NULL;second = NULL;
}

雙向鏈表的銷毀

void ListDestory(ListNode** pphead) {assert(pphead);assert(*pphead);ListNode* pcur = (*pphead)->next;ListNode* next = pcur->next;while (pcur != *pphead){free(pcur);pcur = next;next = next->next;}free(pcur);pcur = NULL;next = NULL;*pphead = NULL;}

雙向鏈表補充

// 雙向鏈表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos);

雙向鏈表查找指定數據

ListNode* ListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;//找到了返回當前節點的地址}pcur=pcur->next;}return NULL;//雙鏈表跑完一遍都沒找到，返回空。
}

在pos節點之前插入新節點

//在pos之前插入
void ListInsert(ListNode* pos, LTDataType x) {assert(pos);ListNode* newnode = ListCreate(x);ListNode* prev = pos->prev;newnode->next = pos;pos->prev = newnode;prev->next = newnode;newnode->prev = prev;pos = NULL;prev = NULL;newnode = NULL;
}

刪除位置為pos的節點

void ListErase(ListNode* pos) {assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);prev->next = next;next->prev = prev;pos = NULL;prev = NULL;next = NULL;
}

十分鐘實現一個鏈表

1. 實現什么類型的鏈表？
2. 需要寫什么函數？

雙向鏈表；
實現函數，增刪查改，還有來鏈表的初始化，銷毀。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
}LT;LT* LTInit(void) {LT* newnode = (LT*)malloc(sizeof(LT));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->next = newnode;newnode->prev = newnode;return newnode;
}LT LTDestory(LT** pphead) {assert(pphead);assert(*pphead);LT* pcur = (*pphead)->next;LT* next = pcur->next;while (pcur != *pphead) {free(pcur);pcur = next;next = next->next;}free(pcur);*pphead = NULL;}//在pos之前插入新節點
void LTInsert(LT* pos, LTDataType x) {assert(pos);LT* prev = pos->prev;LT * newnode = (LT*)malloc(sizeof(LT));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->data = x;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}void LTErase(LT* pos) {assert(pos);LT* prev = pos->prev;LT* next = pos->next;free(pos);prev->next = next;next->prev = prev;
}void LTPushBack(LT* phead,LTDataType x) {LTInsert(phead, x);
}void LTPushFront(LT* phead, LTDataType x) {LTInsert(phead->next, x);
}void LTPopBack(LT* phead) {LTErase(phead->prev);
}void LTPopFront(LT* phead) {LTErase(phead->next);
}LT* LTFind(LT* phead, LTDataType x) {LT* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;return;
}LT* LTMidfy( LT* pos,LTDataType x) {pos->data = x;
}

雙向鏈表完結。鏈表完結！