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所示。