admin管理员组文章数量:1794759
数据结构·双向链表
前言：上文提交的链表有八种，我们介绍两种，一种是单向不带头不循环链表，我们简称为单链表，一种是双向带头循环链表，我们简称为双向链表，虽然提及到双向链表是难度最大的，可是实际上写完后你会认为双向链表是最好理解并且最好写的。
1 双向链表基本框架
双向链表，即链表可以循环，可以由前到后，由后到前，那么循环的实现就是交给头尾相连，前后互通就是交给两个指针完成：
这是双向链表的概念图，我们需要两个指针，分别是next,prev，用来指向下一个结点和上一个结点，所以结构体的创建也有所改变：
代码语言：javascript代码运行次数：0运行复制typedef int Datatype;
typedef struct DouList
{
Datatype val;
struct DouList* next;
struct DouList* prev;
}SLTNode;head结点是哨兵位，是不存储数据，或者说是存储一个无效数据的，实际使用的时候我们关心的是head之后结点的数据。
双向链表的基本框架创建好了，那么我们就可以开始实现双向链表的功能了。
2 结点的创建 打印 查找
我们考虑到结点的创建在实现的时候频繁使用，所以实现该功能，哨兵位是个独特的位置，我们就创建好之后，两个指针的位置应该都要指向他本身，并且我们规定，哨兵位的指针指向自己的时候链表为空：
代码语言：javascript代码运行次数：0运行复制SLTNode* DLTCreate(Datatype x)//创建结点
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode != NULL)
{
newnode->val = x;
newnode->prev = newnode->next = newnode;
return newnode;
}
return NULL;
}创建结点这点与单链表差别不大，返回值都是结构体指针，仍然判断是不是为空，开辟好空间之后进行赋值，自身相连接，最后返回就行了。
打印基本上是一样的，循环结束的条件应该是指针指到了哨兵位，打印的时候应该是从哨兵位的下一个结点开始：
代码语言：javascript代码运行次数：0运行复制void DLTPrint(SLTNode* phead)//打印
{
assert(phead);
SLTNode* tem = phead->next;
while (tem != phead)
{
printf("%d->", tem->val);
tem = tem->next;
}
printf("\n");
}查找的时候同打印，循环条件，循环体的改变，注意返回值应该是结构体指针，因为在指定位置插入数据的时候我们会用的到：
代码语言：javascript代码运行次数：0运行复制SLTNode* DLTFind(SLTNode* phead, Datatype x)//查找数据
{
assert(phead);
SLTNode* tem = phead->next;
while (tem != phead)
{
if (tem->val == x)
{
return tem;
}
tem = tem->next;
}
return NULL;
}基本上就是和打印一样的，稍加注意即可。
3 头插/尾插
在头插之前注意一点，我们用的参数都是一级指针，因为我们使用的时候我们实际是用的head之后的位置，所以只是需要结点的位置，我们并不需要对哨兵位进行改变，所以使用的是一级指针，前面查找同理，我们不需要修改，我们需要哨兵位后面的结点的地址。
在插入数据的时候，实际上影响到了三个结点，哨兵位结点，新插入的结点，原来的头结点：
这里修改的时候，先让newnode的两个指针指向过去，然后修改头结点和哨兵位指向，也就是说一共修改了四个指向，修改的代码也就4行：
代码语言：javascript代码运行次数：0运行复制void DLTPushHead(SLTNode* phead, Datatype x)//头插数据
{
assert(phead);
SLTNode* newnode = DLTCreate(x);
assert(newnode);
SLTNode* tem = phead->next;
newnode->next = tem;
newnode->prev = phead;
tem->prev = newnode;
phead->next = newnode;
}尾插
尾插影响到的结点还是三个结点，尾结点，哨兵位，插入结点，仍然是修改四条线路，先修改newnode的指向，然后修改其他的指向，先修改newnode的指向是因为防止先修改其他的会改变newnode本身，所以这里选择先修改newnode的指向：
代码语言：javascript代码运行次数：0运行复制void DLTPushBack(SLTNode* phead, Datatype x)//尾插数据
{
assert(phead);
SLTNode* newnode = DLTCreate(x);
assert(newnode);
SLTNode* tem = phead->prev;
newnode->next = phead;
newnode->prev = tem;
tem->next = newnode;
phead->prev = newnode;
}其实结合图，理解简直就是易如反掌。
4 头删/尾删
头删，删除删的是哨兵位的下一个结点，也就是head->next，影响三个结点，分别是哨兵位结点，头结点，头结点的下一个结点，结点连接好后，需要释放头结点，并且置为NULL：
代码语言：javascript代码运行次数：0运行复制void DLTPopHead(SLTNode* phead)//头删数据
{
assert(phead);
assert(phead->next != phead);
SLTNode* tem = phead->next;
phead->next = tem->next;
tem->next->prev = phead;
free(tem);
tem = NULL;
}当然，头删的时候需要注意的点是链表不能为空，前面提及，如果哨兵位指向的是自己，那么就认为链表为空，所以需要用到两个assert，释放的结点最好单独用一个变量来存储，一是为了代码的整洁度，二是为了内存不泄露。
尾删，删除的是哨兵位的上一个结点，也就是head->prev，影响三个结点，分别是哨兵位结点，尾结点，尾结点的上一个结点，
修改方法同头删，如法炮制即可，无非就是那几个结点指向的位置变来变去：
代码语言：javascript代码运行次数：0运行复制void DLTPopBack(SLTNode* phead)//尾删数据
{
assert(phead);
assert(phead->next != phead);
SLTNode* tem = phead->prev;
tem->prev->next = phead;
phead->prev = tem->prev;
free(tem);
tem = NULL;
}注意的仍然是链表不能为空，其他的和头删没什么两样。
5 指定位置 删除数据/之前插入数据
指定位置相关函数的时候就需要用到最开始写到的查找函数了，删除数据影响的是三个结点，指定位置本身以及前后的结点：
void DLTDelete(SLTNode* pos)//指定位置删数据
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}修改结点修改两个，修改好了之后释放点结点就行了。
在指定位置之前插入数据：
老规矩，先修改newnode，然后修改其他指向，那么一共修改四个指向：
代码语言：javascript代码运行次数：0运行复制void DLTInsertAfter(SLTNode* pos, Datatype x)//指定位置之前插入数据
{
assert(pos);
SLTNode* newnode = DLTCreate(x);
assert(newnode);
newnode->next = pos;
newnode->prev = pos->prev;
pos->prev->next = newnode;
pos->prev = newnode;
}只要把指向改好了，就可以了
6 双向链表的销毁
销毁我们这里好像就要传二级指针了？没错，确实可以，但是我们为了保证接口的一致性，我们就还是用一级指针，最后需要手动置为空指针而已。
代码语言：javascript代码运行次数：0运行复制void DLTDestroy(SLTNode* phead)//销毁
{
assert(phead);
SLTNode* tem = phead->next;
while (tem != phead)
{
SLTNode* pcur = tem->next;
free(tem);
tem = pcur;
}
free(phead);
phead = NULL;
}int main()
{
SLTNode* plist = DLTCreate(-1);
DLTPushHead(plist, 2);
DLTPushHead(plist, 1);
DLTPushBack(plist, 3);
DLTPushBack(plist, 4);
DLTPrint(plist);
SLTNode* tem = DLTFind(plist, 3);
DLTInsertAfter(tem, 1);
DLTPrint(plist);
DLTDestroy(plist);
plist = NULL;
return 0;
}最后在主函数这里，我们把哨兵位置为空，那么双向链表的功能就基本实现了，总结来说，双向链表理解好了之后简直比单链表好容易写，代码量更少！
感谢阅读！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-08-13，如有侵权请联系 cloudcommunity@tencent 删除数据结构链表数据指针存储本文标签： 数据结构双向链表
版权声明：本文标题：数据结构·双向链表 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754794709a1706539.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论