第3章 链表
链表可能是程序员会建立的最简单的数据结构。然而，用来构建它们所需用到的某些概念也会被用来构建这本书里描述的最复杂的数据结构。要使用一个链表，除了了解查找，插入和删除单元格的方法以外，还需要了解单元格和链接。可以使用这些相同的概念来构建复杂的网络、易被混淆的树和平衡树。
本章说明了为使用链表所需要掌握的方法。后面的章节中（特别是第4章、第5章、第8章和第10～14章）会重温这些方法。
3.1 基本概念
链表是由通常被称为单元格的对象构建而成。单元格类包含链表必须存储的数据和到另一个单元格的链接。该链接是一个简单的引用或是指到另一个单元格类对象的指针。通常单元格的指针域被称为Next。
例如，下面的代码显示了在C＃中的整数单元格（IntegerCell）类的定义。该单元格包含一个整数值和一个指向链表中下一个整数单元格对象的指针：
链表通常用图来表示，用小方格代表单元格并用箭头代表链接。
本书用含有X的小方格来代表一个没有指向单元格的链接。（在编程语言中，对应的链接指针没有值、或者是空指针、或者其他一些特定语言的值，表示该指针没有指向任何内容。）
除了链表本身，一个程序需要一个指向链表的变量，这样便于代码能够找到该链表。往往这个变量被命名为top，以表明它表示该链表的顶端。top变量可以是一个单元格类的变量，也可以是一个指向链表第一个单元的指针。
图3-1显示了含有数字31、72、47和9的两个链表。在靠上面的那个链表里，程序里有一个称为top的变量，它是向该链表第一个单元格的指针。在靠下面的链表里，程序里的top变量是该链表中的第一个单元格。这两个链表都以一个包含X的小方格结尾，这个小方格表示一个空指针。
如果数据中的项会随着时间变化而增加或减少时，链表是一种很好的存储方式。若要添加一个新的单元格，只需要在链表的开头或结尾添加该单元格。与此相反，一个数组的大小是固定的，所以很难扩大数组来实现添加更多的项。
以下各节将介绍一些可以用来操纵链表的算法。其中许多算法是通过展示链表在某操作被执行前和执行后的状态来进行描述说明的。