线性表

顺序表链表

顺序表：元素地址连续，支持随机访问

1. 基本概念

• 线性表：具有相同数据类型的 n 个数据元素的有限序列
• 特点：有唯一的第一个元素和最后一个元素，除首尾外每个元素有且仅有一个前驱和一个后继

2. 存储结构对比

存储方式	地址连续	支持随机访问	插入/删除效率	空间利用率
顺序表	是	是	低	低
链表	否	否	高	高

• 顺序表：用一组地址连续的存储单元依次存放线性表元素
• 链表：每个结点包含数据域和指针域，通过指针连接

3. 动画演示

顺序表链表

顺序表：元素地址连续，支持随机访问

4. 易错点小贴士

5. 线性表的典型应用

• 作为栈、队列、字符串等数据结构的基础
• 任务队列、浏览历史、购物车、文本编辑器的撤销/重做等

应用场景	推荐结构
需要频繁随机访问	顺序表
需要频繁插入删除	链表

---

习题

习题 1

简述线性表的定义和主要特点。

答案与解析

线性表是 n 个数据元素的有序序列，有唯一首尾，元素一对一关系。

习题 2

顺序表和链表各自的优缺点是什么？

答案与解析

顺序表：查找快，插入/删除慢，空间利用率低；链表：插入/删除快，查找慢，空间利用率高。

习题 3

单链表插入和删除操作的基本思想是什么？

答案与解析

插入：新结点指向后继，前驱指向新结点；删除：前驱指向被删结点的后继。

习题 4

如何实现线性表的遍历？

答案与解析

顺序表：下标循环；链表：指针逐结点访问。

习题 5

线性表有哪些典型应用？

答案与解析

栈、队列、字符串、查找、排序、合并等。

---

考研真题

真题 1

【2022·数据结构】线性表的顺序存储结构和链式存储结构各有什么优缺点？

答案与解析

顺序存储结构优点：支持随机访问，存取速度快；缺点：插入删除需移动大量元素，空间利用率低。

链式存储结构优点：插入删除操作简单高效，空间利用率高；缺点：不支持随机访问，查找效率低。

真题 2

【2021·数据结构】简述单链表和双链表的区别及各自适用场景。

答案与解析

单链表：每个节点只有一个指向后继的指针，结构简单，适合只需向一个方向遍历的场景。

双链表：每个节点有两个指针分别指向前驱和后继，支持双向遍历，适合需要频繁在两个方向移动的场景，如文本编辑器。