【手撕数据结构】拿捏双向链表

目录链表介绍初始化链表销毁链表查找节点打印链表增加节点尾插头插在指定位置之后插入节点删除节点尾删头删删除指定位置节点链表判空链表介绍前面说到链表的结构一共有八种带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。在这八种结构中我们只挑两种来进行刨析即无头单向非循环链表和带头双向循环链表。而今天我们要介绍的双向链表就是带头的头结点head也被称为哨兵位如果链表为空则链表只有一个哨兵位。双向链表的结构为typedefintLTDataType;//方便以后修改双向链表存储的数据类型typedefstructListNode{LTDataType val;structListNode*prev;structListNode*next;}LTNode;分别用一个变量存储数据前驱指针prev指向前节点next指针指向后节点,这样链表就可以进行随机访问。初始化链表LTNode*LTBuyNode(LTDataType x)//尾插头插等都需要创建新的节点不妨封装一个函数,每个节点的next,prev指针都先指向自己{LTNode*newnode(LTNode*)malloc(sizeof(LTDataType));if(newnodeNULL){perror(malloc failed);exit(1);}newnode-valx;newnode-prevnewnode-nextnewnode;returnnewnode;}因为插入都需要创建节点所以封装一个函数注意:这些节点的next指针和prev指针都指向自己这是为了兼容空链表只有一个哨兵位时和后面插入节点时利用这两个指向自己的指针调成被影响的节点的指针//void LTInit(LTNode** pphead)//{// assert(pphead);// *pphead LTBuyNode(-1);//}//优化接口一致性版本LTNode*LTInit(LTNode*phead){LTNode*newnodeLTBuyNode(-1);returnnewnode;}首先我们要对链表进行初始化上面说了空双向链表是只有一个哨兵位所以我们创建一个节点作为哨兵位.销毁链表//void LTDestroy(LTNode** pphead)//{// assert(pphead *pphead); //*pphead防止释放空链表// LTNode* pcur (*pphead)-next;// while (pcur ! *pphead)// {// LTNode* Next pcur-next;// free(pcur);// pcur NULL;// pcur Next;// }// free(*pphead);// *pphead NULL;//}//优化接口一致性版本voidLTDestroy(LTNode*pphead){assert(pphead);LTNode*pcurpphead-next;while(pcur!pphead){LTNode*Nextpcur-next;free(pcur);pcurNULL;pcurNext;}free(pphead);ppheadNULL;//这里设置NULL了不影响实参需要手动设置NULL,但是释放了空间是同一块空间}销毁链表从头结点的后一个结点处开始向后遍历并释放结点直到遍历到头结点时停止遍历并将头结点也释放掉。查找节点LTNode*LTFind(LTNode*phead,LTDataType x){assert(phead);if(!LTEmpty(phead)){returnNULL;}else{LTNode*pcurphead-next;while(pcur!phead){if(pcur-valx){returnpcur;}pcurpcur-next;}}returnNULL;}给定一个值在链表中寻找与该值相同的结点若找到了则返回结点地址若没有找到则返回空指针(NULL)。如果为空链表就直接返回NULL.这里因为双向楼面是循环的用pcur从头结点(哨兵位下一个节点)开始遍历,如果回到哨兵位表示已经查找完一圈没找到。打印链表voidLTPrint(LTNode*phead){assert(phead);LTNode*pcurphead-next;while(pcur!phead){printf(%d-,pcur-val);pcurpcur-next;}}打印双向链表时也是从头结点的后一个结点处开始向后遍历并打印直到遍历哨兵位结点处时便停止遍历和打印哨兵位结点数据不打印。增加节点尾插voidLTPushBack(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeLTBuyNode(x);newnode-nextphead;newnode-prevphead-prev;phead-prev-nextnewnode;phead-prevnewnode;}尾插申请一个新结点将节点插入到旧尾节点之后改变旧尾节点的next指针和新尾节点的next指针和prev指针,改变哨兵为的prev指针头插voidLTPushFront(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeLTBuyNode(x);newnode-nextphead-next;newnode-prevphead;phead-next-prevnewnode;phead-nextnewnode;}头插即申请一个新结点将新结点插入在哨兵位后即可。在指定位置之后插入节点voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnodeLTBuyNode(x);newnode-nextpos-next;newnode-prevpos;pos-next-prevnewnode;pos-nextnewnode;}我们只需申请一个新结点插入到指定位置结点和其后一个结点之间即可。删除节点尾删voidLTPopBack(LTNode*phead){assert(phead);assert(LTEmpty(phead));LTNode*delphead-prev;del-prev-nextphead;phead-prevdel-prev;free(del);delNULL;}头删头删即释放哨兵位的后一个结点并建立哨兵位节点与被删除结点的后一个结点之间的双向关系即可。voidLTPopFront(LTNode*phead){assert(phead);assert(LTEmpty(phead));LTNode*delphead-next;phead-nextdel-next;del-next-prevphead;free(del);delNULL;}删除指定位置节点voidLTErase(LTNode*pos){assert(pos);pos-prev-nextpos-next;pos-next-prevpos-prev;free(pos);posNULL;}删除指定位置结点释放掉目标结点后建立该结点前一个结点和后一个结点之间的双向关系即可。链表判空boolLTEmpty(LTNode*phead){assert(phead);returnphead-next!phead;}链表判空即判断头结点的前驱或是后驱指向的是否是自己即可(因为是循环)