二、线性表

本章导览

共 4 个小节：线性表的定义和基本操作、线性表的顺序表示（顺序表）、线性表的链式表示（链表）、顺序表 VS 链表

本章重点

• 顺序表：随机存取 O(1)、增删需移动 O(n)
• 链表：增删 O(1)、不能随机存取
• 口诀：读多用顺序表，增删多用链表

线性表的定义和基本操作

关键点

• 线性表 = n 个同类型元素的有限序列
• 位序从 1 起（下标从 0）；逻辑相邻 ≠ 物理相邻
• 会改变表本身的操作，参数要用引用「&」

线性表的顺序表示（顺序表）

关键点

• 地址连续、随机存取 O(1)，增删需移动约一半元素 O(n)
• 静态分配定长、动态分配可扩容
• 易错：位序 i 对应下标 i-1

线性表的链式表示（链表）

关键点

• 结点 = 数据域 + 指针域；增删只改指针、不能随机存取
• 单链表指后继、双链表含前驱、循环链表首尾相接、静态链表用数组+游标
• 实务常用带头结点简化边界

单链表

关键点

头插法、尾插法：核心就是初始化操作、指定结点的后插操作

双链表

关键点

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度 O(n)

循环链表

静态链表

顺序表 VS 链表

关键点

• 存取：随机 O(1) ↔ 顺序 O(n)
• 存储密度：顺序表高 ↔ 链表含指针偏低
• 增删：移动 O(n) ↔ 改指针 O(1)；读多选顺序表，增删多选链表