第 七 讲 单链表、循环链表、双向链表 10 23

数据结构中linklist的理解LinkList（链表）的理解。

在数据结构中，链表（LinkList）是一种基本的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表是一种线性数据结构，它可以用来表示一系列元素的顺序。

与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针相互连接起来的。

这种特性使得链表具有一些独特的优势和应用场景。

链表的基本结构。

链表由节点组成，每个节点包含两部分，数据和指针。

数据部分用来存储元素的值，指针部分用来指向下一个节点。

链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针指向空值（NULL）。

链表的分类。

链表可以分为单向链表、双向链表和循环链表三种基本类型。

单向链表，每个节点只包含一个指针，指向下一个节点。

双向链表，每个节点包含两个指针，分别指向前一个节点和后一个节点。

循环链表，尾节点的指针指向头节点，形成一个闭环。

不同类型的链表适用于不同的场景，选择合适的链表类型可以提高数据操作的效率。

链表的优势。

链表相对于数组有一些明显的优势：插入和删除操作高效，由于链表中的元素不是连续存储的，插入和删除操作可以在常数时间内完成，而数组中的插入和删除操作需要移动大量元素，时间复杂度为O(n)。

动态扩展，链表的大小可以动态调整，不需要预先分配固定大小的内存空间。

链表的应用场景。

由于链表的优势，它在一些特定的应用场景中得到了广泛的应用：LRU缓存，链表可以用来实现LRU（Least Recently Used）缓存淘汰算法，当缓存空间不足时，链表可以高效地删除最久未使用的元素。

大整数运算，链表可以用来表示大整数，实现大整数的加减乘除运算。

图论算法，在图论算法中，链表常常用来表示图的邻接表，用于表示图中的顶点和边的关系。

链表的实现。

链表的实现可以使用指针或者引用来表示节点之间的关系。

在C语言中，可以使用指针来表示节点之间的连接关系；在Java等语言中，可以使用引用来表示节点之间的连接关系。

数据结构》课程教案课程类别：专业基础课适用专业：计算机应用技术授课学时：32学时课程学分：4学分一、课程性质、任务课程性质：《数据结构》是计算机应用技术专业的必修课程，也是研究如何对数据进行组织和设计、如何编制高效率的处理程序的一门基础学科。

课程任务：1、学习计算机程序编写中的数据组织和设计；2、数据的物理结构和逻辑结构；3、经典算法的设计和算法效率的分析。

二、课程培养目标：（一）知识目标通过理论学习和程序的编写，使学生系统地掌握程序中数据的组织、数据的物理结构和逻辑结构，在重要算法的实现上逐步提高编程能力。

（二）技能目标通过课程的学习，让学生掌握重要的数据结构，对数据的逻辑结构和物理结构有深入的理解，同时能编写出使用重要算法知识的程序，并运用所学知识编写程序解决实际中的问题。

（三）素质目标通过课程的学习，让学习学会自学，培养学生的自学能力、克服学习困难的能力，同时让学生掌握计算机编程中数据结构的学习方法，并养成严谨、认真、仔细、踏实、上进的好习惯。

三、选用教材与参考资料教材版本信息《数据结构与算法简明教程（Java语言版）》清华大学出版社叶小平陈瑛主编教材使用评价本教材经过两年的使用，得到了读者一致认可，同时也在不断改进，适合高职高专教学使用，内容基础、重难点突出，符合高职高专“理论够用、注重实践”的要求。

选用的参考资料严蔚敏•吴伟民《数据结构（C语言版）》•清华大学出版社.2009年版殷人昆.《数据结构》•清华大学出版社.1999年版《C语言程序设计》•石油大学出版社《C语言程序设计》•中国石油大学出版社.2006年版四、本课程与其他课程的联系与分工先修课程《离散数学》、《程序设计基础》后续课程《面向对象技术》、《操作系统》与其他课程配合与取舍情况《数据结构》与《离散数学》知识点结合较多，《离散数学》讲求逻辑思维能力的培养和训练，《数据结构》中逻辑结构的学习也需要逻辑思维能力做铺垫。

同时《程序设计基础》课程也为学习《数据结构》打下了基础，对于本课程的教材，我们采用C语言来描述数据结构，因此程序设计基础也是以C语言作为的对象。

单链表、双链表、循环链表和静态链表的习题一、单项选择题1.关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（）。

Ⅰ.线性表的顺序存储结构优于其链式存储结构Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构Ⅲ.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构Ⅳ.顺序存储结构和链式存储结构都可以进行顺序存取A. Ⅰ、Ⅱ、ⅢB. Ⅱ、ⅣC. Ⅱ、ⅢD. Ⅲ、Ⅳ2.对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（）。

A.顺序存储方式B.链式存储方式C.散列存储方式D.以上均可以3.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应该是（）。

A.将n个元素从小到大排序B.删除第i个元素（1<i<n）C.改变第i个元素的值（1<=i<=n）D.在第i个元素后插入一个新元素（1<=i<=n）4.下列关于线性表说法正确的是（）。

Ⅰ.顺序存储方式只能用于存储线性结构Ⅱ.取线性表的第i个元素的时间同i的大小有关Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n) Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表A. Ⅰ、ⅡB.Ⅰ、Ⅲ、Ⅳ、ⅤC. Ⅳ、ⅤD. Ⅲ、Ⅳ、Ⅴ5.设线性表中有2n个元素，（）在单链表上实现要比在顺序表上实现效率更高。

A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-l个元素的值(i=0,…, n-1)6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（）。

A .s->next=p->next;p->next=s; B.p->next=s->next; s->next=p;C. q->next=s;s->next=p;D. p->next=s;s->next=q;7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（）。

循环双链表特点循环双链表是一种特殊的数据结构，它具有循环和双向链表的特点。

循环双链表中的每个节点都包含两个指针，一个指向前一个节点，一个指向后一个节点。

最后一个节点的后指针指向头节点，头节点的前指针指向最后一个节点，从而形成了一个闭环。

循环双链表的特点如下：1. 双向性：每个节点都有两个指针，分别指向前一个节点和后一个节点。

这样可以方便地在任意位置插入或删除节点，而不需要像单链表那样需要遍历找到前驱节点。

2. 循环性：循环双链表是一个闭环，即最后一个节点的后指针指向头节点，头节点的前指针指向最后一个节点。

这样可以方便地进行循环遍历，不需要判断是否到达了链表的末尾。

3. 动态性：循环双链表可以动态地增加或删除节点，而不需要预先指定链表的长度。

4. 灵活性：循环双链表可以在任意位置插入或删除节点，不受限于只能在链表的头部或尾部进行操作。

这样可以方便地实现栈、队列等数据结构。

5. 代码实现简单：相比于其他数据结构，循环双链表的代码实现相对简单，只需要处理好节点之间的指针关系即可。

循环双链表的应用领域非常广泛，特别是在需要频繁插入和删除节点的场景中，循环双链表能够提供高效的插入和删除操作。

下面以几个具体的应用场景来展开对循环双链表的解释和扩展。

1. 缓存替换算法：循环双链表可以用于实现LRU（Least Recently Used）缓存替换算法。

LRU算法中，当缓存满时，需要替换掉最近最少使用的数据。

循环双链表可以维护数据的访问顺序，每次访问一个数据时，将其移到链表的头部；当缓存满时，删除链表尾部的数据即可。

这样就可以保证链表头部的数据是最近访问的数据，尾部的数据是最久未访问的数据。

2. 轮播图：循环双链表可以用于实现轮播图功能。

轮播图需要循环展示多张图片，循环双链表正好可以满足这个需求。

每个节点表示一张图片，节点之间通过指针连接起来形成一个循环链表。

通过不断地遍历链表，可以实现图片的自动切换。

3. 约瑟夫环问题：循环双链表可以用于解决约瑟夫环问题。

循环单链表循环单链表是一种特殊的单链表，它的最后一个节点的指针指向第一个节点，形成一个环。

它具有单链表独有的优点，同时又克服了单链表存在的缺点。

因此，循环单链表在实际应用中受到了极大的欢迎。

本文介绍了循环单链表的概念，结构特性和实现功能，并分析了其与普通单链表的区别。

1.环单链表的概念循环单链表，也叫循环链表，是一种特殊的单链表，它的最后一个节点的指针指向第一个节点，形成一个环。

循环链表的结构比普通的单链表略有不同，其头结点的next域指向头节点，该结构最显著的特点就是头节点的“上一个”节点和最后一个节点“下一个”节点都是头结点，所以可以利用循环链表来实现双向链表的操作。

2.环单链表的结构特性循环单链表是一种特殊的单链表，其最后一个节点指针指向头结点，从结构上来看，它具有单链表的特点，如指针存储结构、节点为一个结构体成员以及只有单向指针，但又与普通单链表不同，它的结构特征有：（1）头结点的next域指向自身；（2）最后一个节点的next域也指向头结点；（3）整个结构类似一个拥有多叉指针的环形结构体。

3.环单链表的实现功能循环单链表的实现功能包括插入、删除、查找等，这些基本操作的实现和普通单链表的实现方法基本相同，只是有一些细节的不同。

例如，在普通单链表的删除操作中，如果需要删除的节点是链表的最后一个节点，则需要修改链表的尾指针，但是在循环单链表中，只需要修改头结点的next域指向，就可以实现操作。

4.与普通单链表的区别循环单链表有一些独特的结构特点，同时又克服了普通单链表的缺点，因此在实际应用中受到了极大的欢迎。

（1）普通单链表无法实现双向遍历，而循环单链表可以实现双向遍历和遍历，因为它有头结点和最后一个节点，所以可以实现双向遍历，再加上其结构特点，可以实现对双向链表的操作。

（2）普通单链表遍历需要维护一个辅助指针，而循环单链表则不需要，只需要从头结点开始，依次访问每一个节点，直到头结点。

结论：循环单链表是一种特殊的单链表，它的结构特征是头结点的next域指向头结点，最后一个节点的next域也指向头结点，它克服了普通单链表的缺点，可以实现双向遍历，同时又不需要维护辅助指针，因此广泛应用在实际工程中。

第8讲 双向链表● 循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前趋结点，但时间耗费是O (n) 。

● 如果希望从表中快速确定某一个结点的前趋，另一个解决方法就是在单链表的每个结点里再增加一个指向其前趋的指针域prior 。

这样形成的链表中就有两条方向不同的链，我们称之为双向链表。

● 双向链表的结构定义如下：typedef struct DNode{ ElemType data ；struct DNode *prior ，*next ；}DNode, * DoubleList ；● 双向链表的结点结构如图所示。

图：双链表的结点结构注：● 双向链表也是由头指针唯一确定的，● 增加头结点能使双链表的某些运算变得方便● 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。

● 设指针p 指向双链表中某一结点，则有下式成立：p->prior->next = p = p->next->prior●在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，● 但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。

1、 双向链表的前插操作【算法思想】欲在双向链表第i 个结点之前插入一个的新的结点，则指针的变化情况如图所示：… p …s->prior=p->prior; ①p->prior->next=s;②s->next=p; ③p->prior=s;④【算法描述】int DlinkIns(DoubleList L,int i,ElemType e){DNode *s,*p;… /*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/… /*若位置i合法，则找到第i个结点并让指针p指向它*/s=(DNode*)malloc(sizeof(DNode));if (s){ s->data=e;s->prior=p->prior; ①p->prior->next=s; ②s->next=p; ③p->prior=s; ④r eturn TRUE;}else return FALSE;}2、双向链表的删除操作【算法思想】欲删除双向链表中的第i个结点，则指针的变化情况如图所示：p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);【算法描述】int DlinkDel(DoubleList L,int i,ElemType *e){DNode *p;… /*先检查待插入的位置i 是否合法（实现方法同单链表的删除操作）*/… /*若位置i 合法，则找到第i 个结点并让指针p 指向它*/*e=p->data;p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);return TRUE;}3、 双向循环链表双向链表可以有循环表,称为双向循环链表。

单链表基本操作在计算机科学里，链表是一种常见的数据结构，它可以用来解决各种复杂的问题。

其中，单链表是最常见的一种，它由一系列节点组成，每个节点包含了一个数据元素和一个指针，指向下一个节点。

这篇文章将介绍单链表的基本操作，包括创建、插入、删除和遍历等。

创建单链表创建单链表是基本操作之一，它有两种方法：头插法和尾插法。

头插法是从链表的头节点开始，逐个将新节点插入。

具体来说，创建一个空链表，设置一个头节点，将头节点的指针指向空；依次输入新节点，将新节点的指针指向表头，将表头的指针指向新节点。

这样，每插入一个新节点就成为了新的表头，即最后插入的节点为新的表头。

尾插法则是从链表的尾节点开始，逐个将新节点插入。

具体来说，创建一个空链表，设置一个头节点，将头节点的指针指向空；依次输入新节点，将新节点的指针指向空，将最后一个节点的指针指向新节点。

这样，最后插入的节点为尾节点，它的指针值为空。

插入节点插入节点是指在单链表的任意位置插入一个新节点。

插入节点的前提是找到插入位置，可以通过遍历单链表来查找插入位置。

插入新节点的基本步骤如下：1、创建新节点；2、将新节点的指针指向待插入节点的后继节点；3、将待插入节点的指针指向新节点。

删除节点删除节点是指删除单链表中的任意节点。

删除节点的前提是找到删除的节点位置，可以通过遍历单链表来查找删除位置。

删除节点的基本步骤如下：1、找到要删除的节点；2、将该节点的前驱节点的指针指向该节点的后继节点；3、删除该节点。

遍历节点遍历节点是指按照链表的顺序依次访问链表中的各个节点。

遍历节点的基本步骤如下：1、从链表的头节点开始遍历；2、依次访问每个节点的数据元素；3、通过指针访问下一个节点，直到遇到尾节点。

优缺点单链表的优点是简单，灵活，易于实现和扩展，可以方便地进行插入和删除等操作。

其缺点是存在指针开销，查找元素时需要遍历整个链表，不能直接访问链表中任意位置的节点。

总结单链表是一种最常用的数据结构，它是由一系列节点组成，每个节点包含一个数据元素和一个指针，指向下一个节点。

链表一种数据结构的链接实现是指按链式存储方式构建其存储结构，并在此链式存储结构上实现其基本运算。

线性表的常见链式存储结构有单链表、循环链表和双链表，其中最简单的单链表。

本节讨论单链表的组织方法以及线性表的基本运算在单链表上的实现。

单链表示法的基本思想是用指针表示结点间的逻辑关系。

因此单链表的一个存储结点包含两个部分，结点形式如下：其中，data部分称为数据域，用于存储线性表的一个数据元素。

next部分称为指针域或链域，用于存放一个指针，该指针指向本结点所含数据元素的直接后继所在的结点。

从上述单链表中可以联想到我们生活中的火车，还有一种火车只有火车头。

假设数据元素的类型为Datatype。

单链表的类型定义如下：typedef struct node{Datatype data;struct node * next;} node，* LinkList;struct node表示链表的结点，一个结点是由两个域数据域data和指针域next组成的记录（每个域实际上相当于一个变量），而next本身又是一个pointer类型的指针型变量。

这个定义与上面给出的单链表的结点形式一致。

单链表的简单操作：1、初始化建立一个空表。

空表由一个头指针和一个头结点（该结点同时也是尾结点）组成。

LinkList Initiate_LinkList()/* 建立一空表 */{ LinkLis head;head= malloc(sizeof(node));head -> next = NULL;return head;}2、定位：按值查找。

按从前往后的顺序，依次比较单链表中各表结点数据域的值与给定值X，第一个值与X相等的表结点的序号就是结果。

若没有这样的结点，运算结果为0。

int Locate_LinkList(LinkList head,Datatype x){ Node *p;p = head; /* 置初值 */p=p->next;j = 0; /* 置初值 */while((p!= NULL)&&(p -> data != x)){ p = p -> next;j ++;} /* 未达尾结点又未找到等于x的结点时继续扫描 */if (p -> data == x)return(j+1);elsereturn(0);}3、插入:把新的结点x插入到i结点之前。

数据结构—链表链表⽬录⼀、概述1.链表是什么链表数⼀种线性数据结构。

它是动态地进⾏储存分配的⼀种结构。

什么是线性结构，什么是⾮线性结构？线性结构是⼀个有序数据元素的集合。

常⽤的线性结构有：线性表，栈，队列，双队列，数组，串。

⾮线性结构，是⼀个结点元素可能有多个直接前趋和多个直接后继。

常见的⾮线性结构有：⼆维数组，多维数组，⼴义表，树(⼆叉树等)。

2.链表的基本结构链表由⼀系列节点组成的集合，节点（Node）由数据域（date）和指针域（next）组成。

date负责储存数据，next储存其直接后续的地址3.链表的分类单链表（特点：连接⽅向都是单向的，对链表的访问要通过顺序读取从头部开始）双链表循环链表单向循环链表双向循环链表4.链表和数组的⽐较数组：优点：查询快（地址是连续的）缺点：1.增删慢，消耗CPU内存链表就是⼀种可以⽤多少空间就申请多少空间，并且提⾼增删速度的线性数据结构，但是它地址不是连续的查询慢。

⼆、单链表[1. 认识单链表](#1. 认识单链表)1. 认识单链表（1）头结点：第0 个节点（虚拟出来的）称为头结点（head），它没有数据，存放着第⼀个节点的⾸地址（2）⾸节点：第⼀个节点称为⾸节点，它存放着第⼀个有效的数据（3）中间节点：⾸节点和接下来的每⼀个节点都是同⼀种结构类型：由数据域（date）和指针域（next）组成数据域（date）存放着实际的数据，如学号（id）、姓名（name）、性别（sex）、年龄（age）、成绩（score）等指针域（next）存放着下⼀个节点的⾸地址（4）尾节点：最后⼀个节点称为尾节点，它存放着最后⼀个有效的数据（5）头指针：指向头结点的指针（6）尾指针：指向尾节点的指针（7）单链表节点的定义public static class Node {//Object类对象可以接收⼀切数据类型解决了数据统⼀问题public Object date; //每个节点的数据Node next; //每个节点指向下⼀结点的连接public Node(Object date) {this.date = date;}}2.引⼈头结点的作⽤1. 概念头结点：虚拟出来的⼀个节点，不保存数据。

数据结构中的双向链表实现和应用场景双向链表是一种常用的数据结构，它在许多实际应用中都发挥着重要的作用。

本文将介绍双向链表的实现原理以及一些常见的应用场景。

一、双向链表的实现原理双向链表由一系列节点组成，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。

相比于单向链表，双向链表可以实现双向遍历，提高了一些操作的效率。

1.1 节点定义双向链表的节点通常由数据域和两个指针域组成，例如：```struct Node {int data; // 节点数据Node* prev; // 前一个节点指针Node* next; // 后一个节点指针};```1.2 插入操作在双向链表中插入一个节点可以分为两种情况：在表头插入和在表尾插入。

在表头插入时，只需修改原来头节点的prev指针为新节点的地址，并将新节点的next指针指向原头节点即可。

在表尾插入时，需要先找到原来的尾节点，然后将尾节点的next指针指向新节点的地址，并将新节点的prev指针指向尾节点的地址。

1.3 删除操作删除操作与插入操作类似，同样分为在表头和表尾删除节点。

在表头删除时，只需将头节点的next指针指向新的头节点，同时将新头节点的prev指针置为空。

在表尾删除时，需要先找到尾节点的前一个节点，然后将该节点的next指针置为空。

1.4 查找操作双向链表支持从前向后和从后向前两种遍历方式。

从前向后遍历时，我们可以利用节点的next指针不断向后遍历得到所有节点。

同样，从后向前遍历时，可以利用节点的prev指针不断向前遍历得到所有节点。

二、双向链表的应用场景双向链表广泛应用于各种软件和系统中，下面列举了一些常见的应用场景。

2.1 浏览器的历史记录在浏览器中，经常需要记录用户浏览过的网页历史记录。

这时可以使用双向链表来实现。

每当用户访问一个新的网页，就在双向链表中插入一个新节点，同时将新节点的next指针指向前一个节点，prev指针指向后一个节点。

数据结构--数组、单链表和双链表介绍以及双向链表数组：数组有上界和下界，数组的元素在上下界内是连续的。

数组的特点是：数据是连续的；随机访问速度快。

数组中稍微复杂⼀点的是多维数组和动态数组。

对于C语⾔⽽⾔，多维数组本质上也是通过⼀维数组实现的。

⾄于动态数组，是指数组的容量能动态增长的数组；对于C语⾔⽽⾔，若要提供动态数组，需要⼿动实现；⽽对于C++⽽⾔，STL提供了Vector。

单向链表：单向链表(单链表)是链表的⼀种，它由节点组成，每个节点都包含下⼀个节点的指针。

表头为空，表头的后继节点是"节点10"(数据为10的节点)，"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的后继节点是"节点30"(数据为20的节点)，"节点30"的后继节点是"节点40"(数据为10的节点)，......删除"节点30"删除之前："节点20" 的后继节点为"节点30"，⽽"节点30" 的后继节点为"节点40"。

删除之后："节点20" 的后继节点为"节点40"。

在"节点10"与"节点20"之间添加"节点15"添加之前："节点10" 的后继节点为"节点20"。

添加之后："节点10" 的后继节点为"节点15"，⽽"节点15" 的后继节点为"节点20"。

单链表的特点是：节点的链接⽅向是单向的；相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很⾼。