Java/链表之道
reference embedded reference reference!embedded node cargo
在上一章中，我们看到对象的实例变量可以是数组，并且我提到它们也可以是对象。
其中一个比较有趣的情况是，一个对象可以包含对同一类型另一个对象的引用。有一种常见的数据结构，即列表，利用了此特性。
列表由节点组成，其中每个节点都包含对列表中下一个节点的引用。此外，每个节点通常还包含一个称为货物的单元数据。在我们的第一个示例中，货物将是一个整数，但稍后我们将编写一个可以包含任何类型对象的通用列表。
generic data structure data structure!generic
Node class class!Node
像往常一样，当我们编写一个新类时，我们将从实例变量、一个或两个构造函数和 toString 开始，以便我们可以测试创建和显示新类型的基本机制。
verbatim public class Node
int cargo; Node next;
public Node ()
cargo = 0;
next = null;
public Node (int cargo, Node next)
this.cargo = cargo;
this.next = next;
public String toString ()
return cargo + "";
verbatim
实例变量的声明自然遵循规范，其余部分则机械地遵循实例变量。表达式 cargo + "" 是一种笨拙但简洁的将整数转换为字符串的方法。
要测试到目前为止的实现，我们将在 main 中添加如下内容
verbatim
Node node = new Node (1, null); System.out.println (node);
verbatim
结果很简单
verbatim 1 verbatim
为了使其变得有趣，我们需要一个包含多个节点的列表！
verbatim
Node node1 = new Node (1, null); Node node2 = new Node (2, null); Node node3 = new Node (3, null);
verbatim
此代码创建了三个节点，但我们还没有列表，因为这些节点没有链接。状态图如下所示
figure=figs/list1.eps
要链接这些节点，我们必须使第一个节点引用第二个节点，第二个节点引用第三个节点。
verbatim
node1.next = node2; node2.next = node3; node3.next = null;
verbatim
第三个节点的引用为 null，这表示它是列表的末尾。现在状态图如下所示
figure=figs/list2.eps
现在我们知道如何创建节点并将它们链接到列表中。此时可能不太清楚的是为什么。
collection
使列表变得有用的原因是它们是一种将多个对象组合成单个实体的方法，有时称为集合。在示例中，列表的第一个节点充当对整个列表的引用。
list!printing list!as parameter
如果要将列表作为参数传递，我们只需要传递对第一个节点的引用即可。例如，方法 printList 以单个节点作为参数。从列表的头部开始，它打印每个节点，直到到达末尾（由 null 引用指示）。
verbatim
public static void printList (Node list)
Node node = list;
while (node != null)
System.out.print (node);
node = node.next;
System.out.println ();
verbatim
要调用此方法，我们只需要传递对第一个节点的引用即可
verbatim
printList (node1);
verbatim
在 printList 内部，我们对列表的第一个节点有一个引用，但是没有变量引用其他节点。我们必须使用每个节点的 next 值来获取下一个节点。
此图显示了 list 的值以及 node 采用的值
figure=figs/list3.eps
这种遍历列表的方式称为遍历，就像遍历数组元素的类似模式一样。通常使用像 node 这样的循环变量依次引用列表中的每个节点。
loop variable list!traversal traverse
此方法的输出为
verbatim 123 verbatim
按照惯例，列表用括号括起来，元素之间用逗号分隔，例如 (1, 2, 3)。作为练习，修改 printList 以使其生成此格式的输出。
作为另一个练习，使用 for 循环而不是 while 循环重写 printList。
list!traverse recursively traverse
递归和列表就像蚕豆和美味的基安蒂一样相配。例如，以下是如何反向打印列表的递归算法
fava beans Chianti
enumerate
将列表分成两部分：第一个节点（称为头部）和其余部分（称为尾部）。
反向打印尾部。
打印头部。
enumerate
当然，步骤 2（递归调用）假设我们有办法反向打印列表。但是，如果我们假设递归调用有效——信念的飞跃——那么我们可以说服自己此算法有效。
leap of faith list!printing backwards
我们只需要一个基本情况，以及证明对于任何列表，我们最终都会到达基本情况的方法。基本情况的自然选择是只有一个元素的列表，但更好的选择是空列表，由 null 表示。
verbatim
public static void printBackward (Node list)
if (list == null) return;
Node head = list;
Node tail = list.next;
printBackward (tail);
System.out.print (head);
verbatim
第一行通过什么都不做来处理基本情况。接下来的两行将列表分成头部和尾部。最后两行打印列表。
我们调用此方法的方式与调用 printList 完全相同
verbatim
printBackward (node1);
verbatim
结果是一个反向列表。
我们能否证明此方法始终会终止？换句话说，它是否始终会到达基本情况？事实上，答案是否定的。有一些列表会导致此方法崩溃。
infinite list list!infinite loop!in list list!loop
没有什么可以阻止一个节点引用列表中较早的节点，包括自身。例如，下图显示了一个包含两个节点的列表，其中一个节点引用自身。
figure=figs/list4.eps
如果在此列表上调用 printList，它将永远循环。如果我们调用 printBackward，它将无限递归。这种行为使无限列表难以处理。
尽管如此，它们偶尔还是很有用的。例如，我们可以将数字表示为数字列表，并使用无限列表表示循环小数。
无论如何，我们无法证明 printList 和 printBackward 会终止，这一点是有问题的。我们所能做的最好的事情是假设陈述，“如果列表不包含循环，则这些方法将终止。” 这种类型的声明称为先决条件。它对其中一个参数施加约束，并在满足约束条件时描述方法的行为。我们很快就会看到更多示例。
precondition
ambiguity!fundamental theorem theorem!fundamental ambiguity
printBackward 中有一部分可能引起了注意
verbatim
Node head = list;
Node tail = list.next;
verbatim
在第一次赋值后，head 和 list 具有相同的类型和相同的值。那么为什么我要创建一个新的变量呢？
原因是这两个变量扮演着不同的角色。我们将 head 视为对单个节点的引用，并将 list 视为对列表第一个节点的引用。这些“角色”不是程序的一部分；它们存在于程序员的脑海中。
variable!roles role!variable
第二个赋值创建了对列表中第二个节点的新引用，但在这种情况下，我们将其视为一个列表。因此，即使 head 和 tail 具有相同的类型，它们也扮演着不同的角色。
这种模糊性很有用，但它可能使包含列表的程序难以阅读。我经常使用像 node 和 list 这样的变量名来记录我打算如何使用一个变量，有时我会创建额外的变量来消除歧义。
我本可以在不使用 head 和 tail 的情况下编写 printBackward，但我认为这样会更难理解。
verbatim
public static void printBackward (Node list)
if (list == null) return;
printBackward (list.next);
System.out.print (list);
verbatim
查看这两个函数调用，我们必须记住，printBackward 将其参数视为一个列表，而 print 将其参数视为单个对象。
始终牢记基本模糊性定理。
引用 指向节点的变量可能会将节点视为单个对象或列表中的第一个节点。引用
method!object node!object method
您可能想知道为什么 printList 和 printBackward 是类方法。我声称，任何可以用类方法完成的事情也可以用对象方法完成；这仅仅是一个哪个形式更简洁的问题。
在这种情况下，选择类方法有一个合理的理由。将 null 作为参数发送到类方法是合法的，但对 null 对象调用对象方法是不合法的。
逐字 Node node = null; printList (node); // 合法 node.printList (); // NullPointerException 逐字
此限制使得以简洁的面向对象风格编写列表操作代码变得很麻烦。不过，稍后我们将看到一种解决此问题的方法。
list!modifying modifying lists
显然，修改列表的一种方法是更改其中一个节点的货物，但更有趣的操作是添加、删除或重新排序节点的操作。
例如，我们将编写一个方法来删除列表中的第二个节点并返回对已删除节点的引用。
verbatim
public static Node removeSecond (Node list)
Node first = list;
Node second = list.next;
// make the first node refer to the third
first.next = second.next;
// separate the second node from the rest of the list
second.next = null;
return second;
verbatim
同样，我使用临时变量来使代码更易读。以下是使用方法。
verbatim
printList (node1);
Node removed = removeSecond (node1);
printList (removed);
printList (node1);
verbatim
输出是
逐字 (1, 2, 3) 原始列表 (2) 已删除的节点 (1, 3) 修改后的列表 逐字
这是一个状态图，显示了此操作的效果。
图=figs/list5.eps
如果我们调用此方法并传递仅包含一个元素（单例）的列表会发生什么？如果我们传递空列表作为参数会发生什么？此方法是否有先决条件？
singleton
wrapper methods method!wrapper helper method method!helper
对于某些列表操作，将工作划分为两个方法很有用。例如，要以常规列表格式（3, 2, 1）反向打印列表，我们可以使用 printBackwards 方法打印 3、2，但我们需要一个单独的方法来打印括号和第一个节点。我们将其称为 printBackwardNicely。
verbatim
public static void printBackwardNicely (Node list)
System.out.print ("(");
if (list != null)
Node head = list;
Node tail = list.next;
printBackward (tail);
System.out.print (head);
System.out.println (")");
verbatim
同样，最好检查像这样的方法，以查看它们是否适用于空列表或单例等特殊情况。
singleton
在程序的其他地方，当我们使用此方法时，我们将直接调用 printBackwardNicely，它将代表我们调用 printBackward。从这个意义上说，printBackwardNicely 充当包装器，它使用 printBackward 作为辅助函数。
LinkedList class!LinkedList
我们一直以来实现列表的方式存在一些细微的问题。为了颠倒因果关系，我将首先提出另一种实现，然后解释它解决了哪些问题。
首先，我们将创建一个名为 LinkedList 的新类。它的实例变量是一个包含列表长度的整数和对列表中第一个节点的引用。LinkedList 对象用作操作 Node 对象列表的句柄。
逐字 public class LinkedList
int length; Node head;
public LinkedList ()
length = 0;
head = null;
verbatim
LinkedList 类的一个好处是，它为我们提供了一个放置像 printBackwardNicely 这样的包装函数的自然位置，我们可以将其设为 LinkedList 类中的对象方法。
verbatim
public void printBackward ()
System.out.print ("(");
if (head != null)
Node tail = head.next;
Node.printBackward (tail);
System.out.print (head);
System.out.println (")");
verbatim
为了使事情变得混乱，我将 printBackwardNicely 重命名了。现在有两个名为 printBackward 的方法：一个在 Node 类中（辅助函数），另一个在 LinkedList 类中（包装器）。为了使包装器能够调用辅助函数，它必须显式地识别类（Node.printBackward）。
因此，LinkedList 类的好处之一是它提供了一个放置包装函数的好地方。另一个好处是它使添加或删除列表的第一个元素变得更容易。例如，addFirst 是 LinkedList 的对象方法；它将一个 int 作为参数，并将其放在列表的开头。
verbatim
public void addFirst (int i)
Node node = new Node (i, head);
head = node;
length++;
verbatim
与往常一样，要检查这样的代码，最好考虑特殊情况。例如，如果列表最初为空会发生什么？
invariant object invariant list!well-formed
有些列表是“格式良好的”；有些则不是。例如，如果列表包含循环，它将导致我们的许多方法崩溃，因此我们可能希望要求列表不包含循环。另一个要求是 LinkedList 对象中的 length 值应等于列表中节点的实际数量。
像这样的要求称为不变量，因为理想情况下，它们应该始终对每个对象都为真。为对象指定不变量是一种有用的编程实践，因为它可以更容易地证明代码的正确性、检查数据结构的完整性和检测错误。
关于不变量有时会令人困惑的一件事是，有时它们会被违反。例如，在 addFirst 的中间，在添加节点后但增加 length 之前，不变量被违反了。这种违反是可以接受的；事实上，在不至少暂时违反不变量的情况下，修改对象通常是不可能的。通常的要求是，每个违反不变量的方法都必须恢复不变量。
如果存在任何不变量被违反的代码段，那么注释必须明确说明这一点，以便不会执行依赖于不变量的操作。
documentation
list node cargo link generic data structure precondition invariant wrapper
描述
[列表：]一种使用链接节点序列实现集合的数据结构。
[节点：]列表的一个元素，通常实现为一个对象，其中包含对同一类型另一个对象的引用。
[货物：]节点中包含的数据项。
[链接：]嵌入在对象中的对象引用。
[泛型数据结构：]一种可以包含任何类型数据的数据结构。
[先决条件：]为了使方法正常工作，必须为真的断言。
[不变量：]应该始终对对象为真的断言（除了对象正在被修改时）。
[包装器方法：]充当调用者和辅助函数之间中间人的方法，通常提供比辅助函数更简洁的接口。