当前位置： 首页 > article >正文

数据结构初阶---链表(2)---双向链表

article 2025/1/20 2:02:39

链表(1)中讲过了在OJ题中出现很多并且能作为一些复杂数据结构子结构的不带头单向不循环链表，下面讲解应用很广很实用的带头双向循环链表。

三、双向链表---DoublyLinkedList

演示带头双向循环链表(实用)。

带头--->不需要对空链表继续单独判断；循环--->可以很轻松的找到尾结点。 

集各种优势于一身的链表。

1.双向链表的结构

//双向带头循环链表
#define DLListDataType int 
typedef struct DLListNode
{
	struct DLListNode* prev;//前驱指针
	struct DLListNode* next;//后继指针
	DLListDataType data;//数据
}DLListNode;

链表是双向的，结构体成员不仅要有next指针用于指向下一个结点，同时需要有prev指针指向前一个结点。

2.双向链表的接口函数

①初始化DLListInit

void DLListInit ( DLListNode** pphead ) ;

对于带头的双向循环链表而言，我们不仅需要创建结构体指针变量，同时还需要创建一个哨兵位，我们在函数DLListInit中创建哨兵位，由于我们是对结构体指针进行修改，如果传入函数，需要传入指针的地址，函数使用结构体二级指针DLListNode** pphead接收才能够修改所创建的指针变量pdll的值：

DLListNode* pdll = NULL;
DLListInit(&pdll);
void DLListInit(DLListNode** pphead)
{
    assert(pphead);
    *pphead = (DLListNode*)malloc(sizeof(DLListNode));
	if (*pphead == NULL)
	{
		perror("malloc fail");
	}
	*pphead->next = *pphead;
	*pphead->prev = *pphead;
	*pphead->data = -1;
}

但是，如果我们不想用二级指针接收，也有办法，我们可以就用结构体指针接收，最后传回这个哨兵位的地址给指针变量pdll即可：

DLListNode* DLListInit ( ); 

DLListNode* pdll = DLListInit();
DLListNode* DLListInit()
{
	DLListNode* phead = (DLListNode*)malloc(sizeof(DLListNode));
	if (phead == NULL)
	{
		perror("malloc fail");
	}
	phead->next = phead;
	phead->prev = phead;
	phead->data = -1;
	return phead;
}

以上两种方法都能够达到目的。

注意，由于是循环链表，因此，我们将哨兵位的next和prev都指向它本身。这个操作也对后面的接口函数有比较好的影响。

②结点创建DLListCreateMemory

DLListNode* DLListCreateMemory ( DLListDataType x );

与单链表的大差不差：

//创建结点
DLListNode* DLListCreateMemory(DLListDataType x)
{
	DLListNode* newnode = (DLListNode*)malloc(sizeof(DLListNode));
	//省略if判断
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

③数据打印DLListPrint

void DLListPrint ( DLListNode* phead ); 

打印上就与单链表显得不太一样了，单链表尾结点的next指向NULL，因此循环条件定为遍历不为NULL继续，为NULL停止，可以依次打印出单链表各个结点存储的数据，但是双向循环链表，尾结点存储的next又指向了哨兵位phead，循环条件是有区别的，从何处开始打印也需要注意。

对于双向循环带头链表而言，我们从phead->next开始是第一个有效结点，一直到phead结束为整个链表的结点，那么我们创建指针cur进行遍历，cur从phead->next开始依次打印数据，直到cur指向哨兵位即cur == phead停止。

//打印数据
void DLListPrint(DLListNode* phead)
{
	assert(phead);
	printf("哨兵位");
	//循环带头链表，尾结点的next指向哨兵位，哨兵位的prev指向尾结点
	DLListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("==>%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

④数据销毁DLListDestroy

DLListNode* DLListDestroy ( DLListNode* phead ); 

创建一个指针cur依次释放空间，注意要保存后一个结点，循环条件为cun->next != phead；那么销毁到最后就会只剩一个哨兵位空间，最后释放掉哨兵位空间，然后返回NULL给我们在主函数创建的结构体指针变量即可，这也是为了防止野指针。

//销毁
DLListNode* DLListDestroy(DLListNode* phead)
{
	assert(phead);
	DLListNode* cur = phead->next;
	while (cur != phead)
	{
		DLListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	return NULL;
}

如果不返回NULL，我们也可以传入二级指针来操作，或者我们在进行完销毁操作后再置空也可以

⑤数据查找DLListSearch

DLListNode* DLListSearch ( DLListNode* phead, DLListDataType x ); 

查找并返回该结点，没有则返回NULL：

//查找---找到返回结点地址，未找到返回NULL
DLListNode* DLListSearch(DLListNode* phead, DLListDataType x)
{
	assert(phead);
	DLListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

下面是头尾插删操作。

⑥尾插DLListPushBack

void DLListPushBack ( DLListNode* phead, DLListDataType x );

我们不再需要向单链表那样遍历得到尾结点再来插入结点，可以直接通过哨兵位的prev指针得到尾结点，然后插入新的结点。那么对于双向循环带头链表而言，需要改变哨兵位的prev指向，原尾结点的next指向，然后对于新插入尾结点的next与pre指针指向进行赋值---next指向哨兵位、prev指向原尾结点。

//尾插
void DLListPushBack(DLListNode* phead, DLListDataType x)
{
	assert(phead);
	DLListNode* tail = phead->prev;//找尾
	DLListNode* newnode = DLListCreateMemory(x);
	//尾插结点的next指向哨兵位，prev指向原尾结点
	newnode->next = phead;
	newnode->prev = tail;
	//哨兵位的prev指向尾插结点，原尾结点的next指向尾插结点
	phead->prev = newnode;
	tail->next = newnode;
}

⑦头插DLListPushFront

void DLListPushFront ( DLListNode* phead, DLListDataType x ); 

对于带头循环双向链表而言，最容易出错的部分就是指针指向的修改，往往会有多个指针需要修改指向，我们要将其理清楚。对于头插，我们需要将原一号结点的prev指向插入结点，哨兵位的next指向插入结点，同时将插入结点的next指向原一号结点，prev指向哨兵位。

//头插
void DLListPushFront(DLListNode* phead, DLListDataType x)
{
	assert(phead);
	DLListNode* cur = phead->next;
	DLListNode* newnode = DLListCreateMemory(x);
	phead->next = newnode;
	newnode->next = cur;
	newnode->prev = phead;
	cur->prev = newnode;
}

⑧尾删DLListPopBack

void DLListPopBack ( DLListNode* phead ); 

首先要判断链表是否为空，为空不能删除，使用一个assert宏断言phead->next即可，如果phead->next与phead相同，那么说明该链表是空链表，仅有一个哨兵位：

assert(phead->next != phead);//没有数据--->不允许删除

尾删我们首先通过哨兵位phead的prev指针找到尾结点tail，由于删除尾结点需要对尾结点上一个结点的next指向进行修改，那么我们以同样方式找到尾结点tail的上一个结点tailprev，将tailprev的next指向哨兵位，将哨兵位的prev指针指向tailprev，然后释放tail结点即可。

//尾删
void DLListPopBack(DLListNode* phead)
{
	assert(phead);//哨兵位不能开辟失败
	assert(phead->next != phead);//没有数据--->不允许删除
	//找尾与尾的前一位
	DLListNode* tail = phead->prev;
	DLListNode* tailprev = tail->prev;
	//尾删操作
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
}

⑨头删DLListPopFront

void DLListPopFront ( DLListNode* phead ); 

头删需要找到第一个有效结点cur与第二个有效结点curnext，将其存储的prev指针指向哨兵位，同时将哨兵位next结点指向第二个结点curnext，释放cur结点空间即可。

//头删
void DLListPopFront(DLListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	DLListNode* cur = phead->next;
	DLListNode* curnext = cur->next;
	phead->next = curnext;
	curnext->prev = phead;
	free(cur);
}

同尾删，如果空链表，不允许删除，如果删除操作继续，我们会发现哨兵位被释放了，那么这个操作会对后续的结构体指针变量的使用产生巨大影响，该指针变量就是野指针！ 

⑩pos结点前插入DLListInsert

void DLListInsert ( DLListNode* pos, DLListDataType x ); 

在pos结点前插入结点，通常搭配着查找接口函数使用，那么我们需要找到pos原来前一个结点，假设为posprev，那么将posprev的next指向插入结点，pos的prev指向插入结点，再将插入结点的next与prev分别指向pos与posprev即可。

//pos前插入x
void DLListInsert(DLListNode* pos, DLListDataType x)
{
	assert(pos);
	DLListNode* newnode = DLListCreateMemory(x);
	DLListNode* posprev = pos->prev;
	posprev->next = newnode;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
}

DLListInsert接口可以完成尾插与头插：

尾插--->DLListInsert ( phead , x ) ;

头插--->DLListInsert ( phead->next , x ) ;

只需要改变传入的结点即可，传入哨兵位即为尾插；传入第一个有效结点即为头插。

pos可不可以指向哨兵位呢？

是可以的，pos指向哨兵位时在pos前插入，相当于尾插，因为posprev就是原尾结点，相当于在尾结点的后面插入了一个结点。所以不需要额外进行判断。

⑪删除pos结点DLListErase

void DLListErase ( DLListNode* pos );

对于删除操作而言，不能删除哨兵位因此需要断言：

	assert(pos);
	assert(pos->next != pos);//不能删除哨兵位

删除pos结点，那么需要改变前一个prev结点的next指向，改变后一个next结点的prev指向，然后释放pos结点空间。

//删除pos结点
void DLListErase(DLListNode* pos)
{
	assert(pos);
	assert(pos->next != pos);
	DLListNode* posprev = pos->prev;
	DLListNode* posnext = pos->next;
	free(pos);
	pos = NULL;
	posprev->next = posnext;
	posnext->prev = posprev;
}

其实在接口里pos置空还不行，因为传入的实参pos仍然是野指针，我们需要在DLListErase函数外对pos置空。即DLListErase操作结束后对pos实参置空。

DLListErase接口可以完成头删和尾删：

尾删--->DLListErase ( phead->prev ) ;

头删--->DLListErase ( phead->next ) ; 

十分钟写一个链表可不可能？

是可以做到的，我们写一个双向带头循环链表，头尾插删写一个DLListInsert与一个DLListErase即可完成。

四、顺序表与链表的区别

不同点顺序表链表
存储空间上逻辑、物理上均连续逻辑上连续、物理上不连续
随机访问随机访问1个数据---O(1)随机访问1个数据---需要遍历因此O(N)
任意位置插入或删除元素挪位---O(N)，效率低只需要改变指针指向
插入结点空间扩容---1.浪费空间 2.开辟空间存在消耗插入一个开辟一块，无容量概念
应用场景元素高效存储、频繁访问任意位置的频繁插入删除---均O(1)
缓存利用率高低


http://www.kler.cn/a/429055.html

相关文章：

  • 解决 MySQL 服务无法启动：failed to restart mysql.service unit not found
  • 海云安开发者安全智能助手D10荣膺 “ AI标杆产品 ” 称号，首席科学家齐大伟博士入选2024年度 “ 十大杰出青年 ”
  • 【21】Word：德国旅游业务❗
  • Qt之文件系统操作和读写
  • python实现pdf转word和excel
  • 02.02、返回倒数第 k 个节点
  • Vue 组件通信全面解析
  • 【text2sql】低资源场景下Text2SQL方法
  • 【CKS最新模拟真题】从ETCD 中读取 Secret的键值
  • mac电脑安装hadoop、hive等大数据组件
  • 计算机病毒的特效及种类【知识点+逐字稿+答辩题】----高中信息技术教资面试
  • 设计模式10：观察者模式(订阅-发布)
  • 朗新科技集团如何用云消息队列 RocketMQ 版“快、准、狠”破解业务难题？
  • 生活大爆炸版石头剪刀布(洛谷P1328)
  • SpringBoot 赋能：精铸超稳会员制医疗预约系统，夯实就医数据根基
  • flume对kafka中数据的导入导出、datax对mysql数据库数据的抽取
  • vscode（二）常用的文件变量
  • 基于卷积神经网络的人脸表情识别系统，resnet50，mobilenet模型【pytorch框架+python源码】
  • C# AES
  • spring中的@Bean和@Component有什么区别?
  • CentOS 9 Stream上安装SQL Server 2022
  • OceanBase数据库使用 INSERT 语句违反唯一约束冲突解决办法及两者差异分析
  • python+docker实现分布式存储的demo
  • git commit -m “Add user login feature“
  • Winform（C#）实现下拉列表显示表格（利用自定义组件）
  • Vector软件CANdb++的信号起始位Bug