Question

当程序中要求存储一系列元素时，首先就会想到使用数组。使用数组有一个特别的地方，就是在定义数组时需要指定它的长度，因此，数组非常适合在明确知道数据元素个数的情况下使用。但在数据元素个数未知的情况下，就需要编程人员在数组长度和内存大小之间作出抉择了。如果数组的长度小了，就不够存储数据元素，如果数组的长度大了，就会造成内存资源的浪费，很难找到一个准确、恰好的点。那有没有能完美解决这个问题的办法呢？有的，就是本节的主题——链表。

链表由任意多的节点构成，其中节点个数为 0 的链表被称之为空链表，要注意的是，链表的各节点在内存中并不一定是连续存储的，也许会分散在内存的不同地方。链表的每个节点又分为数据域和指针域部分，数据域存储着相关的数据，而指针域则存储着另外一个节点的内存地址。因此，凭借着节点的指针域中的指针，可以将一系列的节点给串起来，例如通过当前节点中的指针，可以找到下一个节点，而通过下一个节点的指针，又可以找到下下一个节点，以此类推。链表是不是非常像现实中的一列火车？如图 8.1 所示，链表中的节点就如同火车中的车厢，数据域中的数据就如同车厢中的人或货物，而指针域中的指针就如同车厢间的挂钩。

图 8.1　火车

链表中的节点和火车的车厢一样，是一个连着一个的，通常将当前节点的前一个或上一个节点称为它的前驱节点，将后一个或下一个节点称之为它的后继节点。链表中的第一个节点被称为头节点，最后一个节点被称为尾节点。在链表中，头节点是没有前驱的节点，尾节点是没有后继的节点，其他的所有节点都称为中间节点，中间节点都会拥有一个前驱节点和一个后继节点。根据链表中节点的访问方式和遍历方向的不同，可以将链表分为单向链表和双向链表。