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
描述
[列表：]一種使用連結節點序列實現集合的資料結構。
[節點：]列表的一個元素，通常實現為一個物件，其中包含對同一型別另一個物件的引用。
[貨物：]節點中包含的資料項。
[連結：]嵌入在物件中的物件引用。
[泛型資料結構：]一種可以包含任何型別資料的資料結構。
[先決條件：]為了使方法正常工作，必須為真的斷言。
[不變數：]應該始終對物件為真的斷言（除了物件正在被修改時）。
[包裝器方法：]充當呼叫者和輔助函式之間中間人的方法，通常提供比輔助函式更簡潔的介面。