数据结构–顺序表VS链表
逻辑结构
存储结构
顺序表:
优点:支持随机存取、存储密度高
缺点:大片连续空间分配不方便,改变容量不方便
链表:
优点:离散的小空间分配方便,改变容量方便
缺点:不可随机存取,存储密度低
基本操作
顺序表:
需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源
静态分配:静态数组
动态分配:动态数组( malloc、free)
容量可改变,但需要移动大量元素,时间代价高
链表:
只需分配一个头结点(也可以不要头结点,只声明一头指针)之后方便拓展
增删改查
顺序表:
插入/删除元素要将后续元素都后移/前移
时间复杂度O(n),时间开销主要来自移动元素
若数据元素很大,则移动的时间代价很高
链表:
插入/删除元素只需修改指针即可
时间复杂度O(n),时间开销主要来自查找目标元素
查找元素的时间代价更低
顺序表:
按位查找:O(1)
按值查找:O(n)
若表内元素有序,可在 O ( l o g 2 n ) 时间内找到 \color{red}若表内元素有序,可在O(log_2n)时间内找到 若表内元素有序,可在O(log2n)时间内找到
链表:
按位查找:O(n)
按值查找:O(n)
用顺序表还是链表
表长难以预估、经常要增加 / 删除元素――链表 \color{red}表长难以预估、经常要增加/删除元素 ―― 链表 表长难以预估、经常要增加/删除元素――链表
表长可预估、查询 ( 搜索)操作较多――顺序表 \color{red}表长可预估、查询(搜索)操作较多 ―― 顺序表 表长可预估、查询(搜索)操作较多――顺序表
知识点回顾与重要考点
开放式问题的答题思路:
问题:请描述顺序表和链表的bla bla bla…
实现线性表时,用顺序表还是链表好?
顺序表和链表的逻辑结构都是线性结构,都属于线性表。
但是二者的存储结构不同,顺序表采用顺序存储…(特点,带来的优点缺点);链表采用链式存储… (特点、导致的优缺点)。
由于采用不同的存储方式实现,因此基本操作的实现效率也不同。当初始化时…;当插入一个数据元素时…;当删除一个数据元素时…;当查找一个数据元素时…