顺序表和链表的对比

逻辑结构

• 都是线性表，都是线性结构

存储结构

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

基本操作

创

• 顺序表：分配一大片连续空间（动态分配、静态分配）
• 链表：只分配一个头结点

销

• 顺序表：修改lenth=0，将顺序表标记为一个空表
  • 静态分配：静态数组（自动回收空间）
  • 动态分配：动态数组（malloc、free）（需要手动free）
• 链表：依次销毁各个结点（free）

增删

• 顺序表：增/删都需要移动大量数据元素
  • 时间复杂度O(n),主要消耗到移动元素上（若数据元素很大，则移动的时间代价很高）
• 链表：只需要修改指针
  • 时间复杂度O（n），主要消耗在查找目标元素上

查

• 顺序表：
  • 按位查找：时间复杂度O（1）
  • 按值查找：时间复杂度O（n）（若顺序表内元素有序，时间复杂度O（$\log_{2}{n}$）
• 链表：
  • 按位查找：时间复杂度O（n）
  • 按值查找：时间复杂度O（n）

项目	顺序表	单链表
弹性（可扩容）	×	√
增/删	×	√
查	√	×

链表：表长难以估计，经常要进行增删操作
顺序表：表长可预估，查找操作较多

知识总览