玩转数据结构:探索双向链表的奥秘
文章目录
- 前言
- 一、双向链表是什么?
-
二、双向链表的实现
- 1.节点结构的创建
- 2.链表的初始化
- 3.创建新节点
- 4.打印链表
- 5.尾插
- 6.头插
- 7.头删
- 8.尾删
- 9.查找
- 10.指定位置插入
- 11.指定位置删除
- 12.链表的销毁
- 总结
前言
制作不易,点赞支持一下呗!!!
之前我们介绍了链表的分类,并且详细介绍其中的单链表,这节将会带大家了解另一种重要的链表------双向链表!!!
由于双向链表的插入删除比单链表要简单许多,能理解单链表的操作,应该可以很轻松明白双向链表的操作,所以这里不会十分详细的介绍过程
如有疑问,可以看看之前的单链表一文
一、双向链表是什么?
双向链表全称是带头双向循环链表,带头也就是带有哨兵位(不用来存储有效数据的头节点),双向意味着可以通过当前节点找到它的前驱节点和后继节点,因此,在节点的结构中需要两个指针。
结构示意图如上所示
二、双向链表的实现
1.节点结构的创建
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
2.链表的初始化
双向链表是带有哨兵卫的,插入数据之前应该先初始化一个哨兵卫。
void LTInit(LTNode** pphead)
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
if (*pphead == NULL)
{
perror("malloc");
exit(1);
}
(*pphead)->data = -1;
(*pphead)->prev = *pphead;
(*pphead)->next = *pphead;
}
3.创建新节点
因为我们后续插入数据时需要多次用到创建新节点这个操作,因此我们这里单独将它封装成一个函数。
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
4.打印链表
为了方便我们调试,我们需要将链表中的数据打印出来检查是否插入或删除成功,我们需要实现一个打印链表的功能。
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
5.尾插
由于在插入数据时不应该修改哨兵卫,所以之后的所有函数接口的参数应该用一级指针
并且由于哨兵卫的前驱节点就是尾节点,所以尾插时不需要循环遍历找尾节点!!!因此双向链表比单链表简单许多
这里新创建一个节点newnode。
第一步先改变新节点的prev和next。
第二步改变原尾节点的next使其指向newnode,哨兵卫的prev使其指向newnode
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;
}
6.头插
头插的定义是在第一个有效数据前插入新节点,因为在哨兵卫之前插入数据就相当于尾插(循环链表中)
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;
}
7.头删
若哨兵卫的prev或next指针指向它自己,说明链表为空(没有有效的节点)
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* del = phead->next;
LTNode* next = del->next;
phead->next = next;
next->prev = phead;
free(del);
del = NULL;
}
8.尾删
若哨兵卫的prev或next指针指向它自己,说明链表为空(没有有效的节点)
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);//保证链表中存在有效节点
LTNode* del = phead->prev;//保存一份要删除的节点,后面释放时需要使用
del->prev->next = phead;
phead->prev =del->prev;
free(del);
del = NULL;
}
9. 查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
10.指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
11.删除指定位置数据
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
next->prev = prev;
prev->next = next;
free(pos);
pos = NULL;
}
12.链表的销毁
void LTDestroy(LTNode** pphead)
{
assert(pphead);
assert(*pphead);//哨兵卫不为空
LTNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(*pphead);
*pphead = NULL;
}
总结
双向链表的所有代码:
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void LTInit(LTNode** pphead)
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
if (*pphead == NULL)
{
perror("malloc");
exit(1);
}
(*pphead)->data = -1;
(*pphead)->prev = *pphead;
(*pphead)->next = *pphead;
}
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//尾插
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 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);
assert(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);
assert(phead->next != phead);
LTNode* del = phead->next;
LTNode* next = del->next;
phead->next = next;
next->prev = phead;
free(del);
del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
next->prev = prev;
prev->next = next;
free(pos);
pos = NULL;
}
void LTDestroy(LTNode** pphead)
{
assert(pphead);
assert(*pphead);//哨兵卫不为空
LTNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(*pphead);
*pphead = NULL;
}
上一篇: 在Spring Boot中应用Flowable工作流:遇到的问题与解决方案
下一篇: 面对2PC的瓶颈?也许该是更新二阶段提交协议的时候了 - 丹尼尔·阿巴迪原创观点,探讨高可用架构变迁,发表于2019年
推荐阅读
-
玩转 JSP:探索动作元素的奥秘
-
玩转C语言:探索三维数组的奥秘
-
玩转敏捷课程开发:探索SAM模型的奥秘
-
玩转数字世界:探索计数器的奥秘与实用应用——数字电路实验07
-
玩转数据结构:探索双向链表的奥秘
-
玩转Java编程:探索命令模式的奥秘
-
玩转Google Earth Engine (GEE):以NDVI为例,探索影像的数学计算奥秘
-
数据结构:双向链表各种操作的图解(表头插入、表尾插入、任意位置插入、查询节点、删除节点、查找链表长度......)。...)
-
数据结构:双向链表各种操作的图解(表头插入、表尾插入、任意位置插入、查询节点、删除节点、查找链表长度......)。...)
-
Java - 双向链表的数据结构