线性表的定义与基本概念

2026 大纲 二（一）线性表的基本概念。

线性表是什么

线性表是由 $n(n\ge 0)$ 个数据特性相同的元素构成的有限序列，记作 $L=(a_1,a_2,\dots ,a_n)$。$n$ 叫表长，$n=0$ 时是空表。

定义里有三个限定词，缺一条就不是线性表：

判据	含义	反例
数据特性相同	所有元素属于同一数据对象，占用相同大小的存储空间	一个数组里既放 int 又放结构体，不构成线性表
有限	元素个数 $n$ 是有限的	无穷序列不是线性表
序列	元素之间有确定的先后次序，相邻元素构成序偶关系	集合无序，不是线性表

其中第三条最要紧：它意味着元素之间的关系由位置决定，而不是由值决定。$(3,1,2)$ 和 $(1,2,3)$ 是同一个集合，但不是同一个线性表。"按位查找""在第 $i$ 个位置插入"这些操作之所以说得通，全靠这一条。

把"序列"这件事说细，就是非空线性表的四条特征：有唯一的"第一个"（无前驱）、有唯一的"最后一个"（无后继）、其余元素有且仅有一个直接前驱、有且仅有一个直接后继。这四条合起来正是"一对一"的精确表述，也是线性结构与树（一对多）、图（多对多）的分界线。

⚠️ 前驱和直接前驱不是一回事。 $a_1$ 到 $a_{i-1}$ 全都是 $a_i$ 的前驱，而直接前驱只有 $a_{i-1}$ 一个。链表结点的指针域存的是直接后继——这个"直接"是后面所有指针操作的前提。

逻辑结构与存储结构：为什么要分两层

逻辑结构回答"数据元素之间有什么关系"，面向问题，与计算机无关；存储结构（物理结构）回答"这些关系在内存里怎么表示出来"，面向机器。同一个逻辑结构可以配多种存储结构。

分层的价值，用一个例子就能说清：线性表的逻辑结构要求"能取到第 $i$ 个元素"，顺序表和链表都必须兑现这个承诺；但顺序表兑现它只要 $O(1)$，链表要 $O(n)$。"能不能做"是逻辑结构的事，"要花多少代价"是存储结构的事。

不分层，就会冒出三类似是而非的说法：

混淆的说法	为什么错	正确表述
"线性表是用数组实现的"	把逻辑结构和它的一种实现绑死了	线性表可以用顺序存储（数组）实现，也可以用链式存储实现
"链表不是线性表"	用存储结构去否定逻辑结构	链表是线性表的一种存储结构，其逻辑结构仍是线性表
"顺序存储的一定能随机存取"	把两个不同层面的"顺序"混为一谈	顺序表是顺序存储且支持随机存取；两个"顺序"毫无关系

一个分叉，推出全部差异

到了存储层，"$a_i$ 的直接后继是 $a_{i+1}$"这层关系只有两种表示办法——这是整章唯一需要记的分叉：

两条路的代价正好对读：靠地址相邻隐式表示，关系不占额外空间，代价是元素必须"排队站好"，插一个人就得全体后移；靠指针显式表示，关系占掉了额外空间，换来元素可以散落在任何地方，插入只要改指针。

下面对比表的每一行，你都应该能反推回这个分叉，不需要分别背两张表。

比较维度	顺序表	链表	差异的来历
存取方式	随机存取，$O(1)$	顺序存取，$O(n)$	地址可由公式算出 vs 必须顺链走
按位查找	$O(1)$	$O(n)$	同上
按值查找	$O(n)$（无序时）	$O(n)$	两者都要逐个比较
插入 / 删除	$O(n)$，平均移动约半个表	改指针 $O(1)$，但定位前驱 $O(n)$	逻辑相邻绑定物理相邻 vs 不绑定
空间分配	预先分配，需估计上限	按需申请，只受内存总量限制	是否要求整块连续空间
存储密度	$1$	$<1$	链表每结点多一个指针域
空间碎片	需要一整块连续空间	结点可散落，不要求连续	同上

存储密度是这里唯一需要算的量：${\displaystyle \frac{\text{元素本身占用}}{\text{整个结点占用}}}$。顺序表恒为 1；存 int 的单链表，数据域 4 字节、指针域 4 字节，密度只有 0.5。但这个数会随数据域变大而迅速接近 1——数据域 100 字节时约 0.96。

所以"链表比顺序表费空间"是一句站不住的笼统结论：数据域越大，指针的相对开销越小；而表长难以预估时，顺序表按上限预分配造成的空闲区浪费，往往远超链表的指针开销。

选型就是把这个分叉套到具体场景上：

应用特征	选择	理由
表长变化大、事先难以估计规模	链表	顺序表要么溢出，要么按上限预分配造成浪费
表长稳定、事先容易确定	顺序表	存储密度为 1，且不必付指针开销
主要操作是按位序取值，很少增删	顺序表	随机存取 $O(1)$ 是链表给不了的
频繁在表中间插入、删除	链表	不必移动元素；结点信息量越大，这个优势越明显

线性表的抽象数据类型：基本操作清单与三点约定（想看全 ADT 的操作与前置条件就展开）

抽象数据类型（ADT）把"这个结构对外承诺哪些操作"和"这些操作怎么实现"分开。

操作	含义	前置条件
InitList(&L)	构造一个空表 $L$	无
DestroyList(&L)	销毁表 $L$，释放其占用的空间	$L$ 已存在
ClearList(&L)	将 $L$ 重置为空表（结构还在）	$L$ 已存在
ListEmpty(L)	判空	$L$ 已存在
ListLength(L)	返回表长 $n$	$L$ 已存在
GetElem(L, i, &e)	按位查找：用 $e$ 返回第 $i$ 个元素	$L$ 已存在且 $1\le i\le n$
LocateElem(L, e)	按值查找：返回第一个值为 $e$ 的元素的位序	$L$ 已存在
ListInsert(&L, i, e)	在第 $i$ 个位置之前插入元素 $e$	$1\le i\le n+1$
ListDelete(&L, i)	删除第 $i$ 个元素	$1\le i\le n$
TraverseList(L)	遍历，依次访问每个元素	$L$ 已存在

三点必须说清的约定，否则后面代码的边界会全部对不上：

1. 位序从 1 开始。第 1 个元素的位序是 1，不是 0。而顺序表底层数组的下标从 0 开始，所以第 $i$ 个元素存在 data[i-1]——这个"错位 1"是顺序表代码里最容易写反的地方。
2. 插入位置的合法范围是 $1\le i\le n+1$，删除是 $1\le i\le n$。插入比删除多出的那个 $n+1$，对应"插在表尾之后"，此时不需要移动任何元素。
3. & 表示该参数会被操作修改（C++ 的引用传参）。凡是可能改变表本身（表长、首地址、头指针）的操作都带 &，只读操作不带。

这些操作是怎么被挑出来的？ 判据是"是否只能由结构的实现者完成"。求表中最大值、判断表是否有序、合并两个表，这些都能用上面的基本操作组合出来，所以不进基本操作清单；而插入、删除要直接操纵存储结构本身（移动元素或改指针），使用者无法用别的操作拼出来，所以必须进清单。一元多项式相加、集合求并这类应用，本质上就是基本操作的组合。

考点速记

这一节不单独成题。 它的结论是在别处兑现的——顺序表那一篇的题会问"哪个操作平均 $O(1)$""哪些操作必然引起元素移动"，单链表那一篇的题会给你一串指针语句问功能，而判断这些题的依据，全是本篇那个分叉。

三条会被反复调用的结论：

1. 逻辑结构决定能做什么，存储结构决定做得快不快。 两种存储结构对外承诺的基本操作完全一致，差的只是每个操作的代价。
2. 顺序表与链表的所有差异同源：前者用地址相邻隐式表示逻辑关系，省了关系的空间、赔上位置的自由；后者用指针显式表示，反之。
3. 位序从 1 起算，插入合法范围 $1\le i\le n+1$、删除 $1\le i\le n$；顺序表底层下标从 0 起，第 $i$ 个在 data[i-1]。

易错："链表插删 $O(1)$"必须带上"已知前驱指针"这个前提。 只给位序 $i$ 时，得先花 $O(n)$ 走到第 $i-1$ 个结点，总代价仍是 $O(n)$。链表真正占便宜的场景是"边遍历边增删"——遍历已经把前驱送到手里了。

易错："顺序存储"和"顺序存取"是两个层面的词。 顺序存储（顺序表）支持的恰恰是随机存取；顺序存取指的是必须从头逐个走，那是链表的性质。两个词长得像，结论正好相反。

易错：别用存储结构去否定逻辑结构。 链表是线性表，栈和队列也是线性表——它们受限的是运算，不是元素之间的关系。

教材出处

• 线性表的定义、长度与空表，以及非空线性表的四条特征： 严蔚敏《数据结构（C 语言版）》（第 2 版），p19，2.1 节"线性表的定义和特点"。
• 线性表的抽象数据类型定义与基本操作清单（InitList、GetElem、ListInsert 等）： 同书 p22–p23，2.3 节。书中同时说明"其他如求线性表的拆分、复制等操作也都可以利用上述 基本操作的组合来实现"。
• 存储密度的定义、顺序表存储密度为 1 与单链表整型结点存储密度为 0.5 的算例， 以及四条选型判据（空间分配、存储密度、存取效率、插删效率）： 同书 p41，2.6 节"顺序表和链表的比较"。

相关知识

顺序表（平均移动次数的推导在那一篇）｜单链表（链式存储主篇）｜双链表｜循环链表｜静态链表｜链表的三种通用解法｜算法的时间复杂度与空间复杂度｜栈和队列的基本概念（操作受限的线性表）

相关文章

• 顺序表（数组）
• 单链表
• 双链表
• 循环链表
• 静态链表
• 链表题的三种通用解法

真题练习