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

【数据结构】—— 双向循环链表

article 2024/11/24 23:59:31

引入

在正式学习双向循环链表的之前，我们先了解什么是循环链表、什么是双向链表。

循环链表

对于单链表，由于每个结点只存储了其后继结点的指针，到了尾标志（NULL)就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了，就像我们平时所说的不能回到从前。

比如，你是一业务员，家在上海。需要经常出差，行程就是上海到北京一路上的城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留后，再乘飞机返回上海，以后，每隔一段时间，你基本还要按照这样的行程开展业务，如下图所示：

 有一次，你先到南京开会，接下来要对以上的城市走一遍，此时有人对你说，不行，你得从上海开始，因为上海是第一站。你会对这人说什么？神经病。哪有这么傻的，直接回上海根本没有必要，你可以从南京开始，下一站蚌埠，直到北京，之后再考虑走完上海及苏南的几个城市。显然这表示你是从当中一结点开始遍历整个链表，这都是原来的单链表结构解决不了的问题。

事实上，把北京和上海之间连起来，形成一个环就解决了前面所面临的困难。这就是我们现在要讲的循环链表。

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circularlinkedlist)。

从刚才的例子，可以总结出，循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。循环链表带有头结点的空链表如图所示：

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断 p->next是否为空，现在则是 p->next不等于头结点。
在单链表中，我们有了头结点时，我们可以用 O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要 O(n)时间，因为我们需要将单链表全部扫描一遍。

有没有可能用 0(1)的时间由链表指针访问到最后一个结点呢?当然可以。不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针。结构如下所示：

从上图中可以看到，终端结点用尾指针 rear 指示，则查找终端结点是 O(1)，而开始结点，其实就是 rear->next>next，其时间复杂也为O(1)。

双向链表

继续我们刚才的例子，你平时都是从上海一路停留到北京的，可是这一次，你得先到北京开会，谁叫北京是首都呢，会就是多。开完会后，你需要例行公事，走访各个城市，此时你怎么办?

有人又出主意了，你可以先飞回上海，一路再乘火车走遍这几个城市，到了北京后，你再飞回上海。你会感慨，人生中为什么总会有这样出馊主意的人存在呢?真要气死人才行。哪来这么麻烦，我一路从北京坐火车或汽车回去不就完了吗。

对呀，其实生活中类似的小智慧比比皆是，并不会那么的死板教条。我们的单链表，总是从头到尾找结点，难道就不可以正反遍历都可以吗？当然可以，只不过需要加点东西而已。
我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度头O(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历查找。
为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。双向链(doubke linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。结构图如下：

 对于双向循环链表结构定义如下：

typedef int DataType;
typedef struct List
{
	struct List* prev;//前驱结点
	DataType val;
	struct List* next;//后继结点
}List;

到此，我们的铺垫知识全部结束，开始我们的正题！

双向循环链表

预备处理

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表，双向链表的循环带头结点的空链表如图所示。

双向循环链表同单链表的操作有所不同，双向循环链表需要初始化（带头结点)；将头结点的前驱和后继指针全部指向自己。初始化结构如下图所示

 代码实现如下：

void init(List* phead)
{
	assert(phead);
	phead->next = phead;
	phead->prev = phead;
}

 由于该链表实现采用动态开辟堆内存的形式，所以需要经常使用malloc，所以我们这里先对内存开辟进行封装：代码实现如下：

List* CreateSpace()
{
	List* Node = (List*)malloc(sizeof(struct List));
	assert(Node);//可能内存没开辟成功
	Node->prev = NULL;
	Node->next = NULL;
	return Node;
}

 插入操作

对于双向循环链表的插入操作，其实不是难理解，主要是代码实现顺序问题。

###头插操作

对于链表的头操作实现如下：

  1. 为插入的结点n开辟空间
  2. 将n的后继结点指向头结点的后继结点
  3. 将n的前驱结点指向头结点
  4. 将头结点的后继结点指向结点n

 代码实现如下：

void HeadInsert(List* phead, DataType x)
{
	assert(phead);
	List* first = phead->next;
	List* tail = phead->prev;
	List* newNode = CreateSpace();//开辟空间
	newNode->val = x;
	//不论该带头链表中是否有结点都可行
	phead->next = newNode;//表头连接新结点
	newNode->prev = phead;//新结点连接表头

	//当链表中有结点时：下列语句作用是相互连接后面的结点
	//当链表中没有结点时：下列语句作用是构成循环链表
	newNode->next = first;
	first->prev = newNode;
	
}

###尾插操作

由于我们是双向循环链表，相较于单链表，我们可以在O(1)的时间复杂度下访问尾结点rear，即rear = head->prev；那么我们也可以在O(1)的时间内尾插结点，（单链表尾插的时间复杂度为O(n)，需要遍历链表)。

实现思路：

  1. 为新结点newNode开辟空间
  2. 获取尾结点Tail
  3. 将newNode的后继结点指向头结点
  4. 将尾结点Tail的后继结点指向新结点newNode
  5. 将newNode的前驱结点指向尾结点Tail
  6. 将头结点的前驱结点指向新结点newNode

代码实现：

void TailInsert(List* phead, DataType x)
{
	assert(phead);
	List* newNode = CreateSpace();
	newNode->val = x;
	List* Tail = phead->prev;
	//将新结点的prev指向到链表的尾指针
	newNode->prev = Tail;
	newNode->next = phead;//指向表头，构成循环链表

	Tail->next = newNode;//新结点连接在尾结点的后面
	phead->prev = newNode;//指向新结点，构成循环链表
	
}

 对于任意位置的随机插入，也就没有什么难度了，同单链表一样，需要去遍历链表，找到第i结点，唯一需要注意的是在遍历的过程中需要注意循环条件的判断，node->next != head ；不然很容易死循环。其他的操作基本类似，不再赘述。

删除操作

###头删

头删和单链表的头删没有任何区别，主要是需要注意代码书写的顺序。头删操作在这两种链表的时间复杂度都为O(1)。

实现思路：

  1. 获取头指针
  2. 将头结点的后继指向头指针的后继
  3. 将头指针的的后继结点的前驱指向头结点
  4. 释放头指针的空间

代码实现如下：如果感觉不理解，可以参考上面的图自己模拟一下！

void HeadDel(List* phead)
{
	assert(phead);
	//链表为空时，不删除结点
	assert(phead->next != phead);
	List* first = phead->next;
	List* next = first->next;//记录第一个结点的下一个结点

	//当链表结点数>=2时，用来连接表头
	//当链表结点数<2时，用来连接成循环链表
	phead->next = next;
	next->prev = phead;
	free(first);
}

【注意】：不能把头节点给释放掉，链表为空是，就不用再删除了。

###尾删

尾删好像也没什么差别吧！相较于单链表，双向循环链表的时间复杂度为O(1)。

实现思路：

  1. 获取尾结点Tail
  2. 将尾结点Tail的前驱结点的后继指向头结点
  3. 将头结点的前驱指向尾结点的前驱结点
  4. 释放尾结点

代码实现：

void TailDel(List* phead)
{
	assert(phead);
	assert(phead->prev != phead);
	List* tail = phead->prev;
	List* tailPrev = tail->prev;//记录尾结点的上一个结点

	//指向表头，构成循环链表
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
}

注意点和头删一样，注意链表为空时，不要把头结点给释放了！！！

最后补充一点，如何遍历整个双向循环链表：注意循环条件！！！

void ShowList(List* phead)
{
	if (phead->next == phead)
	{
		printf("NULL");
		return;
	}
	List* cur = phead->next;
	while (cur != phead)//注意循环进行条件，防止死循环
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");

}

总结

好了，简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟它多了prev 指针，对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多一些的。不过，由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。

到此，数据结构——线性表就全部结束。我们的重点，由顺序存储结构的插入和删除操作不方便，引出了链式存储结构。它具有不受固定的存储空间限制，可以比较快捷的插入和删除操作的特点。然后我们分别就链式存储结构的不同形式，如单链表、循环链表、双向链表和双向循环链表做了讲解，另外我们还拓展若不使用指针如何处理链表结构的静态链表方法。


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

相关文章：

  • Linux设置以及软件的安装(hadoop集群安装02)
  • 学习编程，学习中间件，学习源码的思路
  • python代码制作数据集的测试和数据质量检测思路
  • DataGear 企业版 1.3.0 发布，数据可视化分析平台
  • 如何理解 TypeScript 中命名空间与模块？两者都有那些区别？如何更好的应用？
  • k8s篇之控制器类型以及各自的适用场景
  • PaddleNLP的环境配置：
  • 如何在Linux系统中排查GPU上运行的程序
  • 阿里云ECS服务器监控报警配置
  • 社交电商专业赋能高校教育与产业协同发展：定制开发AI智能名片及2+1链动商城小程序的创新驱动
  • 加速科技精彩亮相中国国际半导体博览会IC China 2024
  • 解决 GitHub 克隆私有仓库时的身份验证失败问题
  • uni app下开发AI运动小程序解决方案
  • LDR6020驱动的Type-C接口显示器解决方案
  • （免费送源码）计算机毕业设计原创定制：Java+JSP+HTML+JQUERY+AJAX+MySQL springboot计算机类专业考研学习网站管理系统
  • 数字八股文
  • web——sqliabs靶场——第十二关——(基于错误的双引号 POST 型字符型变形的注入)
  • 数据结构：链表进阶
  • React Native的`react-native-reanimated`库中的`useAnimatedStyle`钩子来创建一个动画样式
  • 【JAVA】Java基础—面向对象编程：常用API与数据结构—常用工具类（Collections、Arrays等）
  • qt自定义虚线并添加进QGridLayout
  • Spring-02-springmvc
  • Failed to start Docker Application Container Engine
  • Java-08 深入浅出 MyBatis - 多对多模型 SqlMapConfig 与 Mapper 详细讲解测试
  • Vue3+SpringBoot3+Sa-Token+Redis+mysql8通用权限系统
  • Elasticsearch面试内容整理-Elasticsearch 版本差异