软考-软件设计师：数据结构-线性结构-线性表 作者：马育民 • 2026-02-08 17:00 • 阅读：10001 # 介绍  线性表是最基础的 **线性数据结构**，如上图，它是由 **n个具有相同特性的数据元素** 组成的有限序列，元素之间是“一对一”的逻辑关系： - 除了第一个元素，每个元素有且仅有一个**直接前驱**； - 除了最后一个元素，每个元素有且仅有一个**直接后继**。 ##### 直接前驱 对于线性表中的某个元素 `b`，排在它 **紧前面的那个元素 `a`**，元素`a` 就是元素 `b` 直接前驱 ##### 直接后继 对于某个元素 `b`，排在它 **紧后面的那个元素 `c`**，元素 `c` 就是 元素 `b` 的直接后继 ### 类比 线性表就像一条“直线”，元素按顺序排成一列，比如排队的人、一串数字 `[1,2,3,4]`，都是线性表的直观体现。 # 特征 1. **有限性**：元素个数是有限的（不会无限长）； 2. **有序性**：元素有明确的先后顺序，位置固定（比如第1个、第2个元素）； 3. **同构性**：所有元素的类型相同（比如都是整数，或都是字符串）。 # 实现方式 线性表只是**逻辑结构**（元素的逻辑关系），实际存储时有两种主流的**物理实现方式**，也是你之前问过的数组和链表： | 实现方式 | 物理存储特点 | 核心优点 | 核心缺点 | 典型操作时间复杂度 | |----------|--------------------|-------------------------|-------------------------|--------------------------| | 顺序表（数组） | 连续内存存储 | 随机访问快（O(1)）| 插入/删除慢（O(n)）| 访问：O(1)；增删：O(n) | | 链表 | 非连续内存存储 | 插入/删除快（O(1)）| 随机访问慢（O(n)）| 访问：O(n)；增删：O(1) | #### 补充：顺序表 vs 链表 - 顺序表：依赖 **数组** 实现，长度固定（静态）或可动态扩容（动态），扩容时需要重新分配内存、拷贝元素； - 链表：依赖 **节点+指针** 实现，长度完全动态，无需提前分配内存，但每个节点要额外存储指针，空间开销更大。 # 线性表的通用操作 不管是顺序表还是链表，作为线性表都需要支持这些基础操作，只是实现方式不同： 1. **初始化**：创建一个空的线性表； 2. **判空**：判断线性表是否有元素； 3. **求长度**：返回线性表的元素个数； 4. **按索引访问**：获取第i个位置的元素； 5. **按值查找**：找到第一个值为val的元素的位置； 6. **插入**：在第i个位置插入元素val； 7. **删除**：删除第i个位置的元素； 8. **遍历**：依次访问所有元素。 # 应用场景 1. **顺序表（数组）**：适合需要频繁随机访问的场景，比如： - 排行榜、成绩表（快速按索引查数据）； - 缓存、固定长度的数据集存储。 2. **链表**：适合频繁插入/删除的场景，比如： - 消息队列、任务队列（频繁新增/删除任务）； - 浏览器的前进/后退功能（双向链表）； - 操作系统的内存管理（动态分配内存）。 # 总结 1. 线性表是**逻辑结构**，表示元素“一对一”的线性关系，顺序表（数组）和链表是它的两种**物理实现**； 2. 顺序表的核心优势是**随机访问快**，链表的核心优势是**增删操作快**，需根据场景选择； 3. 线性表的通用操作（插入、删除、访问、遍历）对两种实现都适用，但底层执行效率差异显著。 原文出处：http://malaoshi.top/show_1GW2k0fnUzRd.html