线性表是最简单，最常用，也是最需要熟练掌握的数据结构，没有之一。后续的数据结构都要在线性表基础上构建。

线性表的定义

对于同一数据对象，且相邻的数据元素之间存在次序关系的，该数据对象由 $n (n \ge 0)$ 个数据特性相同的元素构成的有限序列即称为线性表。

一般的，线性表形如 $A_1, A_2, \cdots, A_N$，我们认为这个表的大小是 $N$。特殊的，将大小为 $0$ 的表称为空表。

对于非空的线性表，具有如下的特性：

  • 存在唯一的一个被称作 “第一个” 的数据元素。
  • 存在唯一的一个被称作 “最后一个” 的数据元素。
  • 除了第一个元素之外，结构中每一个数据元素都只有一个前驱。
  • 除了最后一个元素以外，结构中每一个数据元素都只有一个后继。

线性表的 ADT

通常而言，Print 和 MakeEmpty 是常用的操作，Insert 插入操作 和 Delete 删除操作也是常用的。可能存在 Find 操作返回某个元素首次出现的位置，也可能存在 Get 操作返回某个位置的元素等等。

线性表的表示

线性表在实际实现当中通常有两种形式，一种是顺序存储，即使用数组来存储，另一种是链式存储，即使用链表来存储。

两种方法各有优缺点，需要根据实际的需求来选择。

顺序存储

对表的所有操作都可以使用数组实现。由于数组的大小通常是固定的，因此需要预先估计表的最大值。因此可能会造成大量空间的浪费，特别是存在许多未知大小的表的状态下。

数组实现的优点是可以快速访问表中的任意元素，时间复杂度为 $O(1)$。并且使 Print 和 Find 可以以线性时间复杂度完成。但是插入和删除操作的开销是较高的。例如在 0 位置插入需要将整个数组后移一个位置以便腾出空间来，删除元素也要将所有元素前移。因此两种操作的复杂度都是 $O(N)$。

由于插入和删除操作的开销较大，并且需要预先恰当的估计表的大小，因此实际使用中，若要对表中元素进行频繁修改的场景下通常不使用顺序存储实现。

链式存储

链表使得表可以不连续存储，抽象的来说每个子结构都包含了表元素本身和指向该元素后继元素的结构的指针。最后一个元素的指针指向空指针。

1type Node struct {
2    Value interface{}
3    Next *Node
4}

链表的优点是可以动态的增长，因此可以用来实现大小未知的表。并且插入和删除操作的开销较小，因为只需要修改指针即可。因此在不考虑要提前遍历到前置节点的情况下，插入和删除两种操作本身的复杂度都是 $O(1)$。

链表的缺点是无法快速访问表中的任意元素，因为需要遍历到该元素。因此 Find 和 Get 操作的复杂度都是 $O(N)$。但在实际使用中，这个估计可能是保守的，因为不一定每次都从开头重新遍历，是存在一定优化空间的。

表头

有时候，我们需要围绕数据结构存储一些信息，例如当前表的长度，它的最大长度，由或是为了解决数据结构实现过程中的一些麻烦。或者为了优化尾部插入而额外维护一个尾节点地址等等，我们可以通过另一个结构来存储，这个节点就称作表头 (header) 或称作哑节点 (dummy node)。

1type LinkedList struct {
2    Length int
3    MaxLength int
4    Next *Node
5}