02-2.3.6 顺序表和链表的比较

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

逻辑结构

不管是顺序表还是链表，都属于线性表，都是线性结构

物理结构/存储结构

顺序表采用了顺序存储的方式

• 优点：支持随机存取、存储密度高
• 缺点：大片连续空间分配不方便、改变容量不方便
  链表采用链式存储的方式
• 优点：离散的小空间分配方便、改变容量方便
• 缺点：不可随机存取、存储密度低（需要指针）

数据的运算/基本操作

复习回忆思路：创销、增删改查

创

顺序表：

• 需要预分配大片连续空间
• 若分配空间过小，之后不方便扩展容量
• 若分配空间过大，则浪费内存资源
  链表：
• 只需要分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便扩展
  如果我们的线性表采用
• 静态分配：静态数组。那么容量不可改变
• 动态分配：动态数组。即便使用malloc, free函数改变容量，但是需要移动大量元素，时间代价很高

销

链表：

• free依次删除各个结点——手动回收空间
  顺序表：
• 修改length = 0——系统自动回收空间

由malloc申请的地址，是内存中的堆区，堆区不会由系统自动回收
所以在写代码的时候malloc和free必须成对出现

增、删

顺序表：

• 插入/删除元素要将后续的元素都后移/前移
• 时间复杂度：$O(n)$，时间开销主要来自移动元素
• 如果数据元素很大，则移动的时间代价很高
  链表：
• 插入/删除元素只需要修改指针即可
• 时间复杂度：$O(n)$，时间开销主要来自查找目标元素
• 查找元素的时间代价更低

查

顺序表：

• 按位查找：$O(1)$
• 按值查找：$O(n)$，若表内元素有序，可在$O(lo{g}_{2}n)$时间内找到（如二分查找*）
  链表：
• 按位查找：$O(n)$
• 按值查找：$O(n)$

如何抉择？

表长难以估计、经常要增加/删除元素————链表
表长可预估、查询（搜索）操作较多————顺序表

知识回顾

开放式问题的回答思路：

• 可以先探讨逻辑结构
• 再讨论存储结构
• 然后再探讨一些比较重要的基本操作的实现效率
• 最后得出结论