什么是链表

大家都知道自行车，可是你有没有仔细观察过自行车的链条呢？如下图9.5.1就是一段自行车链条的样子。

我们发现，自行车的链条虽然很长，却是由一个个相同的小环节连接而成的。如左下图9.5.2所示。每个环节又可以分成两部分：一部分是一个铁圈，让别的环节能够连接它；另一部分则是一个铁拴，可以去连接别的环节。于是，将这些环节一一连接起来，就形成了长长的链条。

这时候，我们想到了这样一种结构：

struct node
{
   int data;
   node *next;
};

这个结构有两个成员数据，一个是整数data，另外一个是指向这种结构的指针next。那么如果有若干个这样的结构变量，就能像自行车链条一样，把这些变量连接成一条链子。如左下图9.5.3所示。

我们把这些利用结构指针连接起来的结构变量称为链表（Link List），每一个结构变量（相当于链条中的每个环节）称为链表的结点（Node）。如右上图9.5.4所示。

和数组一样，链表也可以用来存储一系列的数据，它也是电脑中存储数据的最基本的结构之一。然而，我们已经拥有了数组，也了解了数组的动态分配（堆内存），我们为什么还需要链表呢？

相信很多人都玩过即时战略游戏（RTS），比如时下流行的魔兽争霸、曾红极一时的红色警戒。可是大家有没有考虑过，每个战斗单位都有它们各自的属性，电脑又是如何为我们造出来的部队分配内存的呢？

显然，部队的数量在程序执行之前是未知的。如果用数组来存储这些数据，那么就会造成游戏前期浪费内存（没有那么多的部队），游戏后期存储空间不够（战斗单位数大大增加）的情况。

那么使用数组的动态分配行不行呢？还是不行。因为部队的数量在程序执行的时候仍然是未知的。甚至连玩家自己也不知道要造多少战斗单位，只是根据战斗的实际情况来发展自己的势力。所以，这时候最合理的内存分配方式就是每造一个战斗单位分配一个内存空间。

然而，新问题又出现了：建造各单位的时间一般不可能是完全连续的，根据不同时刻程序运行的实际情况，每个单位分配到的内存空间也不是连续的了。空间不连续就意味着没有了方便的数组下标。我们就很难把这些零零散散的内存空间集中起来管理。

链表的出现改变了这个情况。它可以在程序运行时根据实际需要一个个分配堆内存空间，并且用它的指针可以把一系列的空间串联起来，就像一条链子一样。这样一来，我们就能够利用指针对整个链表进行管理了。