如果你真的了解我
那请告诉我你已爱上了我
01
线性表的链式存储概念
Law
线性表的链式存储结构称为链表。每个存储结点不仅包含元素本身的信息，而且包含表示元素之间逻辑关系的信息，分别称为数据域和指针域。
链表有很多种不同的类型：单链表、循环链表、双向链表和静态链表。
单链表
1)单链表的定义
当采用链式存储时，一种最简单常用的方法是在每个结点中除包含有数据域以外的只设置一个指针域用于指向其后继结点，这样构成的链表称为线性单向链表，简称单链表。单链表的结点结构如图2.5所示，data为数据域，next为指针域。
若没有特别说明，后面算法中均采用带头结点的单链表，如图2.6所示，在单链表中增加头结点的优点如下：
（1）单链表中首结点的插入和删除操作与其他结点一致，无须进行特殊处理。
（2）无论单链表是否为空都有一个头结点，可以把空表和非空表的处理过程统一。
在单链表中，由于每个结点只包含有一个指向后继结点的指针，所以当访问过一个结点后只能接着访问它的后继结点，而无法访问它的前驱结点，因此在进行单链表结点的插入和删除时就不能简单地只对该结点进行操作，还必须考虑其前后的结点。
2)单链表中基本操作的实现
①建立单链表
这里主要介绍整体建立单链表，由数组a创建单链表L。
心头插法
首先从一个空表开始，创建一个头结点；依次读取字符数组a中的元素，生成新结点；将新结点插入到当前链表的表头上，指导结束为止。如图2.7所示。
②尾插法
首先从一个空表开始，创建一个头结点。依次读取字符数组a中的元素，生成新结点；新结点插入到当前链表的表尾上，直到结束为止。如图2.8所示。
3)单链表基本运算算法
①心初始化单链表lnitList(L)
该运算建立一个空的单链表，即创建一个头结点，如图2.9所示。
②销毁单链表DestroyList(L)
释放单链表L占用的内存空间，时间复杂度为O(n)。
③判单链表是否为空表ListEmpty(L)
若单链表L没有数据结点，则返回真，否则返回假。时间复杂度为0(1)。
④求单链表的长度ListLength(L)
求单链表L中数据结点的个数，时间复杂度为O(n)。
⑤输出单链表DispList(L)
依次访问单链表L的每个数据结点，并显示各结点的data域值。时间复杂度为O(n)。
⑥求单链表L中位置1的数据元素GetElem(L,i,e)在单链表L中从头开始找到第1个结点，若存在第i个数据结点，则将其data域值赋给变量e。时间复杂度为O(n)。
⑦按元素值查找LocateElem(L,e)
在单链表L中从头开始找第1个值域与e相等的结点，若存在这样的结点，则返回位置，否则返回0。
时间复杂度为O(n),算法如下：
双链表
(1)双链表的定义
在单链表中只有一个指示直接后继的指针域，因此，从某个结点出发只能顺着指针往后查找其他结点。若要查找结点的直接前驱，则需要从表头指针出发，所以访问后继结点的时间复杂度为0(1)。
而访问前驱结点的时间复杂度为O(n),为克服单链表这种单向性的缺点，可以使用双向链表，简称双链表。
顾名思义，双链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，结点基本结构如图2.10所示。一个带头结点的双链表如图2.11所示。从任一结点出发可以快速找到其前驱结点和后继结点；从任一结点出发可以访间其他结点。
(2)双链表中基本操作的实现
1）建立双链表
这里主要介绍整体建立双链表，由数组a创建双链表L。
①头插法
②尾插法
2)双链表基本运算算法
双链表中的有些运算如求长度，取元素值和查找元素等算法与单链表中的相应算法是相同的，但双链表中插入和删除结点与单链表有很大区别，下面分别介绍双链表中的插入和删除操作。
①插入操作
假设在p所指结点之后插入一个结点s,具体过程如图2.12所示。
②删除操作
假设删除p所指结点之后的结点s,具体过程如图2.13所示。
循环链表
(1)单循环链表
单循环链表与链表的区别在于它的尾结点的next域指向头结点，使整个单链表形成一个环，因此从表中任一结点出发，都可以找到链表中的其他结点，如图2.14所示。
有时在单循环链表中不设头指针仅设尾指针。因为若只有头指针，则对表尾操作需要O(n)的时间复杂度。而设置尾指针后，可以通过r-next转化为头指针，对表头和表尾操作都仅需要0。
(1)的时间复杂度。
单循环链表在实现约瑟夫问题等一些算法设计中不需要头结点（一些数据结构考研程序设计题目中有涉及），希望引起考生的注意。
(2)双循环链表
双循环链表与双链表区别在于它的尾结点的next域指向头结点，而它的头结点的prior域指向尾结点，使整个双链表形成两个环，因此从表中任一结点出发，都可以找到链表中的其他结点，如图2.15所示。
静态链表
静态链表是利用一维数组描述线性链表，它和指针型描述的线性链表有所不同。
02
顺序表与链表的区别
Law
(1)顺序表中的元素，如果逻辑上相邻则存储位置也相邻，所以当进行插入或删除操作时需要平均移动一半的元素，效率较低。而链表中的元素，如果逻辑上相邻则对应的存储位置不一定相邻，它们是通过指针来链接的，因而每个结点的存储位置可以任意安排，不必要求相邻，所以当进行插入或删除操作时，只需要修改相关结点的指针域即可，效率较高。
(2)顺序表是线性表的直接映射，所以具有随机存取特性，即查找第1个元素时，需要的时间复杂度为0(1),而链表则不具有随机存取特性，相应地查找第i个元素所需要的平均时间复杂度O(n)。
(3)顺序表的存储密度比较高。所谓存储密度是指结点中数据元素本身所占的存储量和整个结点占用的存储量之比，相应的公式如下。
存储密度越大，存储空间的利用率也就越高。所以，顺序表的存储密度为1,而链表的存储密度小于1。
预览时标签不可点收录于话题#个上一篇下一篇