1.2 链表

1.2.1 链表的基本概念

链表也是一种常用的线性数据结构，与数组不同的是，链表的存储空间并不连续，它是用一组地址任意的存储单元来存放数据的，也就是将存储单元分散在内存的各个地址上。

这些地址分散的存储单元叫作链表的节点，链表就是由一个个链表节点连结而成的。那么这些地址分散的节点是如何关联到一起的呢？每个节点中都包含一个叫作“指针域”的成员，指针域中存储了下一个节点的内存地址，这样就可以连接后继节点。

每个链表都会有“链表头”，通常是一个指针（对于Java而言，它是链表节点对象的引用），用来存放链表中第1个节点的地址。同时，链表中最后一个节点的指针域通常会置为空（null），用来表示该节点是链表的最后一个节点，没有后继节点。

图1-16为链表在内存中的结构示意，通过这个图我们可以对链表有更加直观的认识。

图1-16 链表的结构示意

从图1-16中可以看到链表具有以下特征。

链表在逻辑上是连续的，而在物理上并不一定连续，链表节点可能分散在内存的各个地址上。

（1）每个链表节点中都必须包含指针域，用来存放下一个节点的内存地址，数据域则用来存放节点的数据元素。这里需要注意，数据域可以是一个也可以是多个，由具体的需求而定。数据域的类型可以是任意类型（图1-16中是字符类型），而指针域的类型必须是定义的链表节点类型，或链表节点指针类型。

（2）只要获取了链表头（head）就可以通过指针遍历整个链表。以图1-16为例，获取了链表头就可以知道第1个节点的内存地址1249，继而访问到第1个节点中的数据A；然后通过第1个节点中的指针域1356可以访问到第2个节点中的数据B。以此类推，直到访问到最后一个节点（指针域为null）。所以获取链表头非常重要。