数据结构复习笔记2——线性表
线性表
线性表的定义
线性表示具有相同数据类型的n个数据元素的有限序列(按照这个定义,python中的列表不属于线性表),其中n为表长。当n = 0时,线性表为空表。是一个逻辑结构。
线性表的逻辑特性为:
- 唯一的第一个元素称为表头元素
- 唯一的最后一个元素称为表尾元素
- 除最后一个元素外,每个元素只有唯一一个直接后继;除第一个元素外,每个元素只有唯一一个直接前驱
线性表的特点为:
- 表中的元素个数有限(实际上,单链表不受这个限制,可以无限增长,只要内存足够)
- 表中元素具有逻辑上的顺序性,表中元素有其先后次序
- 表中元素都是数据元素,每个元素都是单个元素
- 表中元素的数据类型都相同,这意味着每个元素占有相同大小的存储空间
常见的线性表实现(存储结构):
- 顺序表:基于数组
- 单链表:基于指针
线性表的操作
-
初始化:
- 最大长度
- 当前长度
- 存储结构(数组or链表结点)
-
求表长:
- 返回当前长度
-
按值查找:
- 根据值返回元素的下标
-
按位查找:
- 根据下标返回元素的值
-
插入操作:
- 在指定位置插入元素
-
删除操作:
- 指定位置删除元素
-
输出操作:
- 顺序输出所有元素的值
-
判空操作:
- 线性表是否为空
-
销毁操作:
- 销毁线性表,释放内存(Java中不需要,JVM会自动GC)
-
清空操作:
- 让线性表置空,保留其数据结构
顺序表的实现
顺序表,顾名思义,就是顺序存储结构实现的线性表。按照顺序存储的定义,它的所有数据元素物理存放顺序和逻辑顺序一致。
顺序表的好处也就是顺序存储的好处:
- 随机存取,读取和修改元素方便,O(1)
- 存储密度高,每个结点只存放数据元素(单链表还需要存放指针)
顺序表的缺点:
- 存在外部碎片,空间利用率低
- 插入和删除元素需要移动大量元素(但是,实际上进行表尾的插入删除操作,顺序表优于链表)
所以,我们可以知道:顺序表适用于存取频繁而修改较少的场景,也就是数据静态的场景
单链表的实现
顺序表虽然可以随机存取,访问较快,但在中间插入和删除元素需要移动大量的数据元素。为此,我们使用链式存储结构的单链表实现线性表,它不要求逻辑上相邻的元素在物理位置上相邻,通过指针指示元素的逻辑关系,插入和删除操作只需要移动指针即可。
顺序表对于内存的要求较高,需要连续的内存空间,存在外部碎片的现象。而链表虽然不存在外部碎片,但也会浪费存储空间来存放指针域。
单链表结点的定义
首先,定义一个单链表结点,一个单链表结点由数据域和指针域两部分构成:
单链表的头结点
单链表通常以两种形式来标识:
- 直接使用头指针指向第一个数据元素的链表结点
- 创建一个没有数据域的(伪)头结点,让头指针指向该头结点,该头结点的后继指针指向第一个数据元素的链表结点。
使用头结点的好处有:
- 不用区分链表首部的操作和表中其他位置的操作。
- 对于空表和非空表一样处理。
单链表按序号查找结点
从第一个结点出发,顺序搜索,时间复杂度O(n)。
单链表按结点值查找序号
从第一个结点出发,如果当前结点值与目标值相等,则返回当前结点序号。如果不存在目标值的结点,返回-1。
单链表插入
单链表的插入结点到第 i 个位置需要分为两步:
- 先顺序遍历,定位到第 i - 1个结点(O(n))
- 再在第 i - 1 个结点处进行后插操作(O(1))
单链表删除
与单链表的插入类似,单链表的删除也是先定位到前驱结点,再执行删除操作。
双链表的实现
单链表结点的指针域指向后继,导致单链表只能从头结点开始向后访问,如果要访问某个结点的前驱,需要从头开始查找。
为了克服该缺陷,我们引入了双链表,双链表结点的指针域中有两个指针,prior指向双链表结点的前驱结点,而next指针指向后继结点。
双链表的插入删除操作
双链表与单链表实现几乎一致,最大的区别在于插入删除操作的不同。双链表需要额外修改prior指针。
循环单链表
循环单链表与单链表的区别在于:尾结点的后继指针不为空,而是指向头结点。
这样做的好处是:循环单链表可以从任意一个结点开始遍历整个链表,而普通单链表只能从头结点开始。
循环单链表的判空操作
由于循环单链表的尾结点next指针不为空,所以无法通过头结点的next指针为空判断是空表。取而代之的方法是判断头结点的后继是否为自身。
循环单链表的求长度操作
我们知道,循环单链表可以从任意结点遍历整个链表,遍历的终点为当前结点的前一个结点。
循环单链表的优化
为了进一步优化循环单链表,我们发现,如果设置head指针,那么对于尾结点的操作需要O(n)的时间复杂度,如果设置tail指针,那么对头结点的操作仅需O(1)的时间复杂度,因为单链表只存在后继指针而不存在前驱指针。
所以,如果对循环单链表的表首、表尾操作频繁,则设置尾指针比头指针更好。
循环双链表
循环双链表与循环单链表几乎类似,区别在于它的头结点的prior指针需要指向尾结点。
静态链表
静态链表是使用数组(顺序存储)来模拟链式存储结构的一种数据结构。它本质上属于顺序表,但它的元素之间逻辑关系是使用指针域体现的,所以插入和删除不需要移动元素。需要提前分配较大的连续空间。主要用于在不支持指针的语言中模拟链式存储。
静态链表结合了顺序表和链表的优点,既可以随机存取,又可以避免在插入和删除的时候,移动大量的数据元素。
顺序表和链表的比较
-
存取方式:
- 顺序表可以顺序存取,也可以随机存取
- 链表只能顺序存取
-
逻辑结构和物理结构:
- 顺序表逻辑上相邻的元素物理上一定相邻,元素之间的逻辑关系通过位置关系体现。
- 链表逻辑上相邻的元素物理上不一定相邻,元素之间的逻辑关系通过指针链接体现。
-
查找、插入和删除元素:
- 查找:二者都无序,均需要O(n)的查找时间,如果有序,顺序表可以进行二分查找,仅需要的查找时间。
- 插入、删除:顺序表插入和删除需要移动大量元素,平均O(n)。而链表不考虑定位,只需要修改指针即可,O(1),考虑定位虽然也需要O(n),但大都是比较操作而非赋值操作,更快。
-
空间分配:
- 顺序表必须分配连续的存储空间,存在外部碎片现象。如果预先分配存储空间,当分配空间过小时,会出现内存溢出现象,分配空间过大,会导致浪费。如果使用malloc动态分配空间,扩充时需要移动大量元素,效率很低。并且当内存空间不足时,会导致扩充失败。
- 链表不需要分配连续的空间,不存在外部碎片现象,只要内存有空间就可以分配,灵活高效。但需要存储指针,造成了空间的浪费,数据存储密度较低。
顺序表和链表的选择
-
基于存储的考虑:
- 如果线性表的长度和规模难以估计,优先使用链表。但链表的存储密度比较低,必然小于1,因为需要存放指针。
-
基于运算的考虑:
- 如果经常需要按序号对元素进行存取,优先使用顺序表。(静态的数据)
- 如果经常需要对元素进行插入和删除,优先使用链表。(动态的数据)
-
基于环境的考虑:
- 大多数语言都有数组,但一些语言没有指针,所以无法实现链表。
参考资料:
1、https://hillzhang1999.gitee.io/2020/05/29/shu-ju-jie-gou-fu-xi/#toc-heading-38