双链表的介绍以及基本功能的实现（详细注释版本）

带你梳理 双链表基本功能实现 的思路

前言

✨本博客介绍了链表的分类，双链表的结构，单双链表为空的区别，重点注释双链表基本功能的实现。
感兴趣的话就一起往下看看叭～😁

开篇碎碎念 😗

• 双链表的结构看似复杂，但是由于其双向性，在代码实现上比单链表简单了不少，甚至思路上也大同小异
• 像是双链表的插入都有其固定套路，创建节点 -> 接入新链表 ->改变原有节点的指向
• 双链表的删除也有固定套路，储存(标记)要删除的节点->改变原有节点的指向 ->释放空间
• 要注意哨兵节点phead的作用只是指向第一个节点哦
• 作者添加了许多注释，以便于帮读者理清思路，骄傲[jpg],所以请放心食用😋

目录

正文

1.链表的分类

链表共有2x2x2种类型，下面列举其中的两例。

常见的单链表全称为 :单向 不带头 不循环 链表。
常见的双链表全称为 :双向 带头 循环 链表。

2.双链表的构成

双链表的组成结构

• 保存的数据
• 指向下一节点的指针
• 指向前一个节点的指针

3.单双链表为空的区别

单链表（不带头）

空表连头结点都没有，头指针直接悬空：
phead == NULL // 判空

双链表（带头循环，就是这次写的）

头结点（哨兵）永远在，只是它孤零零自己指自己，成个环：
phead->next == phead // 判空
这时候 phead->prev 也等于 phead，next 和 prev 都绕回自己身上。

区别一句话：

• 单链表空 = 指针是 NULL（连头都没了）。
• 双链表空 = 头结点还在，但它自己抱自己（next == prev == phead）。

4.双链表基本功能的实现

4.0 创建节点

LTNode*BuyNode(LTDataType x){LTNode*newnode=(LTNode*)malloc(sizeof(LTNode));if(newnode==NULL){printf("malloc fail");exit(1);}newnode->data=x;newnode->next=newnode->prev=newnode;returnnewnode;}

4.1 链表打印

voidLTPrint(LTNode*phead){LTNode*cur=phead->next;//创建一个指针变量遍历链表while(cur!=phead){printf("%d ",cur->data);cur=cur->next;//移动指针变量}printf("\n");}

4.2 创建节点

LTNode*BuyNode(LTDataType x){LTNode*newnode=(LTNode*)malloc(sizeof(LTNode));//申请空间if(newnode==NULL)//防止申请失败{printf("malloc fail");exit(1);}newnode->data=x;//初始化newnode->next=newnode->prev=newnode;//确认指向returnnewnode;}

4.3 初始化

LTNode*LTInit(){LTNode*phead=BuyNode(-1);returnphead;}

4.4 销毁链表

voidLTDestroy(LTNode*phead){LTNode*cur=phead->next;//创建可以遍历链表的节点while(cur!=phead)//遍历链表ing...{LTNode*next=cur->next;//储存下一个链表 防止free后丢失目标free(cur);cur=next;}free(phead);//不要忘记手动 free phead哦}

4.5 尾插

voidLTPushBack(LTNode*phead,LTDataType x){LTNode*newnode=BuyNode(x);//创建新节点//接入新节点newnode->next=phead;newnode->prev=phead->prev;//改变原链表的指向phead->prev->next=newnode;phead->prev=newnode;}

4.6 头插

//头插voidLTPushFront(LTNode*phead,LTDataType x){//创建新节点LTNode*newnode=BuyNode(x);//接入新节点newnode->prev=phead;newnode->next=phead->next;//改变原链表的指向phead->next->prev=newnode;phead->next=newnode;}

4.7 判空

boolLTEmpty(LTNode*phead){returnphead->next==phead;}

4.8 尾删

voidLTPopBack(LTNode*phead){//只剩一个头节点时不能删除assert(!LTEmpty(phead));//标记尾节点LTNode*del=phead->prev;//改变原链表指向del->prev->next=phead;phead->prev=del->prev;//释放空间free(del);del=NULL;}

4.9 头删

voidLTPopFront(LTNode*phead){//只剩一个头节点时不能删除assert(!LTEmpty(phead));//标记头节点LTNode*del=phead->next;//改变原链表指向phead->next=del->next;del->next->prev=phead;//释放空间free(del);del=NULL;}

4.10 寻找特定节点

LTNode*LTFind(LTNode*phead,LTDataType x){//设置指针遍历链表LTNode*cur=phead->next;while(cur!=phead){//判断是否相等if(cur->data==x)returncur;//移动指针elsecur=cur->next;}//找不到就返回NULLreturnNULL;}

4.11 在pos节点后插入数据

voidLTInsert(LTNode*pos,LTDataType x){//创建节点LTNode*newnode=BuyNode(x);//接入新节点newnode->prev=pos;newnode->next=pos->next;//改变原链表pos->next->prev=newnode;pos->next=newnode;}

4.12 删除pos节点

voidLTErase(LTNode*pos){LTNode*del=pos->next;del->prev=pos->prev;pos->prev->next=del;free(pos);pos=NULL;}

总结

双链表每个结点多一个prev，前后都能走；带头 + 循环，判空一句phead->next == phead。增删改记住「先接新线、再拆旧线」就够啦