什么是线性表

学习目标

本节先建立线性表的整体概念。

学习完成后，你需要理解：线性表不是某一种具体代码实现，而是一种抽象的数据关系。它描述的是元素之间存在一对一的先后关系，后续的数组、顺序表、链表、栈、队列等结构都可以看作围绕线性关系展开的不同实现或限制。

线性表中的元素按照某种顺序排列。除了第一个元素和最后一个元素之外，每个元素通常都有一个直接前驱和一个直接后继。

例如，一排学生的座位可以看作线性表：

张三 -> 李四 -> 王五 -> 赵六

在这个关系中：

这就是典型的线性关系。它不像树那样一个节点可以有多个子节点，也不像图那样一个元素可以和许多元素任意连接。

线性表本身强调的是“逻辑关系”，而不是“内存中具体怎么存”。

同一个线性表，可以用不同方式实现：

这两种方式表达的逻辑关系都可以是一样的：第一个元素后面是第二个元素，第二个元素后面是第三个元素。区别在于它们在内存中的组织方式不同，因此访问、插入、删除的代价也不同。

这也是学习数据结构时反复出现的一条主线：逻辑结构和存储结构不是一回事。

线性表通常会支持以下操作：

不同实现方式下，这些操作的效率会不同。例如，顺序表按位置访问很方便，而链表在已知节点位置时插入和删除更灵活。

很多现实场景都具有线性关系。

例如：

这些场景中的元素往往可以按前后顺序排列。只要问题的核心关系是“一个接一个”，就可以先考虑线性表模型。

线性表适合表达简单顺序关系，但不适合表达所有数据关系。

例如，文件目录更像树结构，因为一个文件夹下面可以有多个子文件夹。城市交通网络更像图结构，因为一个城市可以连接多个城市。用户关系也常常不是单纯的一条线，而是复杂的网状连接。

因此，线性表是基础，但不是所有问题的答案。学习它的意义在于先掌握最简单、最常见的数据关系，再逐步过渡到更复杂的结构。

线性表表达的是元素之间的一对一顺序关系。

它是一种逻辑结构，不等于某一种具体代码实现。顺序存储和链式存储都可以实现线性表，但它们在访问、插入、删除和空间使用上有不同特点。后续几节会分别学习这两种重要实现方式。