資料結構使用Java 第6章 鏈結串列(Linked List).

Presentation on theme: "資料結構使用Java 第6章 鏈結串列(Linked List)."— Presentation transcript:

1 資料結構使用Java 第6章 鏈結串列(Linked List)

2 課程內容 鏈結串列存在的原因 鏈結串列的基本結構與特性 單向鏈結串列 實作鏈結串列 串列與鏈結串列
addLast, addFirst, add removeLast, removeFirst, remove get, set, size

3 串列與鏈結串列 串列的缺點： 改良─鏈結串列(Linked List) 串列的大小受到陣列的限制。
插入或刪除一個元素，其後面所有元素都要修正。 改良─鏈結串列(Linked List) 鏈結串列的大小可以無限制擴增 插入與刪除元素動作小，不會影響其他元素。

4 鏈結串列 (linked list) 的 基本結構與特性
這種透過鏈結把相似個體連接起來的結構，就是 一種鏈結串列。例如：火車。 鏈結串列的元素透過鏈結連接在一起，除了頭尾 兩個元素以外，每個元素都有之前與之後的兩個 相鄰的元素。

5 鏈結串列形成的實例

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

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

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

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

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

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

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

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

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

15 取得(get)、設定(set)元素值 使用get可以取得某位置的元素值 使用set可以取得某位置的元素值 obj.get(3);
obj.set(3, 元素值);

16 取得目前長度(size) 使用size方法取得目前鏈結串列長度 其他Linked List相關方法：
obj.size(); 其他Linked List相關方法： a/util/LinkedList.html