1.5.1　顺序表与链表

线性表是最简单、最常用的一种数据结构，简言之，一个线性表是n（n≥0）个数据元素的有限序列。

顺序表和链表是常用的两种数据结构，也是线性结构中最简单的实例。两者最大的区别是：顺序表是随机存取，而链表是顺序存取的。

1．顺序表

把线性表的元素按逻辑次序依次存放在一组地址连续的存储单元，用这种方法存储的线性表简称为顺序表。

顺序表的特点是逻辑上相邻的数据元素其物理位置也相邻，表中第i个元素a_i的存储位置可用一个简单且直观的公式表示如下：

LOC（a_i）=LOC（a₁）+L×（i-1），1≤i≤n

其中，L是每个元素占用的存储单元的个数；LOC（a₁）是第一个元素a₁的存储地址（简称为基地址）；LOC（a_i）是元素a_i（2≤i≤n）的存储地址。

由此可见，只要确定了顺序表的起始存储位置，表中任一数据元素都可随机存取。所以顺序表是一种随机存取的存储结构，其示意图如图1-3所示。

显然，在这种存储方式下，容易实现对表的遍历。如果要在表的尾部插入一个新元素，也很容易。但是，要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。执行删除运算的情形类似，如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常采用数组来描述顺序表。

2．链表

链表是线性表的另一种存储方式，其特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），它由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

链表的形式主要有线性链表（或单链表）、循环链表和双向链表。

（1）在线性链表中，每个结点包括两部分：一个是存储数据元素信息的数据域；另一个是存储直接后继存储位置的指针域，该域表示了元素与其直接后继元素之间的逻辑关系，域中存储的信息称作指针或链。n个结点链接成一个链表，即为线性表的链式存储结构。由于此链表的每个结点中只包含一个指针域，故称为线性链表或单链表。

用链表来表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个元素其存储的物理位置不要求紧邻。因此，在使用链表时，人们关心的是它所表示的线性表中数据元素的逻辑顺序，而不是每个数据元素在存储器中的实际位置。那么如何设计链表的逻辑结构图呢？通常把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。例如线性表（a₁，a₂，a₃）的线性链表存储结构如图1-4所示。

其中，H称为头指针，它指示链表中第一个结点的存储位置，整个链表的存取必须从头指针开始进行。由于最后一个元素a₃没有直接后继，因此它的指针域设置为空（NULL）。

（2）由于每次对线性链表进行存取都必须从头指针开始，这给元素的查找及表的合并等操作带来了不便，为了克服该缺点，循环链表顺应而生。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。为此，从表中任一结点出发均可找到表中其他结点。进行表的合并时，仅需将一个表的表尾和另一个表的表头相接即可。

（3）以上两种链式存储结构的结点中只有一个指示直接后继的指针域，因此从某个结点出发只能顺指针往后寻找其他结点。若要寻找某结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，寻找某结点的直接后继的执行时间为O（1），而寻找其直接前驱的执行时间则为O（n）。为了克服这种单向性的缺点，出现了双向链表，其特点是每个结点中有两个指针域，一个指向直接后继；另一个指向直接前驱。

与顺序表相比，链表在对空间的利用上较合理，且在实现数据元素的插入和删除操作时，只需修改指针而不需要移动数据元素。因此，在很多场合下，它是线性表的首选存储结构，但是它失去了顺序表可随机存取的优点。仁者见者，智者见智，读者可根据实际情况选择最合适的数据结构来使用。