`
XiangdongLee
  • 浏览: 90780 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

循环列表和双向列表

阅读更多
本文围绕以下两个部分展开:

一、循环链表(circular linked list)
二、双向链表(double linked list)






一、循环链表(circular linked list)

        1. 概念

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






        2. 与单链表比较

        (1)单链表,每个元素只存储了向后的指针,到了尾标志就停止了向后链的操作。这样,当中某一结点就无法找到它的前驱结点。

        循环链表可以从当中一个结点出发,访问到链表的全部结点。

        (2)循环的判断条件上有差别:单链表:判断p->next是否为空;循环链表:判断p->next是否等于头结点。


        3. 改造:不用头指针,用尾指针好。



        (1)用头指针:可以用O(1)的时间访问开始结点,但访问终端结点由于需要将链表全部扫描一遍,因此需要O(n)的时间。

        而用尾指针访问开始结点和终端结点都用O(1)的时间。

        (2)要将两个循环链表合并为一个表时,有了尾指针就非常简单了。










二、双向链表(double linked list)

        1. 概念

        双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。


        2. 双向链表存储结构




        3. 插入






        4. 删除







        5. 双向循环链表(双向链表带有循环)










整理时重点参考:《大话数据结构》程杰著
0
1
分享到:
评论

相关推荐

    循环链表和双向链表

    总结来说,循环链表和双向链表是链表结构的两种不同类型,它们在数据结构与算法领域中占据着重要地位。通过理解这些链表结构的基本概念和操作方法,可以在实际的编程和应用开发中处理更复杂的数据关系和操作逻辑。

    航班订票系统(单向,双向循环链表)

    本文将深入探讨如何利用单向链表和双向循环链表来构建这样一个系统。我们将讨论标题中的"航班订票系统"、"单向链表"和"双向循环链表"这些核心概念。 首先,我们来看"单向链表"。单向链表是一种线性数据结构,每个...

    循环链表和双向链表.ppt

    循环链表和双向链表是两种特殊类型的线性链表,它们在数据结构中扮演着重要角色,尤其在处理线性关系的数据时。下面将详细讨论这些概念。 首先,我们来看带头结点的链表。在普通链表的基础上,带头结点的链表会在...

    实现循环链表及双向链表3

    循环链表和双向链表是数据结构中的重要概念,它们在计算机科学中有着广泛的应用,尤其是在算法设计和数据存储方面。下面将详细讲解这两种链表的实现原理、操作方法及其优缺点。 首先,我们来看循环链表。循环链表与...

    Linux操作系统中通用双向循环链表的实现分析.pdf

    例如,在进程管理中,Linux内核使用双向循环链表来管理进程队列,该队列中包含了所有的进程控制块(PCB),通过双向循环链表可以快速地插入、删除和查找进程控制块。 在内存管理中,Linux内核使用双向循环链表来...

    双向循环链表(C++)

    双向循环链表是一种特殊的数据结构,它扩展了单链表的概念,允许在链表的任一位置进行前向和后向遍历。在这个话题中,我们将深入探讨如何使用C++来实现双向循环链表,并涵盖其主要功能,如定点插入、定点删除以及...

    c语言 链表 双向链表 双向循环链表

    本文将深入探讨C语言实现的双向链表和双向循环链表,以及如何将这些概念应用于Linux内核。双向链表与单向链表相比,具有更灵活的操作特性,而双向循环链表则在此基础上增加了循环的特性,使得遍历和操作更加方便。 ...

    循环链表和双向链表PPT学习教案.pptx

    循环链表和双向链表是数据结构中的重要概念,它们都是线性表的变体,主要用在存储和操作顺序关系的数据序列。 5.1 带头结点的链表 带头结点的链表是在线性链表的第一个元素之前增加一个特殊的结点,即头结点。头...

    C语言版双向循环链表 双向循环链表经典程序

    C语言版双向循环链表,双向循环链表经典程序,用于指针进行编写的C语言程序。。。

    实现循环链表及双向链表2

    循环链表和双向链表是两种常见的线性数据结构,它们扩展了简单的单链表的概念,提供了更灵活的操作方式。本篇文章将深入探讨这两种数据结构,并以编程实现为视角进行详细解析。 **循环链表** 循环链表是一种链式...

    双向循环链表源码

    在实际应用中,双向循环链表常被用于需要频繁进行双向操作的场景,如实现浏览器的历史记录功能,或者在音乐播放器中前进和后退播放歌曲。由于其循环特性,它也可以用于实现一些无限循环的效果,如轮播图等。 通过这...

    双向循环链表C++实现

    双向循环链表是一种重要的数据结构,它在计算机科学和编程中有着广泛的应用。与单向链表不同,双向循环链表允许元素在正向和反向两个方向上进行遍历,这种特性使得它在需要频繁地进行前向或后向移动操作时特别有用。...

    双向循环链表的C++实现

    在C++中实现双向循环链表,需要对链表的节点结构和操作进行精心设计。 首先,我们来看双向链表的节点结构。在C++中,通常会定义一个名为`node`的类来表示链表中的节点。节点包含三个主要部分:元素值`m_element`、...

    带头结点的双向循环链表

    双向循环链表是一种高级的数据结构,常用于需要前后移动指针的场景,如实现LRU缓存淘汰策略、编辑器的撤销重做功能等。本项目以C++语言实现了带头结点的双向循环链表,这将有助于我们深入理解这一概念。 首先,双向...

    数据结构课程设计报告基于双向循环链表的通讯录设计

    双向循环链表是一种链式存储结构,每个节点包含指向其前后节点的指针,且整个列表形成一个闭环,使得可以从任一节点开始遍历整个列表。在通讯录设计中,双向循环链表提供了高效的信息检索、插入和删除操作。例如,在...

    双向循环链表C代码实现

    在提供的压缩包中,包含两个文件——stack.cpp 和 stack.h,它们可能实现了基于双向循环链表的栈数据结构。栈是一种后进先出(LIFO)的数据结构,常用于函数调用、表达式求值等场景。在链表中实现栈,通常会在链表...

    实现循环链表及双向链表1

    在计算机科学中,数据结构是程序设计的基础,而链表作为一种基本的数据结构,常常用于解决各种问题。...在编程中,熟练掌握双向链表和循环链表的原理和操作方法,对于解决复杂问题和优化算法性能具有重要意义。

    双向循环链表来实现长整数四则运算

    在本实验中,我们利用双向循环链表来实现长整数的存储和四则运算,特别是加法和减法。这种数据结构的选择主要是因为它能够方便地处理长整数的存储和运算过程中的进位和借位操作。 首先,双向循环链表的每个节点仅...

    C语言中双向链表和双向循环链表详解

    C语言中双向链表和双向循环链表详解 本文主要介绍了C语言中双向链表和双向循环链表的实现与操作,包括双向链表和双向循环链表的定义、初始化、插入操作、删除操作等。 一、双向链表和双向循环链表的定义 在C语言...

Global site tag (gtag.js) - Google Analytics