第1章 链表

链表作为最基本的数据结构，它不仅在实际应用中有着非常重要的作用，而且也是程序员面试、笔试中必考的内容。具体而言，它的存储特点为：可以用任意一组存储单元来存储单链表中的数据元素（存储单元可以是不连续的），而且除了存储每个数据元素ai外，还必须存储指示其直接后继元素的信息。这两部分信息组成的数据元素ai 的存储映像称为结点。N个结点链在一块被称为链表，当结点只包含其后继结点的信息的链表就被称为单链表，而链表的第一个结点通常被称为头结点。

对于单链表，又可以将其分为有头结点的单链表和无头结点的单链表，如下图所示。

在单链表的开始结点之前附设一个类型相同的结点，称之为头结点，头结点的数据域可以不存储任何信息（也可以存放如线性表的长度等附加信息），头结点的指针域存储指向开始结点的指针（即第一个元素结点的存储位置）。需要注意的是，在Java中没有指针的概念，而类似指针的功能都是通过引用来实现的，为了便于理解，我们仍然使用指针（可以认为引用与指针是类似的）来进行描述，而在实现的代码中，都是通过引用来建立结点之间的关系。

具体而言，头结点的作用主要有以下两点：

1）对于带头结点的链表，当在链表的任何结点之前插入新结点或删除链表中任何结点时，所要做的都是修改前一个结点的指针域，因为任何结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前面插入结点或删除该结点时操作会复杂些，需要进行特殊的处理。

2）对于带头结点的链表，链表的头指针是指向头结点的非空指针，因此，对空链表与非空链表的处理是一样的。

由于头结点有诸多的优点，因此，本章中所介绍的算法都使用了带头结点的单链表。

如下是一个单链表数据结构的定义示例：