【开卷数据结构 】 循环链表,双向链表

简介: 【开卷数据结构 】 循环链表,双向链表

前言


在这里【开卷数据结构 】- 2 - 链表我们了解了链表的定义,初始化,以及查找删除操作。


提出问题


之前讲到的链表结点中只有一个指向后续结点的指针域,若从某个结点出发只能顺指针向后一个一个寻查其他结点。若要访问某个结点的前驱节点,只能从头开始遍历。


有什么方法可以克服单链表这种单向性的缺点呢?


答案就是我们今天要介绍的循环链表,双向链表。


🌺循环链表


🔺实现原理

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表,由此,从循环链表中任意一个结点出发都能找到其他结点。

e37a592d4f1fec6e75a2e9606f8f9b5f_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ2V5bGFuXw==,size_20,color_FFFFFF,t_70,g_se,x_16.png


对于这个循环链表,可以用O(1)的时间访问第一个结点,但是要访问最后一个结点,却需要O(n)时间,因为需要将单链表全部扫描一遍。


❓有没有什么方法可以用O(1)的时间由链表指针访问到最后一个结点呢?


我们需要对这个循环链表进行改造,不用头指针,而是用指向终端结点的尾指针来表示循环链表,此时查找开始结点和终端结点都为O(1)的时间了。

7bd7239dffefecbda8ee848ae8bff842_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6ZSh5YWwQ2V5bGFuXw==,size_20,color_FFFFFF,t_70,g_se,x_16.png


🌷循环链表的插入和删除


循环链表的插入,删除算法和单链表的一致,这里就不再赘述了


不了解的可以看看这篇文章【开卷数据结构 】- 2 - 链表


🌷循环链表与单链表的差别


他们的差别在于:


当链表遍历时,判别终止的条件不同。假设当前指针为p,在单链表中判断是否到达终点条件为【p!= NULL】或【p->!= NULL】,循环链表的判断条件为【p->next!= L】


🌺双向链表


🔺实现原理

双链表的结点中有两个指针域,一个指向后一结点,一个指向前一结点,结点结构如图所示



💬 代码演示


双链表结点:


typedef struct DNode
{
  ElemType data;
  struct DNode *prior,*next;
}DNode, *DLinklist;


🌷双向链表插入


在双链表中p所指的结点之后插入结点*s

561f07ca17f9bef2cbbf03680c323f17_cf0ee0b17d3d4f5fb57de5f29b357ea6.png


💬 代码演示


s->next=p->next;            //将结点*插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;


🌷双向链表删除


删除双链表中结点*p的后续结点*q

f8f7b932b9c25d38688b56626f65ade0_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ2V5bGFuXw==,size_20,color_FFFFFF,t_70,g_se,x_16.png


💬 代码演示


p->next=q->next;        //操作一
q->next->prior=p;       //操作二
free(p);                //释放结点空间


🌺结束语


本人不才,如有错误,欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】,不行的话我再努努力💪💪💪


相关文章
|
6天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
30 4
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
6天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
23 0
|
21天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
17 0
|
5天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
62 9
|
1天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
3天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
26 4
|
27天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
26 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
8天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!