定义线性表的逻辑关系与抽象操作，比较顺序表和链表的存储特征、复杂度与适用条件，建立后续实现的统一接口。

# 一、线性表的定义与抽象操作

线性表（Linear List）是具有相同数据类型的 $n$ 个数据元素的有限序列，其中 $n\ge0$ 。记作

$L=(a_1,a_2,\ldots,a_i,a_{i+1},\ldots,a_n).$

当 $n=0$ 时，称为空表。除首元素 $a_1$ 外，每个元素有且仅有一个直接前驱；除尾元素 $a_n$ 外，每个元素有且仅有一个直接后继。这是线性表的逻辑关系，和存储地址是否相邻无关。

# 1. 线性表的基本操作

操作	语义
InitList	初始化为空表
DestroyList	销毁表并释放其占用的资源
ListInsert(L, i, e)	在第 $i$ 个位置插入元素 $e$
ListDelete(L, i, e)	删除第 $i$ 个位置元素，并用 $e$ 返回其值
LocateElem	按值或判定条件查找元素位置
GetElem	取得第 $i$ 个位置的元素
Length	返回表长
Empty	判断是否为空
ClearList	清空所有数据元素
ListTraverse	依次访问每个元素

逻辑位置通常从 $1$ 开始编号；C 数组下标通常从 $0$ 开始编号。实现时必须明确约定，最常见的错误正是把两种编号混用。

# 2. 顺序表与链表

flowchart TB
    A[线性表 L] --> B[顺序存储：顺序表]
    A --> C[链式存储：链表]
    B --> B1[元素占用连续存储单元]
    B --> B2[可由首地址和下标直接定位]
    C --> C1[结点地址可不连续]
    C --> C2[通过指针或游标维持前驱后继关系]

对比项	顺序表	链表
元素地址	连续	可不连续
按位查找第 $i$ 个元素	$O(1)$	$O(n)$
已知前驱结点后的插入或删除	通常仍需移动元素	$O(1)$
按值查找	$O(n)$	$O(n)$
空间开销	可能预留未使用容量	每个结点需附加指针或游标
缓存局部性	通常较好	通常较差

“链表插入、删除都是 $O(1)$ ” 缺少前提。若只给出逻辑位置 $i$ ，必须先遍历到第 $i-1$ 个结点，总代价仍为 $O(n)$ 。只有已经得到相关结点或其前驱指针时，改链操作才是 $O(1)$ 。