【數據結構】鏈表 + 手動實現單鏈表和雙鏈表的接口(圖文并茂附完整源碼)

文章目錄

一、鏈表的概念及結構

二、鏈表的分類

?編輯

三、手動實現單鏈表

1、定義單鏈表的一個節點

2、打印單鏈表

3、創建新節點

4、單鏈表的尾插

5、單鏈表的頭插

6、單鏈表的尾刪

7、單鏈表的頭刪

8、單鏈表的查找

?9、在指定位置之前插入一個新節點

10、在指定位置之后插入一個新節點

11、刪除指定節點

12、刪除指定節點之后的節點

13、銷毀鏈表

四、單鏈表實現完整代碼

五、手動實現雙向鏈表

1、定義雙向鏈表的一個節點

2、創建新節點

3、雙向鏈表的初始化

4、打印

5、尾插

6、頭插

7、尾刪

8、頭刪

9、查找

10、指定位置之后插入

11、刪除指定位置的節點

12、銷毀

?六、雙向鏈表完整源碼

一、鏈表的概念及結構

鏈表是?種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。即鏈表的邏輯結構是線性的，物理結構是非線性的。

如上圖所示，鏈表的每個節點在內存中都是隨機分布著的，所以其物理結構（存儲結構）為非連續，非順序的；但是，鏈表的每個節點中的指針指向下一個節點，所以其邏輯結構是線性的。?

?如圖，鏈表的結構跟火車車廂相似，淡季時車次的車廂會相應減少，旺季時車次的車廂會額外增加幾節。只需要將火車里的某節車廂去掉/加上，不會影響其他車廂，每節車廂都是獨立存在的。車廂是獨立存在的，且每節車廂都有車門。想象一下這樣的場景，假設每節車廂的車門都是鎖上的狀態，需要不同的鑰匙才能解鎖，每次只能攜帶一把鑰匙的情況下如何從車頭走到車尾？最簡單的做法：每節車廂里都放一把下一節車廂的鑰匙。

再對應到鏈表，火車的車廂就是鏈表的節點，而下一節車廂中放的鑰匙就是鏈表的每個節點中存放的下一個節點的地址。

鏈表的每個類似于車廂的結構，都是獨立申請的空間，我們稱之為節點。每個節點都由兩部分組成：想要存儲的數據和存儲下一個節點地址的指針。鏈表中每個節點都是獨立申請的（即需要插?數據時才去申請?塊節點的空間），我們需要通過指針變量來保存下?個節點位置才能從當前節點找到下?個節點。

二、鏈表的分類

鏈表的結構非常多樣，以下情況組合起來就有8種（2x2x2）鏈表結構：

?1、帶頭與不帶頭

帶頭即鏈表有頭節點（哨兵位），頭節點不存放實際有意義的數據，只是用來占位置。有哨兵位的鏈表就是帶頭鏈表，如果帶頭鏈表只有一個頭節點，該鏈表就為空鏈表。反之，沒有哨兵位就是不帶頭鏈表，這時，鏈表的第一個節點就不能稱為頭節點。

2、單向與雙向?

單向即鏈表的節點只有一個指向下一個節點的next指針。

雙向即鏈表的節點不僅有一個指向下一個節點的next指針，還有指向上一個節點的prev指針。

3、循環與不循環

循環鏈表的尾節點的指針并不指向NULL，而是指向第一個有效的節點?。

三、手動實現單鏈表

根據上面鏈表的分類，單鏈表為不帶頭單向不循環鏈表。

為了方便閱讀和查閱，我們先將單鏈表的頭文件代碼展示出來

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DateType;
//創建單鏈表的一個節點
typedef struct SList
{DateType val;struct SList* next;//指向下一個節點的指針
}SLT;//打印單鏈表
void PrintSLT(SLT* phead);
//鏈表尾插
void SLTpushBack(SLT** pphead, DateType x);
//鏈表頭插
void SLTpushFront(SLT** pphead, DateType x);
//鏈表尾刪
void SLTpopBack(SLT** pphead);
//鏈表頭刪
void SLTpopFront(SLT** pphead);
//鏈表的查找
SLT* SLTFind(SLT* ps, DateType x);
//在鏈表的指定位置之前插入一個新的節點
void SLTInsert(SLT** pphead, SLT* pos, DateType x);
//在鏈表的指定位置之后插入一個新的節點
void SLTInsertAfter(SLT* pos, DateType x);
//刪除指定節點
void SLTErase(SLT** pphead, SLT* pos);
//刪除指定節點之后的節點
void SLTEraseAfter(SLT* pos);
//銷毀鏈表中的所有節點
void SLTDestry(SLT** pphead);

1、定義單鏈表的一個節點

typedef int DateType;
//創建單鏈表的一個節點
typedef struct SList
{DateType x;struct SList* next;//指向下一個節點的指針
}SLT;

節點中有兩個變量，一個用來存儲數據，一個用來存儲下一個節點的地址。由于next指針指向下一個節點，所以next為struct SList* 類型的指針變量。用typedef關鍵字來重定義，既方便我們修改，也方便我們書寫。

2、打印單鏈表

想要打印單鏈表，只需要將單鏈表遍歷一次。但是有個小細節，我們需要創建另一個SLT*類型的指針pcur，然后用這個指針來遍歷單鏈表，防止指針指向改變而找不到鏈表的第一個節點。

//打印單鏈表
void PrintSLT(SLT* phead)
{SLT* pcur = phead;while (pcur){printf("%d->", pcur->val);pcur = pcur->next;}
}

3、創建新節點

想要實現單鏈表的尾插，頭插以及指定位置插入數據，就避免不了要創建新的節點。由于鏈表再存儲結構上非連續，所以我們用malloc來動態申請內存空間，然后將新節點的地址返回。

//創建新節點
SLT* BuyNode(DateType x)
{SLT* newnode = (SLT*)malloc(sizeof(SLT));if (newnode == NULL){perror("malloc");exit(1);}newnode->val = x;newnode->next = NULL;return newnode;
}

4、單鏈表的尾插

（1）對pphead斷言操作，因為我們不能對空指針進行解引用操作。但是，*pphead可以為空，此時鏈表為空鏈表。

?（2）創建一個新節點newnode，用來存放指定的數據，并返回新節點的地址。

（3）鏈表是否為空：

空鏈表：即*pphead=NULL，我們只需要讓*pphead=newnode；

非空鏈表：因為要尾插，我們先要找到鏈表的尾節點，注意，while循環結束的條件是：

pcur->next = NULL。然后讓尾節點的next指針指向新節點。

注意：當我們在尾插時，如果直接將plist作為實參傳遞給形參phead，那么我們發現，形參phead并不會影響實參plist的值。我們想要改變實參plist的值，就要傳地址，而不是傳值。由于plist是SLT*類型的指針，所以需要用SLT**類型的二級指針來接收實參。

如下圖為傳值調用，經過調試和運行，plist中的val值并沒有發生改變。

//鏈表尾插
void SLTpushBack(SLT** pphead, DateType x)
{//斷言pphead不能為NULL，不能對空指針解引用assert(pphead);//創建新節點SLT* newnode = BuyNode(x);//處理空鏈表if (*pphead == NULL){*pphead = newnode;}//處理非空鏈表else{SLT* pcur = *pphead;while (pcur->next)//找尾節點{pcur = pcur->next;}pcur->next = newnode;}
}

5、單鏈表的頭插

首先同樣是對pphead斷言操作，然后創建新節點，讓新節點的next指針指向原來的第一個節點，這時候我們就不需要關注；吧是否為空了。

//鏈表頭插
void SLTpushFront(SLT** pphead, DateType x)
{assert(pphead);SLT* newnode = BuyNode(x);SLT* pcur = *pphead;newnode->next = pcur;*pphead = newnode;
}

6、單鏈表的尾刪

由于鏈表的節點的空間都是malloc動態申請的，因此，刪除鏈表的節點即釋放節點所占的空間。

（1）對pphead斷言；且對*pphead斷言，因為，如果*pphead = NULL，則鏈表為空鏈表，不需要尾刪。

（2）處理不同節點數量的情況：

只有一個節點：當 *pphead->next = NULL時，即只有一個節點，直接將*pphead釋放。

不止一個節點：我們需要先找到鏈表的尾節點（遍歷），然后釋放。然后將尾節點的前一個節點的next指針置為空。因此，我們需要用創建pcur指針，防止找不到第一個節點；同時，創建prev指針記錄尾節點的前一個節點。

//鏈表尾刪
void SLTpopBack(SLT** pphead)
{//斷言assert(pphead && *pphead);//只有一個節點if ((*pphead)->next == NULL){free(*pphead);//釋放*pphead = NULL;}//不止一個節點else{SLT* pcur = *pphead;SLT* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);//釋放pcur = NULL;prev->next = NULL;}
}

7、單鏈表的頭刪

（1）對pphead斷言；且對*pphead斷言，因為，如果*pphead = NULL，則鏈表為空鏈表，不需要尾刪。

（2）釋放第一個節點。但在釋放之前需要用一個指針pcur記下第一個節點之后的節點，因為釋放后，*pphead應該為原來的第二個節點。

//鏈表頭刪
void SLTpopFront(SLT** pphead)
{//斷言assert(pphead && *pphead);SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}

8、單鏈表的查找

先斷言，phead不能為空鏈表；然后創建pcur指針遍歷鏈表，防止改變phead指針指向而找不到第一個節點。

//鏈表的查找
SLT* SLTFind(SLT* phead, DateType x)
{assert(phead);SLT* pcur = phead;while (pcur){if (pcur -> val == x){return pcur;}pcur = pcur->next;}return NULL;
}

?9、在指定位置之前插入一個新節點

（1）斷言；

（2）創建新節點；

（3）將新節點與鏈表連接起來。我們需要找到指定位置之前的節點prev，然后將prev節點，新節點newnode和指定位置的節點pos連接起來。

//在鏈表的指定位置之前插入一個新的節點
void SLTInsert(SLT** pphead, SLT* pos, DateType x)
{assert(pphead && *pphead);assert(pos);SLT* newnode = BuyNode(x);//找pos節點之前的節點SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//連接prev,newnode,posprev->next = newnode;newnode->next = pos;
}

10、在指定位置之后插入一個新節點

（1）斷言；

（2）創建新節點；

（3）將新節點與鏈表連接起來。我們需要找到指定位置之后的節點pback，然后將指定位置的節點、新節點newnode和pback節點連接起來。

//在鏈表的指定位置之后插入一個新的節點
void SLTInsertAfter(SLT* pos, DateType x)
{assert(pos);SLT* newnode = BuyNode(x);SLT* pback = pos->next;//連接pos,newnode,pbackpos->next = newnode;newnode->next = pback;
}

11、刪除指定節點

（1）斷言；

（2）pos為第一個節點：釋放后首節點改變。

pos不是第一個節點：釋放指定節點，但在此之前需要先將指定節點之前的節點prev和指定節點之后的節點pback記錄下來,最后連接prev節點和pback節點。

//刪除指定節點
void SLTErase(SLT** pphead, SLT* pos)
{assert(pphead && *pphead);assert(pos);//指定節點為第一個節點if (*pphead == pos){SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}else{SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//先連接pos節點的前一個節點與pos的后一個節點prev->next = pos->next;free(pos);pos = NULL;}
}

12、刪除指定節點之后的節點

先斷言，看pos是否為空且pos之后的節點是否為尾節點；若斷言通過，則創建std記錄pos之后的節點，以及創建later 記錄std的后一個節點，然后連接pos與later；最后釋放指定節點之后的節點。

//刪除指定節點之后的節點
void SLTEraseAfter(SLT* pos)
{assert(pos&&pos->next);//pos->next:處理當pos是最后一個節點的情況SLT* std = pos->next;SLT* later = std->next;free(std);std = NULL;pos->next = later;
}

13、銷毀鏈表

斷言，是否傳了空指針，鏈表是否為空；然后遍歷鏈表，逐個釋放。

//銷毀鏈表中的所有節點
void SLTDestry(SLT** pphead)
{assert(pphead && *pphead);SLT* std = *pphead;while (std){//記錄要銷毀節點的下一個節點，防止釋放而找不到SLT* next = std->next;free(std);std = next;}*pphead = NULL;
}

四、單鏈表實現完整代碼

SList.c

#include"SList.h"//打印單鏈表
void PrintSLT(SLT* phead)
{SLT* pcur = phead;while (pcur){printf("%d->", pcur->val);pcur = pcur->next;}
}//創建新節點
SLT* BuyNode(DateType x)
{SLT* newnode = (SLT*)malloc(sizeof(SLT));if (newnode == NULL){perror("malloc");exit(1);}newnode->val = x;newnode->next = NULL;return newnode;
}//鏈表尾插
void SLTpushBack(SLT** pphead, DateType x)
{//斷言pphead不能為NULL，不能對空指針解引用assert(pphead);//創建新節點SLT* newnode = BuyNode(x);//處理空鏈表if (*pphead == NULL){*pphead = newnode;}//處理非空鏈表else{SLT* pcur = *pphead;while (pcur->next)//找尾節點{pcur = pcur->next;}pcur->next = newnode;}
}//鏈表頭插
void SLTpushFront(SLT** pphead, DateType x)
{assert(pphead);SLT* newnode = BuyNode(x);SLT* pcur = *pphead;newnode->next = pcur;*pphead = newnode;
}//鏈表尾刪
void SLTpopBack(SLT** pphead)
{//斷言assert(pphead && *pphead);//只有一個節點if ((*pphead)->next == NULL){free(*pphead);//釋放*pphead = NULL;}//不止一個節點else{SLT* pcur = *pphead;SLT* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);//釋放pcur = NULL;prev->next = NULL;}
}//鏈表頭刪
void SLTpopFront(SLT** pphead)
{//斷言assert(pphead && *pphead);SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}//鏈表的查找
SLT* SLTFind(SLT* phead, DateType x)
{assert(phead);SLT* pcur = phead;while (pcur){if (pcur -> val == x){return pcur;}pcur = pcur->next;}return NULL;
}//在鏈表的指定位置之前插入一個新的節點
void SLTInsert(SLT** pphead, SLT* pos, DateType x)
{assert(pphead && *pphead);assert(pos);SLT* newnode = BuyNode(x);//找pos節點之前的節點SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//連接prev,newnode,posprev->next = newnode;newnode->next = pos;
}
//在鏈表的指定位置之后插入一個新的節點
void SLTInsertAfter(SLT* pos, DateType x)
{assert(pos);SLT* newnode = BuyNode(x);SLT* pback = pos->next;//連接pos,newnode,pbackpos->next = newnode;newnode->next = pback;
}//刪除指定節點
void SLTErase(SLT** pphead, SLT* pos)
{assert(pphead && *pphead);assert(pos);//指定節點為第一個節點if (*pphead == pos){SLT* pcur = (*pphead)->next;free(*pphead);*pphead = pcur;}else{SLT* prev = *pphead;while (prev->next != pos){prev = prev->next;}//先連接pos節點的前一個節點與pos的后一個節點prev->next = pos->next;free(pos);pos = NULL;}
}//刪除指定節點之后的節點
void SLTEraseAfter(SLT* pos)
{assert(pos && pos->next);//pos->next:處理當pos是最后一個節點的情況SLT* std = pos->next;SLT* later = std->next;free(std);std = NULL;pos->next = later;
}//銷毀鏈表中的所有節點
void SLTDestry(SLT** pphead)
{assert(pphead && *pphead);SLT* std = *pphead;while (std){//記錄要銷毀節點的下一個節點，防止釋放而找不到SLT* next = std->next;free(std);std = next;}*pphead = NULL;
}

test.c?

#include"SList.h"void test01()
{SLT* s1 = (SLT*)malloc(sizeof(SLT));SLT* s2 = (SLT*)malloc(sizeof(SLT));SLT* s3 = (SLT*)malloc(sizeof(SLT));s1->val = 1;s2->val = 2;s3->val = 3;s1->next = s2;s2->next = s3;s3->next = NULL;PrintSLT(s1);//打印//SLTpopBack(&s1);//尾刪//SLTpopFront(&s1);//頭刪//SLTpopFront(&s1);//頭刪printf("\n");//PrintSLT(s1);SLT*ret = SLTFind(s1, 2);//查找//printf("%d\n", ret->val);//SLTInsert(&s1, ret, 4);//指定位置之前插入//PrintSLT(s1);//SLTInsertAfter(ret, 4);//指定位置之后插入//PrintSLT(s1);//刪除指定節點SLTErase(&s1, ret);PrintSLT(s1);
}void test02()
{SLT* s1 = (SLT*)malloc(sizeof(SLT));SLT* s2 = (SLT*)malloc(sizeof(SLT));s1->val = 1;s2->val = 2;s1->next = s2;s2->next = NULL;SLT* plist = s1;SLTpushFront(&plist, 3);//頭插PrintSLT(plist);
}void test03()
{SLT* plist = NULL;//SLTpushBack(&plist, 1);//尾插//SLTpushFront(&plist, 1);//頭插//SLTpopBack(&plist);//尾刪PrintSLT(plist);
}
int main()
{test01();//test02();//test03();return 0;
}

五、手動實現雙向鏈表

根據前面的分類，雙向鏈表即帶頭雙向循環鏈表

先展示頭文件

LTNode.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>#define DateType int
//創建雙向鏈表：帶頭雙向循環鏈表
typedef struct LTNode
{DateType date;struct LTNode* prev;struct LTNode* next;
}LTNode;//初始化
void LTInit(LTNode**pphead);
//創建雙向鏈表中的節點
LTNode* BuyNode(DateType x);
//打印雙向鏈表
void PrintLT(LTNode* phead);
//雙向鏈表尾插
void LTPushBack(LTNode* phead, DateType x);
//頭插
void LTPushFront(LTNode* phead, DateType x);
//尾刪
void LTPopBack(LTNode* phead);
//頭刪
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, DateType x);
//指定位置之后插入
void LTInsert(LTNode* pos, DateType x);
//刪除指定位置的節點
void LTEarse(LTNode* pos);
//銷毀
void LTDestry(LTNode* phead);/*所有傳的都是一級指針，保證了接口的一致性，降低了記憶的成本*/

1、定義雙向鏈表的一個節點

雙向鏈表中有一個存儲Dateype類型的數據的變臉，一個用來指向下一個節點的指針next，還有一個用來指向上一個節點的指針prev。

typedef int DateType;
//定義雙向鏈表（帶頭雙向循環鏈表）的一個節點
typedef struct LTNode
{DateType date;struct LTNode* prev;//指向前一個節點struct LTNode* next;//指向后一個節點
}LTNode;

2、創建新節點

想要實現雙向鏈表的初始化，尾插，頭插以及指定位置插入數據，就避免不了要創建新的節點。由于鏈表再存儲結構上非連續，所以我們用malloc來動態申請內存空間，然后賦值，改變兩個指針的指向，使其形成自循環，最后將新節點的地址返回。

//創建雙向鏈表中的節點
LTNode* BuyNode(DateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->date = x;newnode->prev = newnode->next = newnode;return newnode;
}

3、雙向鏈表的初始化

雙向鏈表是帶頭鏈表，所以對雙向鏈表初始化即對頭節點（哨兵位）初始化。由于哨兵位不存儲有效數據，一般將date初始化為-1，然后，改變兩個指針的指向，使其形成自循環，即直接調用創建新節點的函數。

//初始化
void LTInit(LTNode** pphead)
{*pphead = BuyNode(-1);
}

4、打印

打印則要遍歷雙向鏈表，同時，要打印的是雙向鏈表的有效節點。因此，用一個pcur指針指向頭節點的下一個節點，由于是雙向鏈表，遍歷時的結束條件就應該是pcur != phead。

//打印雙向鏈表
void PrintLT(LTNode* phead)
{//pcur指向第一個有效節點LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->date);pcur = pcur->next;}
}

5、尾插

先要找到雙向鏈表的尾節點。即phead->prev。

然后連接新節點與原來的尾節點：

phead->prev->next=newnode，newnode->prev=phead->prev；

最后連接頭節點與新節點：

phead->prev=newnode，newnode->next=phead；

注意連接的順序，不然會改變phead->prev的指向。

//雙向鏈表尾插
void LTPushBack(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//連接原來的尾節點與新節點phead->prev->next = newnode;newnode->prev = phead->prev;//連接頭節點與新節點phead->prev = newnode;newnode->next = phead;
}

6、頭插

頭插是指插入到第一個有效節點之前。找到第一個有效節點，然后連接頭節點，新節點與第一個節點。注意：phead->next的連接順序，防止改變這種指向。

//頭插
void LTPushFront(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//連接新節點與原來第一個與有效節點newnode->next = phead->next;phead->next->prev = newnode;//連接頭節點與新節點phead->next = newnode;newnode->prev = phead;
}

7、尾刪

（1）斷言：排除傳過來NULL和空鏈表（只有一個頭節點）的情況；

（2）找到尾節點：phead->prev；再順藤摸瓜找到尾節點的前一個節點：phead->prev->prev

（3）連接頭節點與新的尾節點，即phead與phead->prev->prev；注意：連接順序

（4）釋放尾節點。

//尾刪
void LTPopBack(LTNode* phead)
{//排除傳過來NULL和空鏈表（只有一個頭節點）的情況assert(phead && phead->next != phead);LTNode* del = phead->prev;//尾節點//尾節點的前一個節點：del->prev//連接尾節點的前一個節點與頭節點del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

8、頭刪

刪除第一個有效節點。

（1）斷言：排除傳過來NULL和空鏈表（只有一個頭節點）的情況；

（2）找到第一個有效節點：phead->next；第一個有效節點之后的節點：phead->next->next；

（3）連接頭節點與第一個有效節點之后的節點，即連接phead與phead->next->next；注意：連接順序

（4）釋放第一個有效節點。

//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//第一個有效節點//第一個有效節點之后的節點;del->next//連接頭節點與第一個有效節點之后的節點del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

9、查找

?查找則要遍歷雙向鏈表，且要查找的是雙向鏈表的有效節點。因此，斷言排除傳過來NULL和只有一個頭節點，然后，用一個pcur指針指向頭節點的下一個節點，由于是雙向鏈表，遍歷時的結束條件就應該是pcur != phead。

//查找
LTNode* LTFind(LTNode* phead, DateType x)
{assert(phead && phead->next != phead);LTNode* std = phead->next;//讓std指針指向第一個有效節點//遍歷while (std != std->next){if (std->date == x){return std;}std = std->next;}return NULL;
}

10、指定位置之后插入

先找到指定位置之后的節點：pos->next；然后。連接pos節點，新節點newnode與指定位置之后的節點pos->next。注意：連接順序，防止改變pos->next的指向。

//指定位置之后插入
void LTInsert(LTNode* pos, DateType x)
{LTNode* newnode = BuyNode(x);//指定位置之后的節點：pos->next//連接新節點與原來指定位置之后的節點newnode->next = pos->next;pos->next->prev = newnode;//連接新節點與指定位置的節點pos->next = newnode;newnode->prev = pos;
}

11、刪除指定位置的節點

現在的指定位置節點之前的節點：pos->prev；指定位置之后的節點：pos->next。然后，連接pos->prev與pos->next。最后，釋放指定位置節點。

//刪除指定位置的節點
void LTEarse(LTNode* pos)
{//指定位置之后的節點：pos->next//指定位置之前的節點：pos->prev//連接指定位置之后的節點與指定位置之前的節點pos->prev->next = pos->next;pos->next->prev = pos->prev;//刪除pos節點free(pos);pos = NULL;
}

12、銷毀

先找到第一個有效節點std，然后用std指針遍歷鏈表，逐個節點釋放，但在釋放結構之前需要記下該節點的下一個節點，防止因為釋放而找不到，到不到銷毀整個鏈表的效果。最后將頭節點釋放。

//銷毀
void LTDestry(LTNode* phead)
{assert(phead);LTNode* std = phead->next;//讓std指針指向第一個有效節點while (std != std->next){LTNode* next = std->next;//保證在std被釋放后，std的下一個節點還能找到free(std);std = next;//下一個節點}//釋放哨兵位free(phead);phead = NULL;
}

?六、雙向鏈表完整源碼

LTNode.c

#include"LTNode.h"
//初始化
void LTInit(LTNode** pphead)
{*pphead = BuyNode(-1);
}//創建雙向鏈表中的節點
LTNode* BuyNode(DateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->date = x;newnode->prev = newnode->next = newnode;return newnode;
}//打印雙向鏈表
void PrintLT(LTNode* phead)
{//pcur指向第一個有效節點LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->date);pcur = pcur->next;}
}//雙向鏈表尾插
void LTPushBack(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//連接原來的尾節點與新節點phead->prev->next = newnode;newnode->prev = phead->prev;//連接頭節點與新節點phead->prev = newnode;newnode->next = phead;
}//頭插
void LTPushFront(LTNode* phead, DateType x)
{LTNode* newnode = BuyNode(x);//連接新節點與原來第一個與有效節點newnode->next = phead->next;phead->next->prev = newnode;//連接頭節點與新節點phead->next = newnode;newnode->prev = phead;
}	//尾刪
void LTPopBack(LTNode* phead)
{//排除傳過來NULL和空鏈表（只有一個頭節點）的情況assert(phead && phead->next != phead);LTNode* del = phead->prev;//尾節點//尾節點的前一個節點：del->prev//連接尾節點的前一個節點與頭節點del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//第一個有效節點//第一個有效節點之后的節點;del->next//連接頭節點與第一個有效節點之后的節點del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, DateType x)
{assert(phead && phead->next != phead);LTNode* std = phead->next;//讓std指針指向第一個有效節點//遍歷while (std != std->next){if (std->date == x){return std;}std = std->next;}return NULL;
}//指定位置之后插入
void LTInsert(LTNode* pos, DateType x)
{LTNode* newnode = BuyNode(x);//指定位置之后的節點：pos->next//連接新節點與原來指定位置之后的節點newnode->next = pos->next;pos->next->prev = newnode;//連接新節點與指定位置的節點pos->next = newnode;newnode->prev = pos;
}
//刪除指定位置的節點
void LTEarse(LTNode* pos)
{//指定位置之后的節點：pos->next//指定位置之前的節點：pos->prev//連接指定位置之后的節點與指定位置之前的節點pos->prev->next = pos->next;pos->next->prev = pos->prev;//刪除pos節點free(pos);pos = NULL;
}
//銷毀
void LTDestry(LTNode* phead)
{assert(phead);LTNode* std = phead->next;//讓std指針指向第一個有效節點while (std != std->next){LTNode* next = std->next;//保證在std被釋放后，std的下一個節點還能找到free(std);std = next;//下一個節點}//釋放哨兵位free(phead);phead = NULL;
}

test.c?

#include"LTNode.h"
void test01()
{LTNode* plist = NULL;LTInit(&plist);//初始化//LTPushBack(plist, 4);//尾插//LTPushFront(plist, 4);//頭插//LTPopBack(plist);//尾刪LTPopFront(plist);PrintLT(plist);
}
void test02()
{LTNode* s = NULL;LTInit(&s);LTNode* s1 = (LTNode*)malloc(sizeof(LTNode));LTNode* s2 = (LTNode*)malloc(sizeof(LTNode));LTNode* s3 = (LTNode*)malloc(sizeof(LTNode));s1->date = 1;s2->date = 2;s3->date = 3;//連接s->next = s1;s->prev = s3;s1->prev = s;s1->next = s2;s2->prev = s1;s2->next = s3;s3->prev = s2;s3->next = s;PrintLT(s);//打印printf("\n");//LTPushBack(s, 4);//尾插//LTPushFront(s,4);//頭插//LTPopBack(s);//尾刪//LTPopFront(s);//頭刪LTNode* ret = LTFind(s, 2);//查找//printf("%d\n", ret->date);//LTInsert(ret, 4);//指定位置之后插入LTEarse(ret);PrintLT(s);
}
int main()
{//test01();test02();return 0;
}