链表结构原理 与 数组模拟链表 的应用

**链表（linked list）**是我们最常使用的一种数据结构。在信息学竞赛中，经常需要使用链表作为遍历等操作使用的数据结构参与解题过程。这是因为链表具有自己的优点。用数组模拟链表，可以简化链表的使用，从而使链表更好的为我们服务。如果您已经知道链表数据结构的原理，可以跳过第一部分直接查看与数组模拟链表有关的内容。

“链表”数据结构

什么是链表？

**链表(linked list)**是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

线性表（链接到百度百科的“线性表”词条）的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如下图所示），表示线性表中的一个数据元素。

数据域 data

指针域 next

其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

链表具有快速插入与删除的优点，还能在运行时动态分配内存空间。

实现快速插入与删除（链表的优点）

和普通的数组相比，链表具有能够快速插入和删除元素而不改变其它元素排列顺序的优点。 举例：对于一个长度为 n 的元素集合，如果这个集合用普通的非链表结构线性表来存储（如一维数组），那么，向其中插入一个元素需要花费大量的时间复杂度。如，在第一个元素后插入一个新元素 A，那么这个数组从原来的第二个元素开始，都需要全部向后移动一个位置。而如果采用链表结构，只需要在一个新的存储空间中记录新元素 A，并且将第一个元素的 next 域（其内容记为 point_old）修改为指向 A 的指针（记为 point_new），并将 A 的 next 域设置为 point_old 即可，这里只需要简单的 O(1) 算法。

示意图如下。原链表内容：

_point_

内存地址A

内存地址B

内存地址C

_data_

1

2

3

_next_

B

C

_null_

（注：null 代表空，即无后续元素指针。下文所提到的 null 均代表空。）

插入2.5到第一个元素位置后的链表内容：

_point_

内存地址A

内存地址B

内存地址C

内存地址D

_data_

1

2

3

2.5

_next_

D

C

_null_

B

（注：null 代表空，即无后续元素指针。下文所提到的 null 均代表空。）

从一次插入操作中可以得知以下结论：

1、可以看出，我们并不需要在为新元素提供连续的存储位置，而是随意开辟了一个新的地址D，只是在第一个元素的 next 域中对后继元素地址进行了修改，并在新元素的 next 域链回原先的后继元素即可。

2、对于一个链表，它遍历一次所需要的时间要长于普通的数组，因为每次遍历一个元素，都不能简单的通过线性移动获得下一个元素的内存地址，而需要通过指针进行定位，但链表的遍历仍然是线性的操作。因此，链表特别适合需要大量编辑、插入、删除等操作的时候使用。如果仅仅需要遍历等操作，则可以直接使用普通数组。

删除操作和遍历类似，在此不再赘述。

链表的遍历

链表的遍历是线性算法。开始的时候，指针 p 在第一个元素上。处理完 p 后，指针 p <- p^.next（这句话是类 Pascal 伪语言，意思是 把 p 所代表的元素的 next 域的指针赋值给 p）。也就是传递它的后继元素地址。然后，继续进行对p的遍历，如此循环，直到 p ==  null。（对于 Pascal，null 为 nil，== 为 =）

遍历的 Pascal 伪代码：

p := first; // fisrt 存储第一个元素的内存地址。

while (p<>nil) do

begin

//处理p代表的这个元素。

p := p^.next;

end;

数组模拟链表

我们简单的介绍了链表的基础知识。要发挥链表动态分配内存空间的优势，需要使用指针建立链表。但是，在信息学竞赛中，我们基本上不需要过多考虑动态空间分配，所以，使用数组模拟链表就可以很好的实现链表数据结构。

数组模拟链表，是一种半静态链表，是链表的线性存储，比链式存储要简单的多了。每个链表可以用一对数组或一个记录数组表示，每个元素是有两个数据域：分别是数据_data_ 域和下一个结点在数组中的位置_next_ 域（整型的）。这样插入，删除，遍历等，都可以归结到数组操作了，这就比链式存储容易多了，却不丧失链表快速插入删除的优势。以下所说的指针，都是模拟指针，代表某元素在数字中的位置。

下面是一个用数组模拟链表操作的简单例子。

//By Ceeji
//From https://ceeji.net/blog
Program Example;
Const max=10000;
Type node=record
           data,next:longint;
          end;
Var table:array[1..max]of node;
    i,j,k: longint;
Begin
   // 加入初始元素
   table[1].data:=1;
   for i:=2 to 500 do
   begin
     table[i].data:=i;
     table[i-1].next:=i;
   end;
   table[500].next:=0;
   //在元素200后插入数据
   table[501].data:=-1;
   j:=table[200].next;
   table[200].next:=501;
   table[501].next:=j;
   //遍历数据
   i:=1;
   while i<>0 do
   begin
      writeln(table[i].data);
      i:=table[i].next;
   end;
End.

如此简短的代码，就实现了数组模拟链表，它能够很快插入和删除数据（见代码），和很快的遍历，却又非常易于编写。

那么，数组模拟列表有哪些应用呢？

数组模拟链表的应用

例 现有 n 个城市，给出他们之间有哪些城市之间有道路和道路的长度（大于0。如果不给出，说明这两个城市之间没有路）。求从城市1到城市 n 的最短路径（编号从1开始）。（n≤5000，道路数量不超过 20000 个）。

分析 我们并不是要分析这个题目本身，而是要分析这个题目所使用的数据结构。在解决这个问题的时候，我们必须存储所有的道路长度。在一种最大众化的图论的最短路算法中我们可以知道，我们需要不断的遍历从某一城市出发的到其它城市的所有道路。无疑，使用数组存储最适合遍历。假设使用数组A[1..n,1..n]代表 某两个城市间的道路长度，那么所需要的空间为 5000 * 5000 = 25,000,000 = 2.5 亿。这是个巨大的数字，很多情况下我们无法承受，不是超时，就是内存溢出。

但是，如果我们采用数组B[1..m,1..3]存储，（1..3分别代表某个道路的开始城市，结束城市，道路长度）空间问题解决了。因为最多需要空间为 20000 * 2 * 3。但是此时，我们要找从某个城市出发的道路，每次都需要遍历最多 20000 * 2 个元素，去查找哪一个道路的开始城市为我们所需要的。显然这是不现实的。（* 2 是因为本题目中的道路是没有方向的，从A到B有一条道路，那么从B到A也要重新存储。）

此时，我们想到了链表。

我们使用数组C[1..n]存储。C[i] 代表 记录以第i个城市为起始端的第一条道路的指针（整形）。那么，我们能够很轻易的遍历到第一条道路，然后，我们把这些道路串成链表，就可以轻易的继续遍历到底。我们把存储具体道路的链表数组记为D（类型 node，其中 每个 node 有两个域 data 和 next，data 表示道路的结束城市的编号），那么D数组最多才有 40000 个元素，80000 个整数。每当读入一条道路，我们就把结束城市的编号加入D数组的尾部，并将这个指针插入到相对应的开始城市的道路链表的第一个位置（这个链表的头是C[i]，i是开始城市编号），维护C数组（记录第一条道路的指针），然后，如果原先已经插入过道路，让新的道路的 next 挂接上第二个道路。那么我们遍历就方便多了。空间上可行，时间上也可行。

为什么要插入到第一个位置？因为如果插入到其他位置，我们需要先遍历到这个位置，然后才能插入。而第一个位置不需要遍历，可以直接由 C 数组取出指针。

由于编程简单，数组模拟链表是图论、大规模数据遍历、树等数据结构最佳的存储方式。