目录

概念

带头双向循环链表的实现

前情提示

双向链表的结构体定义

双向链表的初始化

关于无头单向非循环链表无需初始化函数，顺序表、带头双向循环链表需要的思考

双向链表在pos位置之前插入x

双向链表的打印

双链表删除pos位置的结点

双向链表的尾插

关于单链表的尾插需要用到二级指针，双向链表不需要用到二级指针的思考

双向链表的判空

双向链表的尾删

双向链表的头插

双向链表的头删

双向链表查找值为x的结点

双向链表的销毁

双向链表的修改

双向链表删除值为x的结点

双向链表计算结点总数(不计phead)

双向链表获取第i位置的结点

双向链表的清空

总代码（想直接看结果的可以看这里）

概念

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。我们一般构造双向循环链表。循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其它结点。

带头双向循环链表的实现

前情提示

List.h用于 引用的头文件、双向链表的定义、函数的声明。

List.c 用于 函数的定义。

Test.c用于 双向链表功能的测试。

双向链表的结构体定义

在List.h下

#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突//先将可能使用到的头文件写上#include#include#include#includetypedef int LTDataType;//假设结点的数据域类型为 int//给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动//（比如我晚点想存double类型的数据，我就直接将 int 改为 double )// 带哨兵位双向循环链表的结构体定义typedef struct ListNode{struct ListNode* prev;//前驱指针域:存放上一个结点的地址struct ListNode* next;//后继指针域:存放下一个结点的地址LTDataType data;//数据域}LTNode;//struct 关键字和 ListNode 一起构成了这个结构类型//typedef 为这个结构起了一个别名,叫 LTNode,即：typedef struct ListNode LTNode //现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量

双向链表的初始化

在List.h下

// 双向链表的初始化// 如果是单链表直接给个空指针就行，不需要单独写一个函数进行初始化// 即：LTNode* plist = NULL;// 那为什么顺序表、带头双向循环链表有呢？// 因为顺序表、带头双向循环链表的结构并不简单，// 如:顺序表顺序表为空size要为0,还要看capacity是否要开空间,// 若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功//带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己// 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数LTNode* LTInit();

在List.c下

#include"List.h"//别忘了//动态申请一个结点LTNode* BuyListNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL)//如果malloc失败{perror("malloc fail");return NULL;}//如果malloc成功//初始化一下，防止野指针，如果看到返回的是空指针，那逻辑可能有些错误node->next = NULL;node->prev = NULL;node->data = x;return node;}// 双向链表的初始化LTNode* LTInit(){LTNode* phead = BuyListNode(-1);//创建哨兵位//自己指向自己phead->next = phead;phead->prev = phead;return phead;}

关于无头单向非循环链表无需初始化函数，顺序表、带头双向循环链表需要的思考

无头单向非循环链表结构太简单了，初始化只需直接赋空指针，无需单独写一个函数进行初始化。

即：LTNode* plist = NULL;

那为什么顺序表、带头双向循环链表有单独写一个函数进行初始化呢？
因为顺序表、带头双向循环链表的结构并不简单。
如:

顺序表顺序表为空size要为0,还要看capacity是否要开空间,若不开空间capacity=0,指针要给空，若开空间,还要检查malloc是否成功。

带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己。

顺序表和双向循环链表的初始化有点复杂,最好构建一个函数。

双向链表在pos位置之前插入x

在List.h下

// 双向链表在pos位置之前进行插入void LTInsert(LTNode* pos, LTDataType x);

在List.c下

// 双向链表在pos位置之前进行插入void LTInsert(LTNode* pos, LTDataType x){assert(pos);//pos肯定不为空LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}

双向链表的打印

在List.h下

// 双向链表打印void LTPrint(LTNode* phead);

在List.c下

// 双向链表打印void LTPrint(LTNode* phead){assert(phead);//有哨兵位printf("phead");LTNode* cur = phead->next;//cur指向第一个要打印的结点while (cur != phead)//cur等于头结点时打印就结束了{printf("%d", cur->data);cur = cur->next;}printf("\n");}

在Test.c下

#include"List.h"//别忘了//测试函数void TestList1(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);}int main(){TestList1();return 0;}

双链表删除pos位置的结点

在List.h下

// 双向链表删除pos位置的结点void LTErase(LTNode* pos);

在List.c下

// 双向链表删除pos位置的结点void LTErase(LTNode* pos){assert(pos);//pos肯定不为空LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);pos = NULL;//这个置空其实已经没有意义了，形参的改变不会改变实参}

在Test.c下

//测试函数void TestList1(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);LTErase(plist->next);LTPrint(plist);}int main(){TestList1();return 0;}

双向链表的尾插

在List.h下

//双向链表优于单链表的点——不需要找尾、二级指针//（我们改的不是结构体的指针，改的是结构体的变量）// 双向链表的尾插void LTPushBack(LTNode* phead, LTDataType x);

在List.c下

法一:（便于新手更好地理解双向链表的尾插）

// 双向链表的尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);//有哨兵位//法一:(便于新手更好地理解双向链表的尾插)//一步就可完成链表为空/不为空的尾插——因为有哨兵位LTNode* newnode = BuyListNode(x);//创建一个要插入的结点LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

法二：函数复用（简单方便）

// 双向链表的尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);//有哨兵位//法二:函数复用（简单方便）LTInsert(phead, x);}

关于单链表的尾插需要用到二级指针，双向链表不需要用到二级指针的思考

单链表改变的是结构体的指针，双向链表改变的是结构体的变量

二级指针和一级指针的区别在于指针所指向变量的层级不同，一级指针指向的是结构体的变量，而二级指针指向的是结构体指针的地址。
单链表中，在进行链表结点的删除或插入操作时，需要更新结点之间的指针指向。若使用一级指针，则操作会直接改变指向结点的指针，很难实现目标。因此需要传递二级指针，让函数能够修改指向结点指针的地址，也就是修改之前结点指针变量存放的地址。
而双向链表中，每个结点除了保存指向下一结点的指针外，还有保存指向上一结点的指针，结点之间的双向指针关系使得结点的插入和删除操作更加方便。双向链表不需要传递二级指针，因为在结点的删除和插入操作中，只需要先修改当前结点前后结点的指针，无需直接改变前后结点指针变量存放的地址。
综上所述，单链表只有指向下一结点的指针，通过传递二级指针来修改结点之间的指针关系，使得操作更加灵活；而双向链表的结点之间有双向指针关系，无需直接改变前后结点指针变量存放的地址，因此只需要传递一级指针即可。

单链表（对比）：

在Test.c下

//测试函数void TestList2(){LTNode* plist = LTInit();LTPushBack(plist, 5);LTPushBack(plist, 6);LTPushBack(plist, 7);LTPushBack(plist, 8);LTPrint(plist);}int main(){TestList2();return 0;}

双向链表的判空

在尾删/头删之前，我们要先判断链表是否为空。

在List.h下

// 双向链表的判空bool LTEmpty(LTNode* phead);

在List.c下

// 双向链表的判空bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;//两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)}

双向链表的尾删

在List.h下

// 双向链表的尾删void LTPopBack(LTNode* phead);

在List.c下

法一：（便于新手更好地理解双向链表的尾删）

// 双向链表的尾删void LTPopBack(LTNode* phead){assert(phead);//有哨兵位assert(!LTEmpty(phead));//判空//法一：（便于新手更好地理解双向链表的尾删）LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL;}

法二：函数复用（简单方便）

// 双向链表的尾删void LTPopBack(LTNode* phead){assert(phead);//有哨兵位assert(!LTEmpty(phead));//判空//法二:函数复用LTErase(phead->prev);}

在Test.c下

//测试函数void TestList2(){LTNode* plist = LTInit();LTPushBack(plist, 5);LTPushBack(plist, 6);LTPushBack(plist, 7);LTPushBack(plist, 8);LTPrint(plist);LTPopBack(plist);LTPopBack(plist);LTPrint(plist);}int main(){TestList2();return 0;}

双向链表的头插

在List.h下

// 双向链表头插void LTPushFront(LTNode* phead, LTDataType x);

在List.c下

法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）

// 双向链表头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);//有哨兵位LTNode* newnode = BuyListNode(x);//创建一个要插入的结点//法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）//顺序很重要！！！newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;}

法二:多用了first记录第一个结点的位置（便于新手更好地理解双向链表的头插）

// 双向链表头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);//哨兵位LTNode* newnode = BuyListNode(x);//创建一个要插入的结点//法二：多用了first先记住第一个结点（便于新手更好地理解双向链表的头插）LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

法三:函数复用（简单方便）

// 双向链表头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);//有哨兵位//法三:函数复用（简单方便）LTInsert(phead->next, x);}

在Test.c下

//测试函数void TestList3(){LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);}int main(){TestList3();return 0;}

双向链表的头删

在List.h下

// 双向链表头删void LTPopFront(LTNode* phead);

在List.c下

法一:（便于新手更好地理解双向链表的头删）

// 双向链表头删void LTPopFront(LTNode* phead){assert(phead);//有哨兵位assert(!LTEmpty(phead));//判空//法一:（便于新手更好地理解双向链表的头删）LTNode* head = phead->next;LTNode* headnext = head->next;phead->next = headnext;headnext->prev = phead;free(head);head = NULL;}

法二:函数复用（简单方便）

// 双向链表头删void LTPopFront(LTNode* phead){assert(phead);//有哨兵位assert(!LTEmpty(phead));//判空//法二:函数复用（简单方便）LTErase(phead->next);}

在Test.c下

//测试函数void TestList3(){LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);}int main(){TestList3();return 0;}

双向链表查找值为x的结点

在List.h下

// 双向链表查找值为x的结点LTNode* LTFind(LTNode* phead, LTDataType x);

在List.c下

// 双向链表查找值为x的结点LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);//有哨兵位LTNode* cur = phead->next;while (cur != phead)//让cur去遍历{if (cur->data == x)//如果找到{return cur;}cur = cur->next;}return NULL;//如果没找到}

在Test.c下

//测试函数TestList4(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);}int main(){TestList4();return 0;}

双向链表的销毁

在List.h下

// 双向链表的销毁void LTDestory(LTNode* phead);

在List.c下

// 双向链表的销毁void LTDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;//让cur遍历while (cur != phead){LTNode* curnext = cur->next;free(cur);cur = curnext;}free(phead);phead = NULL;//这个置空其实已经没有意义了，形参的改变不会改变实参//我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空}

在Test.c下

//测试函数TestList4(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);LTDestory(plist);plist = NULL;//在这里置空}

双向链表的修改

在List.h下

// 双向链表的修改,修改pos位置的值为xvoid LTModify(LTNode* pos, LTDataType x);

在List.c下

// 双向链表的修改,修改pos位置的值为xvoid LTModify(LTNode* pos, LTDataType x){assert(pos);pos->data = x;}

在Test.c下

//测试函数TestList5(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);LTModify(plist->next,5);LTPrint(plist);}int main(){TestList5();return 0;}

双向链表删除值为x的结点

在List.h下

// 双向链表删除值为x的结点void LTRemove(LTNode* phead,LTDataType x);

在List.c下

// 双向链表删除值为x的结点void LTRemove(LTNode* phead, LTDataType x){assert(phead);//有哨兵位LTNode* pos = phead->next;while (pos != phead){pos = LTFind(phead, x);if (pos == NULL)//如果遍历完{return NULL;}LTErase(pos);pos = pos->next;}}

在Test.c下

TestList6(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 3);LTInsert(plist, 3);LTInsert(plist, 4);LTInsert(plist, 3);LTPrint(plist);LTRemove(plist, 3);LTPrint(plist);}int main(){TestList6();return 0;}

双向链表计算结点总数(不计phead)

在List.h下

// 双向链表计算结点总数(不计phead)int LTTotal(LTNode* phead);

在List.c下

// 双向链表计算结点总数(不计phead)int LTTotal(LTNode* phead){assert(phead);//有哨兵位int count = 0;//count来计数LTNode* cur = phead->next;//让cur去遍历while (cur != phead){count++;cur = cur->next;}return count;}

在Test.c下

TestList6(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 3);LTInsert(plist, 3);LTInsert(plist, 4);LTInsert(plist, 3);LTPrint(plist);LTRemove(plist, 3);LTPrint(plist);printf("%d\n", LTTotal(plist));}int main(){TestList6();return 0;}

双向链表获取第i位置的结点

在List.h下

// 双向链表获取第i位置的结点LTNode* LTGet(LTNode* phead, int i);

在List.c下

// 双向链表获取第i位置的结点LTNode* LTGet(LTNode* phead, int i){assert(phead);//有哨兵位int length = LTTotal(phead);LTNode* cur = phead->next;if (i == 0){return phead;}else if (ilength)//位置不合法{return NULL;}else if (i next;for (int count = 1; count next;}}else//从表尾开始遍历{cur = phead->prev;for (int count = 1; count prev;}}return cur;}

在Test.c下

//测试函数TestList7(){LTNode* plist = LTInit();LTInsert(plist, 5);LTInsert(plist, 6);LTInsert(plist, 7);LTInsert(plist, 8);LTInsert(plist, 9);LTPrint(plist);LTNode* pos = LTGet(plist,3);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);}int main(){TestList7();return 0;}

双向链表的清空

在List.h下

// 双向链表的清空void LTClean(LTNode* phead);

在List.c下

// 双向链表的清空void LTClear(LTNode* phead){assert(phead);//有哨兵位while (!LTEmpty(phead))//如果不为空就一直头删{LTPopFront(phead);}}

在Test.c下

//测试函数TestList8(){LTNode* plist = LTInit();LTInsert(plist, 5);LTInsert(plist, 6);LTInsert(plist, 7);LTInsert(plist, 8);LTInsert(plist, 9);LTPrint(plist);LTClear(plist);LTPrint(plist);}int main(){TestList8();return 0;}

总代码（想直接看结果的可以看这里）

在List.h下

#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突//先将可能使用到的头文件写上#include#include#include#includetypedef int LTDataType;//假设结点的数据域类型为 int//给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动//（比如我晚点想存double类型的数据，我就直接将 int 改为 double )// 带哨兵位双向循环链表的结构体定义typedef struct ListNode{struct ListNode* prev;//前驱指针域:存放上一个结点的地址struct ListNode* next;//后继指针域:存放下一个结点的地址LTDataType data;//数据域}LTNode;//struct 关键字和 ListNode 一起构成了这个结构类型//typedef 为这个结构起了一个别名,叫 LTNode,即：typedef struct ListNode LTNode //现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量// 双向链表的初始化// 如果是单链表直接给个空指针就行，不需要单独写一个函数进行初始化// 即：LTNode* plist = NULL;// 那为什么顺序表、带头双向循环链表有呢？// 因为顺序表、带头双向循环链表的结构并不简单，// 如:顺序表顺序表为空size要为0,还要看capacity是否要开空间,//若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功// 带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己// 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数LTNode* LTInit();// 双向链表在pos位置之前进行插入xvoid LTInsert(LTNode* pos, LTDataType x);// 双向链表的打印void LTPrint(LTNode* phead);// 双向链表删除pos位置的结点void LTErase(LTNode* pos);//双向链表优于单链表的点——不需要找尾、二级指针// （我们改的不是结构体的指针，改的是结构体的变量）// 双向链表的尾插void LTPushBack(LTNode* phead, LTDataType x);// 双向链表的判空bool LTEmpty(LTNode* phead);// 双向链表的尾删void LTPopBack(LTNode* phead);// 双向链表头插void LTPushFront(LTNode* phead, LTDataType x);// 双向链表头删void LTPopFront(LTNode* phead);// 双向链表查找值为x的结点LTNode* LTFind(LTNode* phead, LTDataType x);// 双向链表的销毁void LTDestory(LTNode* phead);// 双向链表的修改,修改pos位置的值为xvoid LTModify(LTNode* pos, LTDataType x);// 双向链表删除值为x的结点void LTRemove(LTNode* phead, LTDataType x);// 双向链表计算结点总数(不计phead)int LTTotal(LTNode* phead);// 双向链表获取第i位置的结点LTNode* LTGet(LTNode* phead, int i);// 双向链表的清空void LTClear(LTNode* phead);

在List.c下

#include"List.h"//动态申请一个结点LTNode* BuyListNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL)//如果malloc失败{perror("malloc fail");return NULL;}//如果malloc成功//初始化一下，防止野指针，如果看到返回的是空指针，那逻辑可能有些错误node->next = NULL;node->prev = NULL;node->data = x;return node;}// 双向链表的初始化LTNode* LTInit(){LTNode* phead = BuyListNode(-1);//自己指向自己phead->next = phead;phead->prev = phead;return phead;}// 双向链表在pos位置之前进行插入xvoid LTInsert(LTNode* pos, LTDataType x){assert(pos);//pos肯定不为空LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}// 双向链表的打印void LTPrint(LTNode* phead){assert(phead);//有哨兵位printf("phead");LTNode* cur = phead->next;//cur指向第一个要打印的结点while (cur != phead)//cur等于头结点时打印就结束了{printf("%d", cur->data);cur = cur->next;}printf("\n");}// 双向链表删除pos位置的结点void LTErase(LTNode* pos){assert(pos);//pos肯定不为空LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);pos = NULL;//这个置空其实已经没有意义了，形参的改变不会改变实参}// 双向链表的尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);//有哨兵位//法一:（便于新手更好地理解双向链表的尾插）//一步就可完成链表为空/不为空的尾插//LTNode* newnode = BuyListNode(x);//LTNode* tail = phead->prev;//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead;//phead->prev = newnode;//法二:函数复用（简单方便）LTInsert(phead, x);}// 双向链表的判空bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;//两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)}// 双向链表的尾删void LTPopBack(LTNode* phead){assert(phead);//有哨兵位//法一:（便于新手更好地理解双向链表的尾删）//assert(!LTEmpty(phead));//判空//LTNode* tail = phead->prev;//LTNode* tailPrev = tail->prev;//tailPrev->next = phead;//phead->prev = tailPrev;//free(tail);//tail = NULL;//法二:函数复用LTErase(phead->prev);}// 双向链表头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);//有哨兵位//LTNode* newnode = BuyListNode(x);//创建一个要插入的结点//法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）//newnode->next = phead->next;//phead->next->prev = newnode;//phead->next = newnode;//newnode->prev = phead;//法二:多用了first先记住第一个结点（便于新手更好地理解双向链表的头插）//LTNode* first = phead->next;//phead->next = newnode;//newnode->prev = phead;//newnode->next = first;//first->prev = newnode;//法三:函数复用(简单方便)LTInsert(phead->next, x);}// 双向链表头删void LTPopFront(LTNode* phead){assert(phead);//有哨兵位assert(!LTEmpty(phead));//判空//法一:（便于新手更好地理解双向链表的头删）//LTNode* head = phead->next;//LTNode* headnext = head->next;//phead->next = headnext;//headnext->prev = phead;//free(head);//head = NULL;//法二:函数复用（简单方便）LTErase(phead->next);}// 双向链表查找值为x的结点LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);//有哨兵位LTNode* cur = phead->next;while (cur != phead)//让cur去遍历{if (cur->data == x){return cur;}cur = cur->next;}return NULL;}// 双向链表的销毁void LTDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* curnext = cur->next;free(cur);cur = curnext;}free(phead);phead = NULL;//这个置空其实已经没有意义了，形参的改变不会改变实参//我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空}// 双向链表的修改,修改pos位置的值为xvoid LTModify(LTNode* pos, LTDataType x){assert(pos);//pos肯定不为空pos->data = x;}// 双向链表删除值为x的结点void LTRemove(LTNode* phead, LTDataType x){assert(phead);//有哨兵位LTNode* pos = phead->next;while (pos != phead){pos = LTFind(phead, x);if (pos == NULL)//如果遍历完{return NULL;}LTErase(pos);pos = pos->next;}}// 双向链表计算结点总数(不计phead)int LTTotal(LTNode* phead){assert(phead);//有哨兵位int count = 0;//count来计数LTNode* cur = phead->next;//让cur去遍历while (cur != phead){count++;cur = cur->next;}return count;}// 双向链表获取第i位置的结点LTNode* LTGet(LTNode* phead, int i){assert(phead);//有哨兵位int length = LTTotal(phead);LTNode* cur = phead->next;if (i == 0){return phead;}else if (ilength)//位置不合法{return NULL;}else if (i next;for (int count = 1; count next;}}else//从表尾开始遍历{cur = phead->prev;for (int count = 1; count prev;}}return cur;}// 双向链表的清空void LTClear(LTNode* phead){assert(phead);//有哨兵位while (!LTEmpty(phead))//如果不为空就一直头删{LTPopFront(phead);}}

在Test.c下

#include"List.h"//测试函数void TestList1(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);LTErase(plist->next);LTPrint(plist);}//测试函数void TestList2(){LTNode* plist = LTInit();LTPushBack(plist, 5);LTPushBack(plist, 6);LTPushBack(plist, 7);LTPushBack(plist, 8);LTPrint(plist);LTPopBack(plist);LTPopBack(plist);LTPrint(plist);}//测试函数void TestList3(){LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);}//测试函数TestList4(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);LTDestory(plist);plist = NULL;//在这里置空}//测试函数TestList5(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 2);LTInsert(plist, 3);LTInsert(plist, 4);LTPrint(plist);LTModify(plist->next, 5);LTPrint(plist);}TestList6(){LTNode* plist = LTInit();LTInsert(plist, 1);LTInsert(plist, 3);LTInsert(plist, 3);LTInsert(plist, 4);LTInsert(plist, 3);LTPrint(plist);LTRemove(plist, 3);LTPrint(plist);printf("%d\n", LTTotal(plist));}//测试函数TestList7(){LTNode* plist = LTInit();LTInsert(plist, 5);LTInsert(plist, 6);LTInsert(plist, 7);LTInsert(plist, 8);LTInsert(plist, 9);LTPrint(plist);LTNode* pos = LTGet(plist, 3);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);LTClear(plist);LTPrint(plist);}//测试函数TestList8(){LTNode* plist = LTInit();LTInsert(plist, 5);LTInsert(plist, 6);LTInsert(plist, 7);LTInsert(plist, 8);LTInsert(plist, 9);LTPrint(plist);LTClear(plist);LTPrint(plist);}int main(){//TestList1();//TestList2();//TestList3();//TestList4();//TestList5();//TestList6();//TestList7();TestList8();return 0;}

欢迎指正❀