資料結構 老師：李崇明 助教：楊斯竣

學習目標 認識鏈結串列的基本觀念與結構。 了解鏈結串列的基本運算。 知道如何以適當的方式來表示鏈結串列。 認識鏈結串列的應用與相關的演算法。

3.1 鏈結串列 (linked list) 的 基本結構與特性 載運旅客的火車把好幾個車廂一個接一個地連起來，靠火車頭的動力與車廂間的連結力來行駛，這種透過鏈結把相似個體連接起來的結構，就是一種鏈結串列。 火車的車廂一定都按照車廂號碼的順序排列，所以不管你從月台的哪個入口進站，只要知道目前所在的車廂位置，就一定能循序往前或往後找到自己要上的車廂。 列車長查票的時候也要從最前頭的車廂開始，依序到每一個車廂查票，才不會漏掉。

3.1.1 鏈結串列的基本結構 [鏈結串列的形成] [鏈結串列的節點結構] [單向鏈結串列(singly linked list)的定義]

[鏈結串列的形成] 鏈結串列的元素透過鏈結連接在一起，除了頭尾兩個元素以外，每個元素都有之前與之後的兩個相鄰的元素。 帶頭的元素之前沒有元素，之後則連接一個元素，最尾端的元素之前連接了一個元素，之後則沒有元素。

鏈結串列形成的實例

[鏈結串列的節點結構] 鏈結串列中的元素可以用一個節點來表示，節點包括兩個主要的部分 : 資料(data)與鏈結(link)，鏈結儲存的是下一個節點的位址，下一個節點的鏈結則儲存下下一個節點的位址。

[單向鏈結串列(singly linked list) 的定義] 頭節點在結構上看起來跟其他的節點沒有什麼差異，但是前面沒有其他的節點。 尾節點的鏈結是空值(null)，因為沒有下一個節點。

3.1.2 鏈結串列的基本特性 鏈結串列透過鏈結把元素串起來，元素越多則串列越龐大。 雖然串列中的元素有一定的順序，但是我們並沒有像陣列那樣用編號來加以區別。 串列中元素的增加與移除也不必按照特定的順序。

鏈結串列的特性(I)

鏈結串列的特性(II)

鏈結串列的特性(III)

3.2 鏈結串列的基本操作 鏈結串列也可以看成是一種串列，只是節點中多了記載其他節點位址的鏈結，多了鏈結的好處是可以透過鏈結來引用其他節點的資料，或是走訪整個串列。 一般的串列不用鏈結，必須靠陣列索引來存取節點的資料，鏈結串列有鏈結可用，所以有些操作就可以運用鏈結來進行。

3.2.1 頭節點的問題 鏈結串列中頭節點(header node)的使用具有十分特殊的意義，我們在概念上可以把頭節點看成跟其他的節點相同，但是在鏈結串列的實務上，頭節點的處理會跟串列中其他的節點不同，目的在於維持一般節點操作程序的一致性、提高效率。

[解決的辦法] 把頭節點當成特殊的節點來處理，不像其他的節點那樣專門用來儲存同類型的資料，頭節點裡可以記載一些與串列相關的資訊，例如串列中節點的數目。

[對於操作的影響] 在鏈結串列建立的時候馬上加入一個頭節點，格式與其他的串列節點一樣，但是不用來儲存資料，只是為了讓鏈結串列在節點的處理操作上有一致性、提高執行時的效能。

串列節點的插入 (insert) 節點可以插入到頭節點之後、尾節點之後，或是一般節點之後，但是不能插入到頭節點之前，這樣才能維持操作的一致性。下圖顯示如何將節點P插入到Pi之後。

串列節點的刪除 (delete) 規定串列的頭節點不能刪除，其他的節點都可以刪除。下圖顯示如何將節點P從串列中刪除。

3.2.2 基本操作 [鏈結串列的產生] [檢查鏈結串列是否為空的(isEmpty)] [插入節點(insert)] [刪除節點(delete)] [鏈結串列的走訪(traversal)]

[鏈結串列的產生] 鏈結串列是由節點所形成的，必須先產生節點，下面以ListNode類別來定義一個鏈結串列的節點，一個節點包含兩個主要的資料成員，即所儲存的資料(底下的data屬性)、以及指向下一個節點的鏈結(底下的link屬性) 。

[檢查鏈結串列是否為空的(isEmpty)] 簡單地說，只要鏈結串列中沒有任何節點就表示鏈結串列是空的，一個非空的鏈結串列至少要有一個節點。 串列的元素可以新增或刪除，所以有可能碰到串列沒有元素的情況，這時候存在的就是一個空串列。

[插入節點(insert)]

[刪除節點(delete)]

[鏈結串列的走訪(traversal)] 走訪有很多種目的，我們可能會走訪所有的節點，得到串列中節點的數目，代表串列的長度 (length)；假如想知道串列是否有某個數值，也是要透過走訪，檢視串列元素中儲存的資料，這種操作可以稱為找尋(find)。

實作Linked List 使用Java Collections Framework中的Linked List類別實作。 Linked List在Java API架構中的位置： import java.util.*; 宣告Linked List物件 LinkedList <資料型態>物件名 = new LinkedList <資料型態>(); Linked List可以直接輸出 System.out.println(物件名);

插入尾端節點(addLast) 使用addLast方法可直接將元素插入原Linked List尾端 程式碼： 1. 產生新節點(data為元素值，link指向null) 2. 將原linked list最尾端link指向新節點。 程式碼： 物件名.add(元素); 例如：obj.addLast(“Joe”); Joe null John null

插入前端節點(addFirst) 執行步驟 程式碼： 1. 產生新節點(data為元素值，link指向null) 2. 將新節點的link指向原linked list最前端節點。 程式碼： 物件名.add(元素); 例如：obj.addFirst(“Allen”);

插入節點(add) 若無索引值，可將元素插入原Linked List尾端(功能與addLast相同) 1. 產生新節點(data為元素值，link指向null) 2. 將原linked list最尾端link指向新節點。 若有索引值，則可在索引值位置上插入節點 2. 新節點的link指向索引值位置的節點。 3. 索引值的前節點link指向新節點。 程式碼： obj.add(“Martin”); obj.add(1, “Richard”);

刪除尾端節點(removeLast) 刪除linked list中的最後節點 程式碼： 將倒數第2個節點的link改為null。 刪除最後節點(回收空間)。 程式碼： obj.removeLast();

刪除前端節點(removeFirst) 刪除linked list中的最前端節點 程式碼： 將開頭改為第2個節點。 刪除第1個節點(回收空間)。 程式碼： obj.removeFirst();

刪除節點(remove) 給予索引值或元素，刪除該索引值或元素之節點。 程式碼： 將欲刪除節點的前節點，指向下個節點。 刪除節點。(回收空間) 程式碼： obj.remove(“Joe”); obj.remove(1);

取得目前長度(size) 使用size方法取得目前鏈結串列長度 其他Linked List相關方法： obj.size(); 其他Linked List相關方法： http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html

-The End-