介绍

线性表是最基础的 线性数据结构，如上图，它是由 n个具有相同特性的数据元素 组成的有限序列，元素之间是“一对一”的逻辑关系：

• 除了第一个元素，每个元素有且仅有一个直接前驱；
• 除了最后一个元素，每个元素有且仅有一个直接后继。

直接前驱

对于线性表中的某个元素 b，排在它 紧前面的那个元素 a，元素a 就是元素 b 直接前驱

直接后继

对于某个元素 b，排在它 紧后面的那个元素 c，元素 c 就是 元素 b 的直接后继

类比

线性表就像一条“直线”，元素按顺序排成一列，比如排队的人、一串数字 [1,2,3,4]，都是线性表的直观体现。

特征

1. 有限性：元素个数是有限的（不会无限长）；
2. 有序性：元素有明确的先后顺序，位置固定（比如第1个、第2个元素）；
3. 同构性：所有元素的类型相同（比如都是整数，或都是字符串）。

实现方式

线性表只是逻辑结构（元素的逻辑关系），实际存储时有两种主流的物理实现方式，也是你之前问过的数组和链表：

补充：顺序表 vs 链表

• 顺序表：依赖 数组 实现，长度固定（静态）或可动态扩容（动态），扩容时需要重新分配内存、拷贝元素；

• 链表：依赖 节点+指针 实现，长度完全动态，无需提前分配内存，但每个节点要额外存储指针，空间开销更大。

线性表的通用操作

不管是顺序表还是链表，作为线性表都需要支持这些基础操作，只是实现方式不同：

1. 初始化：创建一个空的线性表；
2. 判空：判断线性表是否有元素；
3. 求长度：返回线性表的元素个数；
4. 按索引访问：获取第i个位置的元素；
5. 按值查找：找到第一个值为val的元素的位置；
6. 插入：在第i个位置插入元素val；
7. 删除：删除第i个位置的元素；
8. 遍历：依次访问所有元素。

应用场景

1. 顺序表（数组）：适合需要频繁随机访问的场景，比如：
   • 排行榜、成绩表（快速按索引查数据）；
   • 缓存、固定长度的数据集存储。
2. 链表：适合频繁插入/删除的场景，比如：
   • 消息队列、任务队列（频繁新增/删除任务）；
   • 浏览器的前进/后退功能（双向链表）；
   • 操作系统的内存管理（动态分配内存）。

总结

1. 线性表是逻辑结构，表示元素“一对一”的线性关系，顺序表（数组）和链表是它的两种物理实现；
2. 顺序表的核心优势是随机访问快，链表的核心优势是增删操作快，需根据场景选择；
3. 线性表的通用操作（插入、删除、访问、遍历）对两种实现都适用，但底层执行效率差异显著。

原文出处：/show_1GW2k0fnUzRd.html