-
2021-04-20 14:16:27
前言：
线性表是我们最常用的一种数据结构，线性表包含顺序表和链表，顺序表典型应用就是我们常用的ArrayList，链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结链表中的双向循环链表，为单链表的结点增加一个指向前驱的指针域，单链表就变成了双链表，将双链表的头尾相连，双链表就成了双向循环链表。一、相关概念
第一部分主要介绍下和链表有关的相关概念，这里给出的概念都是书本上的官方定义，并不是作者胡诌的，为什么给出这些官方的定义呢 ？因为笔者认为官方给出的定义，是对一个概念最本质的解释，它的解释经过了时间的考验，被认为是解释的最合理深入简明扼要的。
1.什么是线性表
线性表是由n个数据元素构成的有限序列，n为线性表的表长，当n为0时表示当前线性表是空表。线性表有且仅有一个开始结点和终端节点。且开始结点没有前驱，终端节点没有后继，其余节点有且仅有一个前驱和后继。线性表一般分为顺序表和链表。
2.什么是顺序表
采用顺序存储结构存储数据元素的线性表被称为顺序表，顺序表，要求逻辑上相邻的数据元素在物理内存的存储上也是相邻的，当在顺序表的第i（0<=i<=n）插入一个数据元素时，需要后移n-i+1个数据元素，当删除第i个元素时需要移动n-i个数据元素。java实现顺序表
3.什么是链表
采用链式存储结构存储数据元素的线性表被称为链表，链表不要求逻辑上相邻的数据元素内存上必须相邻，链表的每个节点都包含两部分，一部分是数据域用以存储数据，一部分是指针域用以存储指向相邻结点的指针或者引用。链表通过每个节点的指针域将一串数据串联成链。当结点只有一个指针域时，被称为单链表。单链表-含头结点、单链表-不含头结点
4.单链表、双链表、循环单链表、循环双链表
当链表的结点只有一个指针域时被称为单链表，循环单链表是单链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。
当链表的结点有两个时，一个指向前驱，一个指向后继这种链表便是双链表，循环双链表是双链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。
所有的链表的实现均有两种方式，一种是带有头结点，一种是不带有头结点的实现方式，两种实现略有区别。5.为什么需要循环链表？
循环链表一般就是指循环单链表，不特殊指明是双向循环链表，那么该名称描述的就是单项循环链表，之所以需要循环链表是因为在操作系统中，循环链表有特定的应用场景，在一些场景中，链表中的元素需要循环的执行，但是在实际的开发中应用最多的还是双向循环链表。
6.为什么需要双向链表？
若是给定了一个结点，根据当前结点获取该结点的上一个结点，那么我们是没有办法直接获取的，只能是遍历链表，但若是使用了双向链表，我们则可以直接获取到该元素的上一个结点，时间复杂度就变成了O(1)。所以双向链表的实际应用意义更强，将双向链表的首尾相连就成了双向循环链表，双向循环链表的应用最常见的就是LinkedList。
7.头结点和首结点
首节点：真正存储第一个数据元素的结点被称为首节点。
头结点：当链表采用带头结点方式实现时，会创建一个数据域为null的节点，该节点的指针域存储的指针指向首节点的指针，他的唯一作用是标识链表的开始，带有头结点的链表更易于操作。8.常见的栈和队列与线性表的关系
栈和队列也是常见的数据结构，但是栈和队列并不是线性表的一种，线性表只包含了顺序表和链表。不过我们可以将栈和队列看成是特殊的线性表。怎么特殊呢，栈是被限制了只能在一端进行插入和删除操作的线性表，所以栈的特性是先入后出，队列是被限制了只能在一端插入另一端删除的线性表，所以队列的特性是先入先出。既然栈和队列都是特殊的线性表，那么栈和队列自然就可以使用线性表来实现了，通常可以使用线性表中的顺序表和队列来实现栈和队列。
二、实现过程
单链表-含头结点
单链表-不含头结点
上面是两种单链表的实现方式，其实无论是双链表还是双向循环链表他的实现方式都是类似的，区别都很有限，上面两篇文章里详细实现了单链表的各种常用方法，因此在该文章里只会总结必须用到的几个方法，比如插入、删除、清空、长度、判空、根据下标获取等，其他方法的实现都不难，就不一一展示了。1.提供节点类：DupNode
双向循环链表的实现，我们首先必须为其提供一个结点类，该类需要有三个属性，一个数据域，一个指向前驱的指针域，还有一个指向后继的指针域，然后提供必要的构造方法即可，如下：
/** * @author pcc * @version 1.0.0 * @className DupNode * @date 2021-04-19 16:43 * 该类是双向链表的结点类 * 该类包含了数据域，后继指针域、前驱指针域三个属性。 */ public class DupNode { Object object; DupNode prior;//前驱指针域 DupNode next;//后继指针域 public DupNode(){ this(null); } public DupNode(Object object){ this(object,null,null); } public DupNode(Object object,DupNode prior,DupNode next){ this.object = object; this.prior = prior; this.next = next; } }2.提供双向循环链表的实现类：DoubleLinkedTable
采用带有头结点的方式实现双向循环链表，因此我们需要定义一个头结点。然后提供初始化它的构造器。值得注意的是，在初始化头结点时，我们必须将他的前驱和后继都声明为自己，这样才是一个空的双向循环链表。
public class DoubleLinkedTable { //头结点 DupNode head; public DoubleLinkedTable(){ head = new DupNode(); head.prior = head; head.next = head; } }3.提供长度(length)、打印(display)、清空(clear)等方法
这些方法的实现原理都很简单，求链表长就是遍历链表计数即可，打印也是遍历链表，清空则是将头结点的前驱和后继都声明为自己，下面是三个方法的实现：
//长度 public int length(){ DupNode node = head.next; int j = 0; while(!node.equals(head)){ j++; node = node.next; } return j; } //打印 public void display(){ DupNode node = head.next; while(!node.equals(head)){ System.out.println(node.object); node = node.next; } } //清空 public void clear(){ head.next = head; head.prior = head; }4.提供根据下标插入方法：insert(int i,Object object)
学习双向循环链表建议还是先学习单链表，会了单链表双向循环链表就是窗户纸，一桶就破，因为他们的实现思路都是一样的，只是稍微的变化而已。单链表的遍历我们的退出条件是找到尾结点就退出（node.next == null）,循环链表肯定没有尾结点了，退出循环的条件就成了碰到头结点再退出（node ==head）,另外一点区别就是双向循环链表的赋值问题，我们需要为新结点的前驱指针和后继指针赋值，同时需要为新结点的上一个节点的后继后继指针从新赋值，还需要为新节点的后继结点的前驱指针重新赋值，代码实现如下：/** * 思路： * 1.寻找下标为i-1的数据元素，注意退出循环的条件应该是node！=head * 2.赋值即可，循环链表的核心就是空表也会有循环体系 * 3，赋值时，i+1位置的元素应该是node.next 所以，应为node.next最后赋值 * @param i * @param object * @throws Exception */ public void insert(int i,Object object) throws Exception{ if(i<0 || i>length()) throw new Exception("下标不合法"); DupNode node = head; int j = 0; while(!node.next.equals(head) && j<i){ j++; node = node.next; } // DupNode newNode = new DupNode(object); // node.next.prior = newNode; // newNode.prior = node; // newNode.next = node.next; // node.next = newNode; //写成以下这种和上面注释的部分，效果一样，无区别 DupNode newNode = new DupNode(object,node,node.next); node.next.prior = newNode; node.next = newNode; }到了这里，我们就可以初步测试下，双向链表的插入是否有效了，下面创建一个测试类测试下，如下图所示，将几个元素插入到了双向循环链表中，然后输出结果正常，说明插入方法实现无误。有了这些头插法、尾插法直接根据下标即可轻松实现，这里不展示了。
5.提供根据下标删除的方法：remove(int i)
实现思路其实和单链表的删除是没有区别的：寻找到下标为i-1的数据元素，然后将他的后继更改为i+1的数据元素，然后将下标为i+1的数据元素的前驱更改为，下标为i-1的数据元素即可，实现如下：
//删除 public void remove(int i) throws Exception{ if(i<0 || i>length()-1) throw new Exception("下标不合法"); DupNode node = head; int j = 0; while(!node.next.equals(head) && j<i){ j++; node = node.next; } node.next = node.next.next; node.next.prior = node; }然后来测试下删除方法，就测试下删除下标为2的元素吧，理论上删除后，输出的应该是：张三、李四、赵柳，如下图可见，输出无误，可见删除方法实现时无误的。
6.提供根据下标获取方法(get(int i))、根据指定结点获取前一个结点方法(getPrior)、根据指定结点获取后一个结点信息方法(getNext)
上面也说过，双向链表解决的问题就是在获取指定结点的上一个结点时是无需遍历链表的，这样大大节省了时间成本，这里就测试下该方法的实现。三个方法的实现如下所示：
//根据下标获取 public Object get(int i) throws Exception{ return getNode(i).object; } //根据下标获取其前一个元素 public Object getPrior(int i) throws Exception{ return getNode(i).prior.object; } //根据下标获取其后一个元素 public Object getNext(int i) throws Exception{ return getNode(i).next.object; } public DupNode getNode(int i) throws Exception{ if(i<0 || i>length()) throw new Exception("下标不合法"); DupNode node = head.next; int j =0; while(node.equals(head) && j<i){ j++; node = node.next; } return node; }下面我们来测试下这三个方法是否正确，使用李四所在结点来进行测试，李四的下标应该是1，传入1分别运行三个方法，若是正确应该输出的是：李四、张三、王五，如下图可见结果正确。
三、总结
1.链表的缺点
线性表的两种实现顺序表、链表。相比于顺序表，链表的缺点就是查找元素比较慢，查找元素的时间复杂度是O(n),而顺序表的时间复杂度是O(1)，在查找上顺序表要优于链表,链表查找慢，就是它的缺点了，但是双向循环链表在一定程度上减少了查找时的时间复杂度，但是依然是不及顺序表的查找效率的，所以具体的使用场景还是静态数据适合使用顺序表，动态数据适合使用链表。
2.链表的优点
顺序表在指定下标x位置插入元素，组需要后移n-x+1个元素，若是删除下标为x的数据元素，则需要向前移动n-x个数据元素，但是链表则不需要移动任何元素，链表需要做的只是找到对应的元素将指针域中的指针进行更新即可。链表的插入和删除的时间复杂度可以看成O(1)，而顺序表插入和删除操作的都是O(n).所以链表的优点就是插入和删除比较快。
3.如何使用链表
所以综合链表的优点与缺点我们可以发现，顺序表更适合存储“静态”型数据，而链表更适合存储“动态”型数据，何为动态型呢，就是那些插入、删除操作比较频繁的数据。这类数据更适合使用链表存储。而数据结构不易改变的数据使用顺序表存储更合适。顺序表可类比java中的ArrayList，链表可类比java中的LinkedList。这两者都是顺序表与链表的典型应用。
更多相关内容 -
循环双链表
2018-09-12 19:40:16基于C高级的双向循环链表，可以选择头插还是尾插两种插入方式，及增加节点，删除节点 -
C语言使用非循环双向链表实现队列
2020-12-22 18:50:15第二，大家在很多书上看到的是使用单链表实现队列，我这里将会使用带头结点尾结点的非循环双链表实现，虽然多维护了两个节点和指针域，但是在链表头尾进行插入删除的时候不需要遍历链表了，队列操作变得非常 -
java双向循环链表的实现代码
2020-09-05 01:05:26介绍了java双向循环链表的实现代码，有需要的朋友可以参考一下 -
C语言中双向链表和双向循环链表详解
2020-08-30 05:38:01主要介绍了C语言中双向链表和双向循环链表详解的相关资料,需要的朋友可以参考下 -
深入解析C++的循环链表与双向链表设计的API实现
2021-01-01 16:04:23在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。 循环链表新操作 将游标重置指向链表中的第一个数据元素 CircleListNode* CircleList_Reset(CircleList... -
Python双向循环链表实现方法分析
2020-12-23 21:37:06遇到一个问题就是双向循环链表的实现，改指向的时候总是发蒙。 我自己尝实现了一个python的双向循环链表。附上代码，希望对大家有帮助。 如果不懂什么是双向循环链表的伙伴，需要补习一下数据结构的基础之后哦~~~ 在... -
JavaScript数据结构之双向链表和双向循环链表的实现
2020-10-18 23:00:21本篇文章主要介绍了JavaScript数据结构之双向链表和双向循环链表的实现，具有一定的参考价值，感兴趣的小伙伴们可以参考一下 -
删除循环双链表中的第一个X
2015-11-27 14:18:59创建一个循环双链表，P指向第一个元素值为X的结点，设计一个算法从该链表中删除*P结点。 -
双向循环链表
2017-10-13 14:10:31双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表... -
带头结点的双向循环链表
2018-07-17 08:32:11C++实现的带头结点的双向循环链表， 数据结构课设.。 -
基于java的循环双链表
2015-12-22 22:40:15使用java语言编译循环双链表，有三个类，分别是一个接口类，一个循环双链表继承接口的实现类，一个循环双链表的测试类 -
双向循环链表C++实现
2016-12-11 10:13:18数据结构课程设计实现双向循环链表，我这有详细的课程设计说明书以及答辩ppt，有需要的可以留言哈 ，仅供参考 嘿嘿 -
循环双向链表（C语言）
2014-09-17 18:16:25循环双向链表，实现了插入、查找特定的节点、删除等功能，是自己花了半天的时间写完的。 -
【线性表】链表：循环单链表、双链表、循环双链表的基本特性
2020-06-06 14:09:57链表不仅作为链式存储的一种实现方式，还表达了计算机不连续（离散）的存储思想。展开全文链表不仅作为链式存储的一种实现方式，还表达了计算机不连续（离散）的存储思想。在初学阶段，链表的实现类型有单链表（带/不带头结点）、循环单链表、双链表、循环双链表四种。
上文已经讲解了单链表，接下来将讲解其他三类。
Table of Contents
循环单链表
定义：
将单链表中终端结点的指针端由 NULL 改为 指向头结点 ，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
两种情形：
- 为使空链表与非空链表处理一致，通常设置一个头结点。但并非必须设置头结点。
循环单链表特征：
- 对于单链表而言，最后一个结点指向NULL；把最后一个结点的不指向NULL而指向头，就是循环单链表；
- 在单循环链表上的操作基本上与非循环链表相同。循环链表和单链表的主要差异就在于循环的条件判断上，原来是 p->next == NULL，现在是 p->next != 头结点 ，则循环未结束。
- 单循环链表可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行。如果用头指针表示循环链表，则需O(n) 时间找到最后一个结点。若改用尾指针表示循环链表，此时查找开始结点和终端结点都很方便了。查找终端结点时间是O(1)，而开始结点，其实就是 rear->next->next ，其时间复杂也为O(1)。
第一个循环单链表
#include <stdio.h> #include <malloc.h> #include <assert.h> typedef struct node { int data; struct node* next; }Node; //struct node 完全等于 Node（结构体变量） typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针） int main() { LinkList head = (LinkList)malloc(sizeof(Node)); assert(head != NULL); //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用） LinkList NodeAa = (LinkList)malloc(sizeof(Node)); assert(NodeAa != NULL); LinkList NodeBb = (LinkList)malloc(sizeof(Node)); assert(NodeBb != NULL); LinkList NodeCc = (LinkList)malloc(sizeof(Node)); assert(NodeCc != NULL); head->data = NULL; //头结点，不保存数据 head->next = NodeAa; NodeAa->data = 202; NodeAa->next = NodeBb; NodeBb->data = 303; NodeBb->next = NodeCc; NodeCc->data = 404; NodeCc->next = head; //单链表中：NodeCc->next = NULL; LinkList p = head->next; //把链表头结点的下一个节点，交给指针p，去遍历 while (p != head) { printf("%d ", p->data); p = p->next; } return 0; }
双链表
定义：
双向链表也叫双链表，它的每个数据结点中都有两个指针（保存两个节点的地址），分别指向直接后继和直接前驱。
双链表的代码定义：
typedef struct node { int data; struct node* pre; //前驱 struct node* next; //后继 }Node;特性：
- 从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
- 循环链表的最后一个结点指向头结点，循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
- 双向链表使单链表中扩展出来的结构，因此有一部分操作与单链表是相同的，如求长度函数、查找元素位置、打印函数、销毁函数等，这些函数操作都只要涉及一个方向的指针即可。
第一个双链表
第一个双链表 #include <stdio.h> #include <malloc.h> #include <assert.h> typedef struct node { int data; struct node* pre; struct node* next; }Node; //struct node 完全等于 Node（结构体变量） typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针） int main() { LinkList head = (LinkList)malloc(sizeof(Node)); assert(head != NULL); //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用） LinkList NodeAa = (LinkList)malloc(sizeof(Node)); assert(NodeAa != NULL); LinkList NodeBb = (LinkList)malloc(sizeof(Node)); assert(NodeBb != NULL); LinkList NodeCc = (LinkList)malloc(sizeof(Node)); assert(NodeCc != NULL); head->data = 101; head->pre = NULL; head->next = NodeAa; NodeAa->data = 202; NodeAa->pre = head; NodeAa->next = NodeBb; NodeBb->data = 303; NodeBb->pre = NodeAa; NodeBb->next = NodeCc; NodeCc->data = 404; NodeCc->pre = NodeBb; NodeCc->next = NULL; //单链表中：NodeCc->next = NULL; LinkList p = head; //把链表头结点的下一个交给指针p，去遍历 printf("顺序遍历："); while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n逆序遍历："); LinkList tail = NodeCc; p = tail; while (p != NULL) { printf("%d ", p->data); p = p->pre; } return 0; }
循环双链表
定义：
双向链表也叫双链表，它的每个数据结点中都有两个指针（保存两个节点的地址），分别指向直接后继和直接前驱。头指针的前驱指向最后一个节点，最后一个节点的后继指向头指针。
双链表的代码定义：
typedef struct node { int data; struct node* pre; //前驱 struct node* next; //后继 }Node;特性：
- 从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
- 循环链表的最后一个结点指向头结点，循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
- 双向链表使单链表中扩展出来的结构，因此有一部分操作与单链表是相同的，如求长度函数、查找元素位置、打印函数、销毁函数等，这些函数操作都只要涉及一个方向的指针即可。
两种情形：
第一个循环双链表
#include <stdio.h> #include <malloc.h> #include <assert.h> typedef struct node { int data; struct node* pre; struct node* next; }Node; //struct node 完全等于 Node（结构体变量） typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针） int main() { LinkList head = (LinkList)malloc(sizeof(Node)); assert(head != NULL); //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用） LinkList NodeAa = (LinkList)malloc(sizeof(Node)); assert(NodeAa != NULL); LinkList NodeBb = (LinkList)malloc(sizeof(Node)); assert(NodeBb != NULL); LinkList NodeCc = (LinkList)malloc(sizeof(Node)); assert(NodeCc != NULL); head->data = NULL; //头结点，不保存数据 head->pre = NodeCc; head->next = NodeAa; NodeAa->data = 202; NodeAa->pre = head; NodeAa->next = NodeBb; NodeBb->data = 303; NodeBb->pre = NodeAa; NodeBb->next = NodeCc; NodeCc->data = 404; NodeCc->pre = NodeBb; NodeCc->next = head; //单链表中：NodeCc->next = NULL; LinkList p = head->next; //把链表头结点的下一个交给指针p，去遍历 printf("顺序遍历："); while (p != head) { printf("%d ", p->data); p = p->next; } printf("\n逆序遍历："); p = p->pre; while (p != head) { printf("%d ", p->data); p = p->pre; } return 0; }
-
循环双链表 CDList.h
2021-12-17 23:48:12在Linux内核源码list.h基础上，修改成应用层使用的头文件 实现了循环双链表的的各功能函数和宏定义，包括但不限于链表的创建、插入、删除、遍历。 -
删除循环双向链表中指定元素
2013-11-05 23:46:47本小程序是对于循环双向链表中删除指定元素 考虑几种边界情况! -
数据结构——“双向循环链表“ 易懂刨析双向循环链表（图解+代码）
2022-04-27 12:13:05循环链表单向循环链表双向循环链表1. 双向循环链表——插入2. 双向循环链表——删除 单向循环链表 关于两个循环链表合并为一个循环链表 双向循环链表 在单链表L中，查找ai的后继Next(L，a;)，耗时仅为O(1)，因为...展开全文循环链表
单向循环链表
循环链表和单链表的区别
-
表中最后结点的指针不是NULL，而是改为指向头结点，从而整个链表形成了一个环。
-
循环单链表中没有指针域为NULL的结点，故判空条件为判断
*A （表尾节点）*A 的next是否为头指针 -
空表：
if(A->next == H){ 空表 }
循环链表的特点
- 循环单链表插入，删除算法于单链表几乎一样
正是因为循环单链表是一个“环”，在任何位置插入和删除操作都是等价的，无须判断是否是表全。循环链表可以从任意一个结点开始遍历整个链表，循环链表不设头指针而仅设尾指针，若只
设置尾指针A，A->next即为头指针，对表头，表尾进行操作都只要O(n).- 关于两个循环链表合并为一个循环链表
双向循环链表——概念
在单链表L中，查找
ai的后继Next(L，a;)，耗时仅为O(1)，因为取ai后继指针即可。
但查找ai的直接前驱Prior(L，ai);则需从链表的头指针开始，找到结点ai前一结点即是。故运算Prior(L，ai)依赖表长n，耗时为O(n)。另外，若链表中有一指针值被破坏，则整个链表脱节。这是单链表的不足为此，引入双向链表。先定义双向链表中的结点:
其中，data和next同单链表，增加一指针域prior，其指向本结点的直接前驱。
结点描述:typedef int data_t; typedef struct dnode_t { data_tdata; struct dnode_t *prior; struct dnode_t *next; }dlinknode_t , *dlinklist_t;- 表L=(a0·····an-1)(设n=2) 的双向循环链表如图：
设p为链表中某结点的指针，有对称性：
(p->prior)->next = p =(p->next)->prior- 双向链表的查找等运算基本上和单链表类似。
- 在双向循环链表中，某结点
*p 为尾结点时，p->next == H,当循环双链表尾空表时，某头结点的prior域和next域都等于H
下面我们学习一下双向循环链表的插入和删除运算
1. 双向循环链表——插入
插入： 即实现在链表L的第i结点前插入一结点x的运算，如图
① q->prior = p->prior; ② (p->prior)->next = q; ③ q->next = p; ④ p->prior=q;- 算法思路：
调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);
2. 双向循环链表——删除
删除： 即实现删除链表
L的第i结点的运算，如图
- 算法思路：
调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除
概念我们了解了，接下来我们要去实现双向链表的操作。
双向链表的插入创建
文件一：
dlist.h插入创建双向链表#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); #endif
文件二：dlist.c插入创建双向链表#include"dlist.h" //创建双向链表 dlistnode *dlist_create(){ dlistnode *H,*p,*r; int num; if(( H =(dlistnode *)malloc(sizeof(dlistnode))) == NULL){ puts("malloc failed"); return NULL; } //建立空双向链表 H->prior = H; //头结点前驱后继都指向自己 H->next = H; r = H; //指针r 指向头结点 //用户输入 while(1) { puts("please input(-1 exit):"); scanf("%d",&num); if(num == -1){ puts("-1 exit"); break; } if((p = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){ puts("malloc failed"); return NULL; } //新节点赋值 p->data = num; //插入双向链表 p->prior = r; p->next = r->next; r->next = p; H->prior = p; r = p; } return H; } //遍历链表并输出链表数据 void dlist_show(dlistnode *H){ dlistnode *p; p = H->next; while(p != H){ printf("%d ",p->data); p=p->next; } puts(""); }文件三：
test.c插入创建双向链表#include"dlist.h" int main(){ dlistnode *H; H=dlist_create(); dlist_show(H); return 0; }
双向链表——查找
查找：
getlist(L,i);提供要查找结点ai的编号，返回指向该结点ai的指针
结点个数 n=3;i的范围【0，n-1】文件一：
dlist.h插入创建双向链表#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); extern dlistnode *dlist_get(dlistnode *H,int pos)； #endif文件二：
dlist.c按位查找双向链表dlistnode *dlist_get(dlistnode *H,int pos){ int i =-1; dlistnode *p = H; if(pos < 0){ puts("pos < 0,invalid"); return NULL; } while(i < pos){ p = p->next; i++; if(p == H){ puts("pos is invalid"); return NULL; } } return p; }文件三：
test.c用户输入按位查找双向链表#include"dlist.h" int main(){ dlistnode *H,*p; int pos; H=dlist_create(); dlist_show(H); //用户输入按位查找 while(1){ puts("input pos"); scanf("%d",&pos); p = dlist_get(H,pos); if(p){ printf("%d \n",p->data); } } return 0; }
双向链表——插入
插入： 即实现在链表L的第i结点前插入一结点x的运算，如图
- 算法思路：
调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);
文件一：
dlist.h插入创建双向链表#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); extern dlistnode *dlist_get(dlistnode *H,int pos); extern int dlist_insert(dlistnode *H , int value ,int pos); #endif文件二：
dlist.c按位插入双向链表int dlist_insert(dlistnode *H , int value ,int pos){ dlistnode *p,*q; p = dlist_get(H,pos); if(p == NULL){ return -1; } if((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){ puts("malloc failed"); return -1; } q->data = value; q->prior = p->prior; q->next = p; p->prior->next = q; q->prior = q; return 0; }文件三：
test.c用户输入按位插入双向链表#include"dlist.h" int main(){ dlistnode *H; int pos; H=dlist_create(); dlist_show(H); //用户输入按位查找 while(1){ puts("input pos"); scanf("%d",&pos); dlist_insert(H,100,pos); dlist_show(H); } return 0; }
双向链表——删除
删除： 即实现删除链表
L的第i结点的运算，如图
p->prior->next = p->next; p->next->prior = p-prior;- 算法思路：
调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除
文件一：dlist.h插入创建双向链表
#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); extern dlistnode *dlist_get(dlistnode *H,int pos); extern int dlist_insert(dlistnode *H , int value ,int pos); extern int dlist_delete(dlistnode *H ,int pos); #endif文件二：
dlist.c用户输入按位删除双向链表int dlist_delete(dlistnode *H ,int pos){ dlistnode *p; p = dlist_get(H,pos); if(p == NULL){ return -1; } p->prior->next = p->next; p->next->prior = p-prior; free(p); p=NULL; return 0; }文件三：
test.c用户输入按位删除双向链表#include"dlist.h" int main(){ dlistnode *H; int pos; H=dlist_create(); dlist_show(H); while(1){ puts("input pos"); scanf("%d",&pos); dlist_delete(H,pos); dlist_show(H); } return 0; }
-----------------------------------------很棒学习完了数据结构的 双向循环链表--------------------------------------------------
--------------------------------------------------------[下期预告：线性表的应用举例]------------------------------------------------------
-
-
循环双链表详解（C语言版）
2020-10-22 17:35:55可以实现从表中任一结点出发找到链表中的其他结点，但是该结构如果要从头结点开始查找尾结点，那么就需要通过遍历查找尾结点，这种情况下双链表的效率较低，为了解决这个缺点，将其改进为循环双链表，以此来提高查找...展开全文
前言
之前学习的双链表结构，可以实现从表中任一结点出发找到链表中的其他结点，但是该结构如果要从头结点开始查找尾结点，那么就需要通过遍历查找尾结点，这种情况下双链表的效率较低，为了解决这个缺点，将其改进为循环双链表，以此来提高查找效率。
一、循环双链表的定义
循环双链表是对双链表的改进，将尾结点与头结点建立连接，使得尾结点可以直接查找到头结点，头结点也能够直接查找到头结点，以此来提高查找的效率。
二、循环双链表的结构
结构图
代码描述#define ElemType int //循环双链表结点结构 typedef struct Node { ElemType data; //数据域 struct Node *prio; //前驱结点指针域 struct Node *next; //后继结点指针域 }Node, *PNode; //双链表结点管理结构 typedef struct List { PNode first; //指向首结点（首结点不存放数据） PNode last; //指向尾结点 int size; //记录有效结点数 }List;三、循环双链表的常用操作
初始化循环双联链表
//初始化双链表 void InitDCList(List *list) { //申请头结点空间 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //将头结点连接入管理结点 list->first = list->last = s; //设置前驱指针指向（指向头结点） list->first->prio = list->last; //设置后继结点指向（指向尾结点） list->last->next = list->first; list->size = 0; }获取结点
//获取结点 Node* _buynode(ElemType x) { Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = s->prio = NULL; return s; }尾插
void push_back(List *list, ElemType x) { //获取结点 Node *s = _buynode(x); //将插入结点与头结点连接 s->next = list->last->next; s->next->prio = s; //将插入结点与上一尾结点连接 s->prio = list->last; list->last->next = s; //修改双向链表管理结点的尾指针 list->last = s; list->size++; }头插
//头插 void push_front(List *list, ElemType x) { //获取插入结点 Node *s = _buynode(x); //连接新插入结点和其下一个结点 s->next = list->first->next; s->next->prio = s; //插入结点和头结点 s->prio = list->first; list->first->next = s; //如果这个结点是第一个有效结点，需要更改管理结点尾指针的指向 if(list->first == list->last) list->last = s; list->size++; }查看循环双链表数据
//查看循环双链表数据 void show_list(List *list) { //指向第一个有效结点 Node *p = list->first->next; //将所有有效结点输出 while(p != list->first) { printf("%d-->",p->data); p = p->next; } printf("Nul.\n"); }尾删
//尾删 void pop_back(List *list) { //如果没有有效结点，那么不进行删除 if(list->size == 0) return; //设置管理结点的尾部指针指向 Node *p = list->last; list->last = list->last->prio; //删除结点 p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; }头删
//头删 void pop_front(List *list) { //如果没有有效结点不进行删除 if(list->size == 0) return; //删除结点 Node *p = list->first->next; p->next->prio = p->prio; p->prio->next = p->next; //如果只有一个有效结点，需要更改管理结点尾指针指向 if(list->size == 1) list->last = list->first; list->size--; }按值插入(由小到大的顺序)
//按值插入(由小到大的顺序) void insert_val(List *list, ElemType x) { Node *p = list->first;//先指向头结点 //查找要插入结点的位置 while(p->next!=list->last && p->next->data < x) p = p->next; //如果插入的位置在最后，则进行尾插 if(p->next==list->last && p->next->data<x) { push_back(list,x); } else //普通插入 { Node *s = _buynode(x); s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; list->size++; } }查找某一个值所在的位置
//查找某一个值所在的位置 Node* find(List *list, ElemType key) { //从第一个有效结点位置开始查找 Node *p = list->first->next; while(p != list->first && p->data != key) p = p->next; //如果没有找到返回空 if(p == list->first) return NULL; return p; }获取有效结点个数
//获取有效结点个数 int length(List *list) { return list->size; }按值删除
//按值删除 void delete_val(List *list, ElemType key) { //如果没有有效结点，则无需删除 if(list->size == 0) return; //查找要删除结点所在的位置 Node *p = find(list,key); //如果没有找到，无需删除 if(p == NULL) { printf("要删除的数据不存在.\n"); return; } //如果这个结点是尾结点，则进行尾删 if(p == list->last) { pop_back(list); } else//否则进行普通删除 { p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; } }排序(按照由小到大排序)
//排序(按照由小到大排序) void sort(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *s = list->first->next; Node *q = s->next; list->last->next = NULL; list->last = s; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素按值插入(由小到大)到第一条循环链表中 while(q != NULL) { //拿取元素 s = q; q = q->next; //按值插入（由小到大） Node *p = list->first;//查找插入位置 while(p->next!=list->last && p->next->data < s->data) p = p->next; if(p->next==list->last && p->next->data<s->data) {//尾插 s->next = list->last->next; s->next->prio = s; s->prio = list->last; list->last->next = s; list->last = s; } else {//普通插入 s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; } } }逆置
//逆置 void resver(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *p = list->first->next; Node *q = p->next; list->last->next = NULL; list->last = p; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素头插到第一条循环链表中 while(q != NULL) { //获取元素 p = q; q = q->next; //头插 p->next = list->first->next; p->next->prio = p; p->prio = list->first; list->first->next = p; } }清空有效结点
//清空有效结点 void clear(List *list) { //如果没有结点 if(list->size == 0) return; //从第一个有效结点开始 Node *p = list->first->next; while(p != list->first) { //清空释放有效结点（头删） p->next->prio = list->first; list->first->next = p->next; free(p); p = list->first->next; } list->last = list->first; list->size = 0; }销毁循环双链表
//销毁循环双链表 void destroy(List *list) { //清空释放所有有效结点 clear(list); free(list->first); //清空管理结点 list->first = list->last = NULL; }结语
对循环双链表的介绍就到这里，希望这篇文章能够给予你一些帮助。
附录
以下提供循环双链表的测试代码
DCList.h
#ifndef __DCLIST_H__ #define __DCLIST_H__ #include<stdio.h> #include<malloc.h> #include<assert.h> #define ElemType int //循环双链表结点结构 typedef struct Node { ElemType data; //数据域 struct Node *prio; //前驱结点指针域 struct Node *next; //后继结点指针域 }Node, *PNode; //双链表结点管理结构 typedef struct List { PNode first; //指向首结点（首结点不存放数据） PNode last; //指向尾结点 int size; //记录有效结点数 }List; Node* _buynode(ElemType x); void InitDCList(List *list); void push_back(List *list, ElemType x); void push_front(List *list, ElemType x); void show_list(List *list); void pop_back(List *list); void pop_front(List *list); void insert_val(List *list, ElemType x); Node* find(List *list, ElemType key); int length(List *list); void delete_val(List *list, ElemType key); void sort(List *list); void resver(List *list); void clear(List *list); void destroy(List *list); #endif //__DCLIST_H__DCList.cpp
#include"DCList.h" //获取结点 Node* _buynode(ElemType x) { Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = s->prio = NULL; return s; } //初始化双链表 void InitDCList(List *list) { //申请头结点空间 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //将头结点连接入管理结点 list->first = list->last = s; //设置前驱指针指向（指向头结点） list->first->prio = list->last; //设置后继结点指向（指向尾结点） list->last->next = list->first; list->size = 0; } //尾插 void push_back(List *list, ElemType x) { //获取结点 Node *s = _buynode(x); //将插入结点与头结点连接 s->next = list->last->next; s->next->prio = s; //将插入结点与上一尾结点连接 s->prio = list->last; list->last->next = s; //修改双向链表管理结点的尾指针 list->last = s; list->size++; } //头插 void push_front(List *list, ElemType x) { //获取插入结点 Node *s = _buynode(x); //连接新插入结点和其下一个结点 s->next = list->first->next; s->next->prio = s; //插入结点和头结点 s->prio = list->first; list->first->next = s; //如果这个结点是第一个有效结点，需要更改管理结点尾指针的指向 if(list->first == list->last) list->last = s; list->size++; } //查看循环双链表数据 void show_list(List *list) { //指向第一个有效结点 Node *p = list->first->next; //将所有有效结点输出 while(p != list->first) { printf("%d-->",p->data); p = p->next; } printf("Nul.\n"); } //尾删 void pop_back(List *list) { //如果没有有效结点，那么不进行删除 if(list->size == 0) return; //设置管理结点的尾部指针指向 Node *p = list->last; list->last = list->last->prio; //删除结点 p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; } //头删 void pop_front(List *list) { //如果没有有效结点不进行删除 if(list->size == 0) return; //删除结点 Node *p = list->first->next; p->next->prio = p->prio; p->prio->next = p->next; //如果只有一个有效结点，需要更改管理结点尾指针指向 if(list->size == 1) list->last = list->first; list->size--; } //按值插入(由小到大的顺序) void insert_val(List *list, ElemType x) { Node *p = list->first;//先指向头结点 //查找要插入结点的位置 while(p->next!=list->last && p->next->data < x) p = p->next; //如果插入的位置在最后，则进行尾插 if(p->next==list->last && p->next->data<x) { push_back(list,x); } else //普通插入 { Node *s = _buynode(x); s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; list->size++; } } //查找某一个值所在的位置 Node* find(List *list, ElemType key) { //从第一个有效结点位置开始查找 Node *p = list->first->next; while(p != list->first && p->data != key) p = p->next; //如果没有找到返回空 if(p == list->first) return NULL; return p; } //获取有效结点个数 int length(List *list) { return list->size; } //按值删除 void delete_val(List *list, ElemType key) { //如果没有有效结点，则无需删除 if(list->size == 0) return; //查找要删除结点所在的位置 Node *p = find(list,key); //如果没有找到，无需删除 if(p == NULL) { printf("要删除的数据不存在.\n"); return; } //如果这个结点是尾结点，则进行尾删 if(p == list->last) { pop_back(list); } else//否则进行普通删除 { p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; } } //排序(按照由小到大排序) void sort(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *s = list->first->next; Node *q = s->next; list->last->next = NULL; list->last = s; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素按值插入(由小到大)到第一条循环链表中 while(q != NULL) { //拿取元素 s = q; q = q->next; //按值插入（由小到大） Node *p = list->first;//查找插入位置 while(p->next!=list->last && p->next->data < s->data) p = p->next; if(p->next==list->last && p->next->data<s->data) {//尾插 s->next = list->last->next; s->next->prio = s; s->prio = list->last; list->last->next = s; list->last = s; } else {//普通插入 s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; } } } //逆置 void resver(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *p = list->first->next; Node *q = p->next; list->last->next = NULL; list->last = p; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素头插到第一条循环链表中 while(q != NULL) { //获取元素 p = q; q = q->next; //头插 p->next = list->first->next; p->next->prio = p; p->prio = list->first; list->first->next = p; } } //清空有效结点 void clear(List *list) { //如果没有结点 if(list->size == 0) return; //从第一个有效结点开始 Node *p = list->first->next; while(p != list->first) { //清空释放有效结点（头删） p->next->prio = list->first; list->first->next = p->next; free(p); p = list->first->next; } list->last = list->first; list->size = 0; } //销毁循环双链表 void destroy(List *list) { //清空释放所有有效结点 clear(list); free(list->first); //清空管理结点 list->first = list->last = NULL; }Main.cpp
#include"DCList.h" void main() { List mylist; InitDCList(&mylist); ElemType Item; Node *p = NULL; int select = 1; while(select) { printf("**************************************\n"); printf("* [1] push_back [2] push_front *\n"); printf("* [3] show_list [4] pop_back *\n"); printf("* [5] pop_front [6] insert_val *\n"); printf("* [7] find [8] length *\n"); printf("* [9] delete_val [10] sort *\n"); printf("* [11] resver [12] clear *\n"); printf("* [13*] destroy [0] quit_system *\n"); printf("**************************************\n"); printf("请选择:>"); scanf("%d",&select); if(select == 0) break; switch(select) { case 1: printf("请输入要插入的数据(-1结束):>"); while(scanf("%d",&Item),Item != -1) { push_back(&mylist,Item); } break; case 2: printf("请输入要插入的数据(-1结束):>"); while(scanf("%d",&Item),Item != -1) { push_front(&mylist,Item); } break; case 3: show_list(&mylist); break; case 4: pop_back(&mylist); break; case 5: pop_front(&mylist); break; case 6: printf("请输入要插入的数据:>"); scanf("%d",&Item); insert_val(&mylist,Item); break; case 7: printf("请输入要查找的数据:>"); scanf("%d",&Item); p = find(&mylist,Item); if(p == NULL) { printf("要查找的数据在链表中不存在.\n"); } break; case 8: printf("双向循环链表的长度为:> %d \n",length(&mylist)); break; case 9: printf("请输入要删除的值:>"); scanf("%d",&Item); delete_val(&mylist,Item); break; case 10: sort(&mylist); break; case 11: resver(&mylist); break; case 12: clear(&mylist); break; //case 13: // destroy(&mylist); // break; default: printf("输入的命令错误,请重新输入.\n"); break; } } destroy(&mylist); }
-
双向链表和循环链表的区别
2020-11-14 11:01:032、双向链表在访问元素时，可以从任何结点开始任意向前向后双向访问节点元素，不像循环单链表只能按顺序访问后节点。 3、因为有前后两个指针，双向链表删除前驱和后驱节点，以及插入节点的操作非常便捷。 循环链表... -
Linux内核中的通用双向循环链表
2021-01-09 15:42:19作为众多基础数据结构中的一员，双向循环链表在各种“教科书”中的实现是相当的标准和一致的。 大概是下面这个样子： 1 typedef struct node_tag{ 2 //T data; 3 struct node_tag *prev; 4 ... -
双向循环链表源码
2018-02-01 10:16:34本人自己编写的双向循环链表源码,分享给大家,存在什么问题请指出 -
改造一个双向循环链表，使右链域保持原来的顺序，而左链域从小到大顺序排列。
2021-01-03 21:44:14本题在之前发布过，但发现方法略有复杂。本次将更新一下最简单的思想方法 。点击查看原题出处 思想： 改进：不需要对每个结点的左链域进行置空初始化，因为最后还是会重新赋值。只需要对头结点 L 初始化： L->prior...
收藏数
117,035
精华内容
46,814