文章目录
- 6.对比:顺序表&链表
- 6.1逻辑结构
- 6.2物理结构(存储结构)
- 6.2.1顺序表
- 6.2.2链表
- 6.3数据运算(基本操作)
- 6.3.1初始化
- 6.3.2销毁表
- 6.3.3插入、删除
- 6.3.4查找
6.对比:顺序表&链表
6.1逻辑结构
顺序表和链表都是线性结构。
6.2物理结构(存储结构)
6.2.1顺序表
顺序存储
优点:
- 使用顺序存储,每个数据元素大小相同,所以可以随机访问,即可以在O(1)时间内找到第i个元素。
- 存储密度高,每个节点只存储数据元素。
缺点:
- 拓展容量不方便,使用大片连续的空间,即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高。
- 插入、删除操作不方便,需要移动大量元素。
6.2.2链表
链式存储
优点:
- 离散分配空间,分配方便,改变容量方便。
- 单链表的节点是通过指针来连接的,因此在插入、删除节点时不需要移动其他节点,只需要修改指针的指向即可。
缺点:
- 由于链表每个节点只存储了指向下一个节点的指针,只能顺序存储,不可随机存储,所以访问节点时需要从头指针开始依次遍历访问,直到找到需要的节点,或者到达链表的结尾。
- 存储密度低,每个结点除了存储数据元素,还存储了指针。
6.3数据运算(基本操作)
6个基本操作:创销增删改查
顺序表 | 链表 | |
---|---|---|
数据弹性(可扩容) | √ | |
增、删 | √ | |
查找 | √ |
6.3.1初始化
顺序表:
需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源。
- 静态分配:静态数组,容量不可以改变。
- 动态分配:动态数组(malloc、free):容量可改变,但需要移动大量元素,时间代价高。
链表:
只需分配一个头结点(也可以不要头结点,只声明一个头指针),之后方便拓展。
6.3.2销毁表
顺序表:
- 修改Length = 0
- 释放空间
- 静态分配:静态数组,系统自动回收空间。
- 动态分配:动态数组(malloc、 free),需要手动free。
链表:
依次删除各个结点(free)。
6.3.3插入、删除
顺序表:
插入/删除元素要将后续元素都后移/前移。
时间复杂度O(n),时间开销主要来自移动元素。
链表:
插入/删除元素只需修改指针即可。
时间复杂度O(n),时间开销主要来自查找目标元素。
若元素占用空间很大,那么移动元素花费的时间要比查找元素花费是时间代价更大。
6.3.4查找
顺序表:
按位查找:使用顺序存储,每个数据元素大小相同,所以可以随机访问,即可以在**O(1)**时间内找到第i个元素。
按值查找:O(n)。若表内元素有序,可在 O(log_2n) 时间内找到。
链表:
按位查找:由于单链表每个节点只存储了指向下一个节点的指针,只能顺序存储,不可随机存储,所以访问节点时需要从头指针开始依次遍历访问,直到找到需要的节点O(n)。
按值查找:只能遍历O(n)