考研笔记

速查：顺序表与链表

速查表：核心是教材 2.3.6「顺序表和链表的比较」的四个维度。第 2 章的概念页与指针语句真题见 2.1~2.2、2.3.1~2.3.2、2.3.3~2.3.6。

四个维度（2.3.6）

1. 存取（读/写）方式

顺序表既可以顺序存取，也可以随机存取，链表只能从表头开始依次顺序存取。 例如在第 个位置上执行存取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问 次。

2. 逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。

3. 查找、插入和删除操作

操作顺序表链表
按值查找（表无序）
按值查找（表有序）（可用折半查找）
按序号查找（支持随机访问）
插入、删除平均需要移动半个表长的元素只需修改相关结点的指针域

4. 空间分配

顺序表链表
分配时机静态分配需一次性给足；动态分配可扩容，但扩容需要移动大量元素，操作效率低只在需要时申请，只要内存足够就能分配
空间利用预分配过大浪费、过小溢出每个结点有指针域，存储密度低于顺序表

选择建议

场景选择
表长可预估、变化不大顺序表
频繁按序号存取顺序表（ 随机存取）
表长难以预估、频繁增删链表
要用折半查找只能顺序表
要用折半插入、希尔、快排、堆排序只能顺序表（需随机存取）

四种链表对照

单链表双链表循环单链表循环双链表
指针域nextprior + nextnextprior + next
找前驱
表尾特征next==NULLnext==NULLnext==Lnext==L
判空L->next==NULL同左L->next==LL->next==L && L->prior==L
从任一结点访问全表否否是是

静态链表（2.3.5）

  • 用数组来描述线性表的链式存储结构，结点也有 data 和 next，但指针是结点在数组中的相对地址（数组下标），也称游标。
  • 和顺序表一样，静态链表也要预先分配一块连续的内存空间。
  • 以 next == -1 作为其结束的标志。
  • 插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。
  • 教材评价：「总体来说，静态链表没有单链表使用起来方便，但在一些不支持指针的高级语言（如 Basic）中，这是一种非常巧妙的设计方法。」

高频边界

说法判断说明
「链表可以随机存取」❌只能从表头依次顺序存取
「顺序表只能顺序存取」❌顺序存取和随机存取都可以
「链表插入删除是 」⚠️已定位到位置时是；若要先查找仍是
「链表不需要连续空间」✅但静态链表需要（用数组实现）
「静态链表是顺序存储」⚠️物理上是数组，逻辑上是链式；结束标志是 next==-1
「链表的存储密度更高」❌更低，每个结点多一个指针域
「有序链表可以折半查找」❌折半要求随机存取
「顺序表扩容代价很小」❌需要移动大量元素，操作效率低
「循环单链表判空是 L->next==NULL」❌是 L->next==L

链接

反向链接