双向链表专题

在学习完单链表后我们学习双向链表实际上更加容易。1.链表的结构链表的结构非常多样以下情况组合起来就有八种链表结构。1.1带头或不带头这里的带头指的是链表中有哨兵位节点该哨兵位节点即为头节点。前面我们实现单链表时https://blog.csdn.net/gumidc/article/details/159473875?spm1011.2124.3001.6209口头上提到的头节点实际上指的是第一个有效节点这并不是正确的称呼实际在链表中头节点指的是哨兵位。所以我们之前学的单链表实际上是不带头的。1.2单向或双向单向链表只能从一个方向遍历。双向链表可以从两个方向遍历。1.3循环或不循环判断链表是否循环要看尾节点的next指针是否为空。我们到这里就可以知道我们之前实现的单链表就是不带头单向不循环链表。而带头双向循环链表简称为双向链表。2.双向链表的初始化首先依旧创建三个文件List.hList.ctest.c。接下来我们在List.h中定义双向链表的节点由下图可知双向链表的节点是由数据指向下一个节点的指针指向前一个节点的指针构成的。所以代码如下注意单链表和双向链表为空时它们内部的结构是不一样的如下图所以写双向链表代码时我们必须先要完成哨兵位的初始化然后才能对链表执行增删查改等操作。由于我们要在原链表的基础上创建哨兵位因此链表初始化函数需要传入二级指针函数声明如下注意双向链表的初始化不能像单链表一样将哨兵位的next指针和prev指针都置为NULL。那么这两个指针应该怎样初始化呢在这里我们的双向链表已经满足了带头双向两个要求还需实现循环特性因此需要让哨兵位的next与prev指针都指向自身以此构成闭环。根据以上分析我们即可在List.c中写出如下代码3.双向链表的尾插和头插3.1尾插我们先思考一下以下两种传参方式哪个正确呢答案是第二种。因为哨兵位节点不能被删除节点的地址也不能发生改变所以我们传一级指针即可。根据上图分析想让新节点尾插到双向链表中我们需要·先让newnode的prev与next指针分别指向d3跟哨兵位。·然后我们让d3的next指针改指向newnode让哨兵位的prev指针也改指向newnode。代码如下特殊情况双向链表为空时如下图我们按照代码走一遍发现能走通所以这个代码没有问题。*双向链表的打印根据上图分析想要打印链表我们需要注意必须要让pcur从第一个有效节点开始遍历代码如下接下来我们利用打印函数来测试一下前面的尾插3.2头插注意头插指的并不是往哨兵位的前面去插入而是往第一个有效节点的前面去插入。根据上图我们想要实现双向链表的头插就需要·让newnode的prev与next指针指向哨兵位与第一个有效节点。·先改d1的prev指针让其指向newnode再改哨兵位的next指针让其也指向newnode。代码如下测试一下代码如下List.h文件#includestdio.h #includestdlib.h #includeassert.h typedef int LTDataType; typedef struct ListNode { int data; struct ListNode* prev; struct ListNode* next; }LTNode; //初始化 void LTInit(LTNode** pphead); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //打印 void LTPrint(LTNode* phead); //头插 void LTPushFront(LTNode* phead, LTDataType x);List.c文件#includeList.h //申请节点 LTNode* LTBuyNode(LTDataType x) { LTNode* node (LTNode*)malloc(sizeof(LTNode)); if (node NULL) { perror(malloc); exit(1); } node-data x; node-prev node-next node; return node; } void LTInit(LTNode** pphead) { //创建哨兵位 *pphead LTBuyNode(-1); } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); newnode-prev phead-prev; newnode-next phead; phead-prev-next newnode; phead-prev newnode; } //打印 void LTPrint(LTNode* phead) { LTNode* pcur phead-next; while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; } printf(\n); } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); newnode-prev phead; newnode-next phead-next; phead-next-prev newnode; phead-next newnode; }test.c文件#includeList.h void ListTest01() { LTNode* plist NULL; LTInit(plist); LTPushBack(plist, 1); LTPrint(plist); LTPushBack(plist, 2); LTPrint(plist); LTPushBack(plist, 3); LTPrint(plist); } int main() { ListTest01(); return 0; }4.双链表的尾删与头删4.1尾删注意想要进行删除操作链表就必须有效且链表不能为空判空条件是phead-next!phead。根据上图想要实现双向链表的尾删就需要·让d2的next指针改指向头节点·让头节点的prev指针指向d2。·删除d3代码如下测试一下4.2头删根据上图想要实现双向链表的头删我们需要·让d2的prev指针指向头节点·让头结点的next指针指向d2·删除d1代码如下测试一下5.在指定位置之后插入数据*双链表的查找代码如下比较简单不做赘述根据上图想要实现在指定位置之后插入数据我们需要·让newnode的prev指针指向posnext指针指向pos-next·让d3的prev指针指向newnode让d2的next指针指向newnode代码如下测试一下6.删除pos节点根据上图这个代码也比较简单如下测试一下7.链表的销毁根据上图想要实现链表的销毁操作我们需要·让pcur遍历链表在while循环里逐个销毁节点·出循环后也要记得把头节点删掉代码如下注意由于我们传参传的是一级指针所以在test.c文件中我们需要把plist手动置空。tipsLTErase与LTDestroy参数理论上要传二级指针因为我们需要让形参的改变影响到实参但是为了保持接口一致性才会传一级指针。传一级指针存在的问题是当形参置为NULL后实参plist不会被修改为NULL所以调用完后需要手动将实参置NULL。完整代码如下List.h文件#includestdio.h #includestdlib.h #includeassert.h typedef int LTDataType; typedef struct ListNode { int data; struct ListNode* prev; struct ListNode* next; }LTNode; //初始化 void LTInit(LTNode** pphead); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //打印 void LTPrint(LTNode* phead); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾删 void LTPopBack(LTNode* phead); //头删 void LTPopFront(LTNode* phead); //在指定位置之后插入 void LTInsert(LTNode* pos, LTDataType x); //查找 LTNode* LTFind(LTNode* phead, LTDataType x); //删除pos节点 void LTErase(LTNode* pos); //销毁链表 void LTDestroy(LTNode* phead);List.c文件#includeList.h //申请节点 LTNode* LTBuyNode(LTDataType x) { LTNode* node (LTNode*)malloc(sizeof(LTNode)); if (node NULL) { perror(malloc); exit(1); } node-data x; node-prev node-next node; return node; } void LTInit(LTNode** pphead) { //创建哨兵位 *pphead LTBuyNode(-1); } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); newnode-prev phead-prev; newnode-next phead; phead-prev-next newnode; phead-prev newnode; } //打印 void LTPrint(LTNode* phead) { LTNode* pcur phead-next; while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; } printf(\n); } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); newnode-prev phead; newnode-next phead-next; phead-next-prev newnode; phead-next newnode; } //尾删 void LTPopBack(LTNode* phead) { assert(phead phead-next ! phead); LTNode* del phead-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-prev phead; phead-next del-next; free(del); del NULL; } LTNode* LTFind(LTNode* phead, LTDataType x) { LTNode* pcur phead-next; while (pcur ! phead) { if (pcur-data x) { return pcur; } pcur pcur-next; } return NULL; } //在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode LTBuyNode(x); newnode-prev pos; newnode-next pos-next; pos-next newnode; pos-next-prev newnode; } //删除pos节点 void LTErase(LTNode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); pos NULL; } //销毁链表 void LTDestroy(LTNode* phead) { LTNode* pcur phead-next; while (pcur ! phead) { LTNode* next pcur-next; free(pcur); pcur next; } free(phead); phead NULL; }test.c文件#includeList.h void ListTest01() { LTNode* plist NULL; LTInit(plist); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPrint(plist); LTDestroy(plist); plist NULL; /*LTNode* find LTFind(plist, 1); LTErase(find); LTPrint(plist);*/ /*LTInsert(find, 66); LTPrint(plist);*/ /*LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist);*/ } int main() { ListTest01(); return 0; }