双向链表的实现

双向链表的实现一.双向链表的定义二.链表的节点组成三.处理头节点(初始化)四.链表的函数接口4.1打印4.2尾插4.3头插4.4尾删4.5头删4.6查找和删除特定位置元素4.6在指定位置之后插入数据4.7删除指定位置4.7链表的销毁一.双向链表的定义双向链表可以在单链表的基础上理解对于单向链表是单向不循环链表则双向链表就是双向循环并且带哨兵位的节点二.链表的节点组成由于是双向的链表所以我们不仅仅要定义后继指针也要定义前驱指针并且还有个存储的数据在代码的实现上为了方便简洁要和单向链表那一章节一样对多次出现的数据类型重命名代码的实现如下typedefintLTDatatype;typedefstructListNode{LTDatatype data;structListNode*next;structListNode*prev;}LTNode;三.处理头节点(初始化)首先我们实现初始化的时候应该传入这个函数的是关于头节点二级指针因为要改变头节点voidLTInit(LTNode**pphead);我们在初始化的时候是对哨兵位进行处理但是有一个问题就是我们还要对哨兵位的next以及prev指针指向NULL吗显然不可以置为空否则不能使得这个链表进行循环所以我们应该把两个指针指向自身接下来就展示这个代码并且把申节点空间封装成一个函数函数具体讲解单链表有LTNode*LTBuyNode(LTDatatype x){LTNode*newnodemalloc(sizeof(LTNode));if(newnodeNULL){perror(malloc fail);exit(1);}newnode-datax;newnode-nextnewnode-prevnewnode;returnnewnode;}voidLTInit(LTNode**pphead){*ppheadLTBuyNode(-1);}四.链表的函数接口4.1打印在打印的时候应该定义一个指针pcur指向头结点的next直到pcur不等于pheadvoidLTPrint(LTNode*phead){LTNode*pcurphead-next;while(pcur!phead){printf(%d-,pcur-data);pcurpcur-next;}printf(\n);}4.2尾插注意点哨兵位不能被删除头节点地址不能改变具体实现图如下既然是不能改变头节点那么传入的就是一级指针通过头节点去找到尾节点(phead-prev)改变next和prev的时候应先改变newnode不会影响原链表即使链表只有头节点直接尾插不会有所影响改变初始链表的尾的next和头的pre不能改变位置代码如下voidLTPushBack(LTNode*phead,LTDatatype x){assert(phead);LTNode*newnodeLTBuyNode(x);newnode-nextphead;//新节点next指向头newnode-prevphead-prev;//新节点prev指向尾phead-prev-nextnewnode;//初始链表的尾next指向新phead-prevnewnode;//头节点的prev指向新}4.3头插头插在头节点的后面即哨兵位后面插入头插图如下先改变newnode的前后防止原链表发生变化再通过head找到d1改变d1的prev最后改变head代码如下voidLTPushFront(LTNode*phead,LTDatatype x){assert(phead);LTNode*newnodeLTBuyNode(x);newnode-nextphead-next;//新节点next指向头nextnewnode-prevphead;//新节点prev指向头newnode-next-prevnewnode;//初始链表的头next的prev指向新phead-nextnewnode;//头节点的next指向新}4.4尾删如图删除d3对于尾删需要注意的一点是避免链表为空而链表为空主要就是只剩一个头结点如果pheadNULL这不是一个有效的空链表所以判空的条件就是assert(pheadphead-next!phead)voidLTPopBack(LTNode*phead){assert(pheadphead-next!phead);LTNode*delphead-prev;//保存一下要删的节点del-prev-nextphead;phead-prevdel-prev;//删除del节点free(del);delNULL;}4.5头删如图删除d1对于头删也一样需要注意的一点是避免链表为空而链表为空主要就是只剩一个头结点如果pheadNULL这不是一个有效的空链表所以判空的条件就是assert(pheadphead-next!phead)voidLTPopFront(LTNode*phead){assert(pheadphead-next!phead);LTNode*delphead-next;//先保存起来del-next-prevphead;phead-nextdel-next;free(del);//销毁deldelNULL;}4.6查找和删除特定位置元素因为查找具体思路基本和单链表一样所以直接上代码LTNode*LTFind(LTNode*phead,LTDatatype x){LTNode*pcurphead-next;while(pcur!phead){if(pcur-datax){returnpcur;}pcurpcur-next;}returnNULL;}4.6在指定位置之后插入数据关于删除操作的函数我们只需要传入需要在哪个节点后面插入就行不需要传入头节点所以在最后插入的时候不能调用尾插的方法因为找不到头节点尾插的实现需要传入头节点要删除的那个节点我们调用LTFind函数就可以voidLTInsert(LTNode*pos,LTDatatype x){assert(pos);LTNode*newnodeLTBuyNode(x);newnode-nextpos-next;newnode-prevpos;pos-next-prevnewnode;pos-nextnewnode;}4.7删除指定位置删除pos位置的节点受到影响的pos前后两个节点具体操作就和尾删思路差不多代码如下voidLTErase(LTNode*pos){assert(pos);pos-next-prevpos-prev;pos-prev-nextpos-next;free(pos);//销毁pos}可能就有疑问了为什么pos不传二级指针因为我们要把pos置为空指针这里是为了保持接口的一致性我们只需要出了函数手动把pos置为NULL就可以了具体图如下4.7链表的销毁双向链表和单链表的销毁过程类似在销毁某一个结点的时候我们应该把下一个节点保存起来出了函数把哨兵位节点手动删除代码如下voidLTDestory(LTNode*phead){assert(phead);LTNode*pcurphead-next;while(pcur!phead){LTNode*pnextpcur;free(pcur);pcurpnext;}}最后出了函数把哨兵位销毁图如下