【逻辑结构】

线性表是具相同数据类型的 $n$ 个数据元素的有限序列，其中，相同数据类型意味着每个数据元素所占的存储空间相同，数据元素个数 $n$ 为线性表的长度，当 $n=0$ 时称为空表，反之 $n\neq 0$ 时称为非空表

一个非空表常记为：

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

其中 $a_i$ 是表中的第 $i$ 个数据元素，表中的 $a_{i-1}$ 领先于 $a_{i}$，$a_{i}$ 领先于 $a_{i+1}$，称 $a_{i-1}$ 是 $a_{i}$ 的直接前驱元素，$a_{i+1}$ 是 $a_{i}$ 的直接后继元素

对于 $i=1,2,…,n-1$ 来说，$a_{i}$ 有且只有一个直接后继，$a_n$ 为表尾元素；对于 $i=2,3,…,n$ 来说，$a_{i}$ 有且只有一个直接前驱，$a_1$ 为表头元素；

【顺序存储结构】

线性表的顺序存储结构称为顺序表，常用一维数组来实现，其通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，其支持对数据元素的随机访问，因此属于随机存取结构

设顺序表的每个元素占用 $c$ 个存储单元，则第 $i$ 个元素的存储地址为：

$LOC ( a_ i ) = LOC ( a_1 )+ ( i - 1 ) *c$

线性表的链式存储结构称为链表，其使用一组任意的存储单元来存放线性表的元素，这组存储单元在存储空间中，可以连续也可以不连续，即逻辑顺序与物理顺序可以不一致

为能正确表示元素间的逻辑关系，每个存储单元在存储数据元素的同时，还必须存储地址信息，这两部分构成了数据元素的存储映像，称为结点（Node），之后，将数据结构按照逻辑顺序链接在一起

根据结点的不同结构与结点间的链接关系，链表可分为以下四种：