2.4　链表结构

顺序表结构的存储方式非常容易理解，操作也十分方便。但是顺序表结构有如下缺点：

・在插入或者删除结点时，往往需要移动大量的数据。

・如果表比较大，有时比较难分配足够的连续存储空间，往往导致内存分配失败，而无法存储。

为了克服上述顺序表结构的缺点，可以采用链表结构。链表结构是一种动态存储分配的结构形式，可以根据需要动态申请所需的内存单元。

2.4.1　什么是链表结构

典型的链表结构，如图2-3所示。链表中每个结点都应包括如下内容：

・数据部分，保存的是该结点的实际数据。

・地址部分，保存的是下一个结点的地址。

链表结构就是由许多这种结点构成的。在进行链表操作时，首先需要定义一个“头引用”变量（一般以head表示），该引用变量指向链表结构的第一个结点，第一个结点的地址部分又指向第二个结点……直到最后一个结点。最后一个结点不再指向其他结点，称为“表尾”，一般在表尾的地址部分放一个空地址null，链表到此结束。从链表结构图可以看出，整个存储过程十分类似于一条长链，因此形象地称之为链表结构，或者链式结构。

由于采用了引用来指示下一个数据的地址。因此在链表结构中，逻辑上相邻的结点在内存中并不一定相邻，逻辑相邻关系通过地址部分的引用变量来实现。

链表结构带来的最大好处便是结点之间不要求连续存放，因此在保存大量数据时，不需要分配一块连续的存储空间。用户可以用new函数动态分配结点的存储空间，当删除某个结点时，给该节点赋值null，释放其占用的内存空间。

当然，链表结构也有缺点，那就是浪费存储空间。因此，对于每个节点数据，都要额外保存一个引用变量。但是，在某些场合，链表结构所带来的好处还是大于其缺点的。

对于链表的访问只能从表头逐个查找，即通过head头引用找到第一个结点，再从第一个结点找到第二个结点……这样逐个比较一直到找到需要的结点为止，而不能像顺序表那样进行随机访问。

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。链表结构还可以细分为如下几类。

・单链表：同上面的链式结构一样，每个结点中只包含一个引用。

・双向链表：若每个结点包含两个引用，一个指向下一个结点，另一个指向上一个结点，这就是双向链表。

・单循环链表：在单链表中，将终端结点的引用域null改为指向表头结点或开始结点即可构成单循环链表。

・多重链的循环链表：如果将表中结点链在多个环上，将构成多重链的循环链表。接下来，将分析如何在Java语言中建立链表，并完成链表结构的基本运算。

2.4.2　准备数据

有了前面的理论知识后，下面就开始链表结构的程序设计。首先需要准备数据，也就是准备在链表操作中需要用到的变量及类等。示例代码如下：

上述代码定义了链表数据元素的类DATA2及链表的类CLType。结点的具体数据保存在一个类DATA2中，而引用nextNode用来指向下一个结点。

其实，可以认为该链表是一个班级学生的记录，和上面顺序表所完成的工作类似。其中，key为学号，name为学生的名称，age为年龄。

2.4.3　追加结点

追加结点即在链表末尾增加一个结点。表尾结点的地址部分原来保存的是空地址null，此时需将其设置为新增结点的地址（即原表尾结点指向新增结点），然后将新增结点的地址部分设置为空地址null，即新增结点成为表尾。

由于一般情况下，链表只有一个头引用head，要在末尾添加结点就需要从头引用head开始逐个检查，直到找到最后一个结点（即表尾）。

典型的追加结点的过程，如图2-4所示。追加结点的操作步骤如下：

（1）首先分配内存空间，保存新增的结点。

（2）从头引用head开始逐个检查，直到找到最后一个结点（即表尾）。

（3）将表尾结点的地址部分设置为新增结点的地址。

（4）将新增结点的地址部分设置为空地址null，即新增结点成为表尾。

在链表结构中追加结点的代码示例如下：

在上述代码中，输入参数head为链表头引用，输入参数nodeData为结点保存的数据。程序中，使用new关键字申请保存结点数据的内存空间，如果分配内存成功，node中将保存指向该内存区域的引用。然后，将传入的nodeData保存到申请的内存区域，并设置该结点指向下一结点的引用值为null。

2.4.4　插入头结点

插入头结点即在链表首部添加结点的过程。插入头结点的过程，如图2-5所示。插入头结点的步骤如下：

（1）分配内存空间，保存新增的结点。

（2）使新增结点指向头引用head所指向的结点。

（3）使头引用head指向新增结点。

插入头结点的代码示例如下：

在上述代码中，输入参数head为链表头引用，输入参数nodeData为结点保存的数据。程序中首先使用new关键字申请保存结点数据的内存空间，如果分配内存成功，node中将保存指向该内存区域的引用。然后，将传入的nodeData保存到申请的内存区域，并使新增结点指向头引用head所指向的结点，然后设置头引用head重新指向新增结点。

2.4.5　查找结点

查找结点就是在链表结构中查找需要的元素。对于链表结构来说，一般可通过关键字进行查询。查找结点的示例代码如下：

在上述代码中，输入参数head为链表头引用，输入参数key是用来在链表中进行查找结点的关键字。程序中，首先从链表头引用开始，对结点进行逐个比较，直到查找到。找到关键字相同的结点后，返回该结点的引用，方便调用程序处理。

2.4.6　插入结点

插入结点就是在链表中间部分的指定位置增加一个结点。插入结点的过程，如图2-6所示。插入结点的操作步骤如下：

（1）分配内存空间，保存新增的结点。

（2）找到要插入的逻辑位置，也就是位于哪两个结点之间。

（3）修改插入位置结点的引用，使其指向新增结点，而使新增结点指向原插入位置所指向的结点。

在链表结构中插入结点的代码示例如下：

在上述代码中，输入参数head为链表头引用，输入参数findkey是用来在链表中进行查找的结点关键字，找到该结点后将在该结点后面添加结点数据，nodeData为新增结点的数据。程序中首先使用new关键字申请保存结点数据的内存空间，然后调用方法ChainListFind查找指定关键字的结点，接着执行插入操作。

2.4.7　删除结点

删除结点就是将链表中的某个结点数据删除。删除结点的过程，如图2-7所示。删除结点的操作步骤如下：

（1）查找需要删除的结点。

（2）使前一结点指向当前结点的下一结点。

（3）删除结点。

在链表结构中删除结点的代码示例如下：

在上述代码中，输入参数head为链表头引用，输入参数key表示一个关键字，是链表中需要删除结点的关键字。程序中，通过一个循环，按关键字在整个链表中查找要删除的结点。如果找到被删除结点，则设置上一结点（node引用所指结点）指向当前结点（h引用所指结点）的下一结点，即可完成链表中结点的逻辑删除。但是，此时被删除结点仍然保存在内存中，接着执行赋值null操作，用来释放被删除节点所占用的内存空间。

2.4.8　计算链表长度

计算链表长度即统计链表结构中结点的数量。在顺序表中比较方便，但是在这里，链表结构在物理上并不是连续存储的，因此，计算链表长度稍复杂些，需要遍历整个链表来对结点数量进行累加。

计算链表长度的代码示例如下：

在上述代码中，输入参数head表示链表的头引用。程序中通过while循环来遍历整个链表，从而累加结点数量并返回。

2.4.9　显示所有结点

显示所有结点数据并不是一个数据结构基本的运算，因为其可以简单地逐个引用结点来实现。不过为了方便，这里将其单独列为一个方法。代码示例如下：

在上述代码中，输入参数head表示链表的头引用。程序中通过while循环来遍历整个链表，从而输出各个结点数据。

2.4.10　链表操作实例

学习了前面的链表的基本运算之后，便可以轻松地完成对链表的各种操作。下面给出一个完整的例子，来演示链表的创建、插入结点、查找结点、删除结点等操作。代码示例如下：

【程序2-2】

在上述代码中，main（）主方法首先初始化链表，然后循环添加数据结点，当输入全部为0时则退出结点添加的进程。接下来显示所有的结点数据，然后分别演示了插入结点、删除结点和查找结点等操作。该程序执行结果，如图2-8所示。