Download presentation
Presentation is loading. Please wait.
1
資料結構 老師：李崇明 助教：楊斯竣
2
學習目標 認識鏈結串列的基本觀念與結構。 了解鏈結串列的基本運算。 知道如何以適當的方式來表示鏈結串列。 認識鏈結串列的應用與相關的演算法。
3
3.1 鏈結串列 (linked list) 的 基本結構與特性
載運旅客的火車把好幾個車廂一個接一個地連起來，靠火車頭的動力與車廂間的連結力來行駛，這種透過鏈結把相似個體連接起來的結構，就是一種鏈結串列。 火車的車廂一定都按照車廂號碼的順序排列，所以不管你從月台的哪個入口進站，只要知道目前所在的車廂位置，就一定能循序往前或往後找到自己要上的車廂。 列車長查票的時候也要從最前頭的車廂開始，依序到每一個車廂查票，才不會漏掉。
4
3.1.1 鏈結串列的基本結構 [鏈結串列的形成] [鏈結串列的節點結構] [單向鏈結串列(singly linked list)的定義]
![3.1.1 鏈結串列的基本結構 [鏈結串列的形成] [鏈結串列的節點結構] [單向鏈結串列(singly linked list)的定義]](http://slidesplayer.com/slide/16593575/96/images/4/3.1.1+%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E5%9F%BA%E6%9C%AC%E7%B5%90%E6%A7%8B+%5B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E5%BD%A2%E6%88%90%5D+%5B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E7%AF%80%E9%BB%9E%E7%B5%90%E6%A7%8B%5D+%5B%E5%96%AE%E5%90%91%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%28singly+linked+list%29%E7%9A%84%E5%AE%9A%E7%BE%A9%5D.jpg "3.1.1 鏈結串列的基本結構 [鏈結串列的形成] [鏈結串列的節點結構] [單向鏈結串列(singly linked list)的定義]")
5
[鏈結串列的形成] 鏈結串列的元素透過鏈結連接在一起，除了頭尾兩個元素以外，每個元素都有之前與之後的兩個相鄰的元素。
帶頭的元素之前沒有元素，之後則連接一個元素，最尾端的元素之前連接了一個元素，之後則沒有元素。
![[鏈結串列的形成] 鏈結串列的元素透過鏈結連接在一起，除了頭尾兩個元素以外，每個元素都有之前與之後的兩個相鄰的元素。](http://slidesplayer.com/slide/16593575/96/images/5/%5B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E5%BD%A2%E6%88%90%5D+%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E5%85%83%E7%B4%A0%E9%80%8F%E9%81%8E%E9%8F%88%E7%B5%90%E9%80%A3%E6%8E%A5%E5%9C%A8%E4%B8%80%E8%B5%B7%EF%BC%8C%E9%99%A4%E4%BA%86%E9%A0%AD%E5%B0%BE%E5%85%A9%E5%80%8B%E5%85%83%E7%B4%A0%E4%BB%A5%E5%A4%96%EF%BC%8C%E6%AF%8F%E5%80%8B%E5%85%83%E7%B4%A0%E9%83%BD%E6%9C%89%E4%B9%8B%E5%89%8D%E8%88%87%E4%B9%8B%E5%BE%8C%E7%9A%84%E5%85%A9%E5%80%8B%E7%9B%B8%E9%84%B0%E7%9A%84%E5%85%83%E7%B4%A0%E3%80%82.jpg "帶頭的元素之前沒有元素，之後則連接一個元素，最尾端的元素之前連接了一個元素，之後則沒有元素。")
6
鏈結串列形成的實例
7
[鏈結串列的節點結構] 鏈結串列中的元素可以用一個節點來表示，節點包括兩個主要的部分 : 資料(data)與鏈結(link)，鏈結儲存的是下一個節點的位址，下一個節點的鏈結則儲存下下一個節點的位址。
![[鏈結串列的節點結構] 鏈結串列中的元素可以用一個節點來表示，節點包括兩個主要的部分 : 資料(data)與鏈結(link)，鏈結儲存的是下一個節點的位址，下一個節點的鏈結則儲存下下一個節點的位址。](http://slidesplayer.com/slide/16593575/96/images/7/%5B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E7%AF%80%E9%BB%9E%E7%B5%90%E6%A7%8B%5D+%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E4%B8%AD%E7%9A%84%E5%85%83%E7%B4%A0%E5%8F%AF%E4%BB%A5%E7%94%A8%E4%B8%80%E5%80%8B%E7%AF%80%E9%BB%9E%E4%BE%86%E8%A1%A8%E7%A4%BA%EF%BC%8C%E7%AF%80%E9%BB%9E%E5%8C%85%E6%8B%AC%E5%85%A9%E5%80%8B%E4%B8%BB%E8%A6%81%E7%9A%84%E9%83%A8%E5%88%86+%3A+%E8%B3%87%E6%96%99%28data%29%E8%88%87%E9%8F%88%E7%B5%90%28link%29%EF%BC%8C%E9%8F%88%E7%B5%90%E5%84%B2%E5%AD%98%E7%9A%84%E6%98%AF%E4%B8%8B%E4%B8%80%E5%80%8B%E7%AF%80%E9%BB%9E%E7%9A%84%E4%BD%8D%E5%9D%80%EF%BC%8C%E4%B8%8B%E4%B8%80%E5%80%8B%E7%AF%80%E9%BB%9E%E7%9A%84%E9%8F%88%E7%B5%90%E5%89%87%E5%84%B2%E5%AD%98%E4%B8%8B%E4%B8%8B%E4%B8%80%E5%80%8B%E7%AF%80%E9%BB%9E%E7%9A%84%E4%BD%8D%E5%9D%80%E3%80%82.jpg "[鏈結串列的節點結構] 鏈結串列中的元素可以用一個節點來表示，節點包括兩個主要的部分 : 資料(data)與鏈結(link)，鏈結儲存的是下一個節點的位址，下一個節點的鏈結則儲存下下一個節點的位址。")
8
[單向鏈結串列(singly linked list) 的定義]
頭節點在結構上看起來跟其他的節點沒有什麼差異，但是前面沒有其他的節點。 尾節點的鏈結是空值(null)，因為沒有下一個節點。
![[單向鏈結串列(singly linked list) 的定義]](http://slidesplayer.com/slide/16593575/96/images/8/%5B%E5%96%AE%E5%90%91%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%28singly+linked+list%29+%E7%9A%84%E5%AE%9A%E7%BE%A9%5D.jpg "頭節點在結構上看起來跟其他的節點沒有什麼差異，但是前面沒有其他的節點。 尾節點的鏈結是空值(null)，因為沒有下一個節點。")
9
3.1.2 鏈結串列的基本特性 鏈結串列透過鏈結把元素串起來，元素越多則串列越龐大。
雖然串列中的元素有一定的順序，但是我們並沒有像陣列那樣用編號來加以區別。 串列中元素的增加與移除也不必按照特定的順序。
10
鏈結串列的特性(I)
11
鏈結串列的特性(II)
12
鏈結串列的特性(III)
13
3.2 鏈結串列的基本操作 鏈結串列也可以看成是一種串列，只是節點中多了記載其他節點位址的鏈結，多了鏈結的好處是可以透過鏈結來引用其他節點的資料，或是走訪整個串列。 一般的串列不用鏈結，必須靠陣列索引來存取節點的資料，鏈結串列有鏈結可用，所以有些操作就可以運用鏈結來進行。
14
3.2.1 頭節點的問題 鏈結串列中頭節點(header node)的使用具有十分特殊的意義，我們在概念上可以把頭節點看成跟其他的節點相同，但是在鏈結串列的實務上，頭節點的處理會跟串列中其他的節點不同，目的在於維持一般節點操作程序的一致性、提高效率。
15
[解決的辦法] 把頭節點當成特殊的節點來處理，不像其他的節點那樣專門用來儲存同類型的資料，頭節點裡可以記載一些與串列相關的資訊，例如串列中節點的數目。
![[解決的辦法] 把頭節點當成特殊的節點來處理，不像其他的節點那樣專門用來儲存同類型的資料，頭節點裡可以記載一些與串列相關的資訊，例如串列中節點的數目。](http://slidesplayer.com/slide/16593575/96/images/15/%5B%E8%A7%A3%E6%B1%BA%E7%9A%84%E8%BE%A6%E6%B3%95%5D+%E6%8A%8A%E9%A0%AD%E7%AF%80%E9%BB%9E%E7%95%B6%E6%88%90%E7%89%B9%E6%AE%8A%E7%9A%84%E7%AF%80%E9%BB%9E%E4%BE%86%E8%99%95%E7%90%86%EF%BC%8C%E4%B8%8D%E5%83%8F%E5%85%B6%E4%BB%96%E7%9A%84%E7%AF%80%E9%BB%9E%E9%82%A3%E6%A8%A3%E5%B0%88%E9%96%80%E7%94%A8%E4%BE%86%E5%84%B2%E5%AD%98%E5%90%8C%E9%A1%9E%E5%9E%8B%E7%9A%84%E8%B3%87%E6%96%99%EF%BC%8C%E9%A0%AD%E7%AF%80%E9%BB%9E%E8%A3%A1%E5%8F%AF%E4%BB%A5%E8%A8%98%E8%BC%89%E4%B8%80%E4%BA%9B%E8%88%87%E4%B8%B2%E5%88%97%E7%9B%B8%E9%97%9C%E7%9A%84%E8%B3%87%E8%A8%8A%EF%BC%8C%E4%BE%8B%E5%A6%82%E4%B8%B2%E5%88%97%E4%B8%AD%E7%AF%80%E9%BB%9E%E7%9A%84%E6%95%B8%E7%9B%AE%E3%80%82.jpg "[解決的辦法] 把頭節點當成特殊的節點來處理，不像其他的節點那樣專門用來儲存同類型的資料，頭節點裡可以記載一些與串列相關的資訊，例如串列中節點的數目。")
16
[對於操作的影響] 在鏈結串列建立的時候馬上加入一個頭節點，格式與其他的串列節點一樣，但是不用來儲存資料，只是為了讓鏈結串列在節點的處理操作上有一致性、提高執行時的效能。
![[對於操作的影響] 在鏈結串列建立的時候馬上加入一個頭節點，格式與其他的串列節點一樣，但是不用來儲存資料，只是為了讓鏈結串列在節點的處理操作上有一致性、提高執行時的效能。](http://slidesplayer.com/slide/16593575/96/images/16/%5B%E5%B0%8D%E6%96%BC%E6%93%8D%E4%BD%9C%E7%9A%84%E5%BD%B1%E9%9F%BF%5D+%E5%9C%A8%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E5%BB%BA%E7%AB%8B%E7%9A%84%E6%99%82%E5%80%99%E9%A6%AC%E4%B8%8A%E5%8A%A0%E5%85%A5%E4%B8%80%E5%80%8B%E9%A0%AD%E7%AF%80%E9%BB%9E%EF%BC%8C%E6%A0%BC%E5%BC%8F%E8%88%87%E5%85%B6%E4%BB%96%E7%9A%84%E4%B8%B2%E5%88%97%E7%AF%80%E9%BB%9E%E4%B8%80%E6%A8%A3%EF%BC%8C%E4%BD%86%E6%98%AF%E4%B8%8D%E7%94%A8%E4%BE%86%E5%84%B2%E5%AD%98%E8%B3%87%E6%96%99%EF%BC%8C%E5%8F%AA%E6%98%AF%E7%82%BA%E4%BA%86%E8%AE%93%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E5%9C%A8%E7%AF%80%E9%BB%9E%E7%9A%84%E8%99%95%E7%90%86%E6%93%8D%E4%BD%9C%E4%B8%8A%E6%9C%89%E4%B8%80%E8%87%B4%E6%80%A7%E3%80%81%E6%8F%90%E9%AB%98%E5%9F%B7%E8%A1%8C%E6%99%82%E7%9A%84%E6%95%88%E8%83%BD%E3%80%82.jpg "[對於操作的影響] 在鏈結串列建立的時候馬上加入一個頭節點，格式與其他的串列節點一樣，但是不用來儲存資料，只是為了讓鏈結串列在節點的處理操作上有一致性、提高執行時的效能。")
17
串列節點的插入 (insert) 節點可以插入到頭節點之後、尾節點之後，或是一般節點之後，但是不能插入到頭節點之前，這樣才能維持操作的一致性。下圖顯示如何將節點P插入到Pi之後。
18
串列節點的刪除 (delete) 規定串列的頭節點不能刪除，其他的節點都可以刪除。下圖顯示如何將節點P從串列中刪除。
19
3.2.2 基本操作 [鏈結串列的產生] [檢查鏈結串列是否為空的(isEmpty)] [插入節點(insert)]
[刪除節點(delete)] [鏈結串列的走訪(traversal)]
![3.2.2 基本操作 [鏈結串列的產生] [檢查鏈結串列是否為空的(isEmpty)] [插入節點(insert)]](http://slidesplayer.com/slide/16593575/96/images/19/3.2.2+%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C+%5B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E7%94%A2%E7%94%9F%5D+%5B%E6%AA%A2%E6%9F%A5%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E6%98%AF%E5%90%A6%E7%82%BA%E7%A9%BA%E7%9A%84%28isEmpty%29%5D+%5B%E6%8F%92%E5%85%A5%E7%AF%80%E9%BB%9E%28insert%29%5D.jpg "[刪除節點(delete)] [鏈結串列的走訪(traversal)]")
20
[鏈結串列的產生] 鏈結串列是由節點所形成的，必須先產生節點，下面以ListNode類別來定義一個鏈結串列的節點，一個節點包含兩個主要的資料成員，即所儲存的資料(底下的data屬性)、以及指向下一個節點的鏈結(底下的link屬性) 。
![[鏈結串列的產生] 鏈結串列是由節點所形成的，必須先產生節點，下面以ListNode類別來定義一個鏈結串列的節點，一個節點包含兩個主要的資料成員，即所儲存的資料(底下的data屬性)、以及指向下一個節點的鏈結(底下的link屬性) 。](http://slidesplayer.com/slide/16593575/96/images/20/%5B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E7%94%A2%E7%94%9F%5D+%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E6%98%AF%E7%94%B1%E7%AF%80%E9%BB%9E%E6%89%80%E5%BD%A2%E6%88%90%E7%9A%84%EF%BC%8C%E5%BF%85%E9%A0%88%E5%85%88%E7%94%A2%E7%94%9F%E7%AF%80%E9%BB%9E%EF%BC%8C%E4%B8%8B%E9%9D%A2%E4%BB%A5ListNode%E9%A1%9E%E5%88%A5%E4%BE%86%E5%AE%9A%E7%BE%A9%E4%B8%80%E5%80%8B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E7%AF%80%E9%BB%9E%EF%BC%8C%E4%B8%80%E5%80%8B%E7%AF%80%E9%BB%9E%E5%8C%85%E5%90%AB%E5%85%A9%E5%80%8B%E4%B8%BB%E8%A6%81%E7%9A%84%E8%B3%87%E6%96%99%E6%88%90%E5%93%A1%EF%BC%8C%E5%8D%B3%E6%89%80%E5%84%B2%E5%AD%98%E7%9A%84%E8%B3%87%E6%96%99%28%E5%BA%95%E4%B8%8B%E7%9A%84data%E5%B1%AC%E6%80%A7%29%E3%80%81%E4%BB%A5%E5%8F%8A%E6%8C%87%E5%90%91%E4%B8%8B%E4%B8%80%E5%80%8B%E7%AF%80%E9%BB%9E%E7%9A%84%E9%8F%88%E7%B5%90%28%E5%BA%95%E4%B8%8B%E7%9A%84link%E5%B1%AC%E6%80%A7%29+%E3%80%82.jpg "[鏈結串列的產生] 鏈結串列是由節點所形成的，必須先產生節點，下面以ListNode類別來定義一個鏈結串列的節點，一個節點包含兩個主要的資料成員，即所儲存的資料(底下的data屬性)、以及指向下一個節點的鏈結(底下的link屬性) 。")
21
[檢查鏈結串列是否為空的(isEmpty)]
簡單地說，只要鏈結串列中沒有任何節點就表示鏈結串列是空的，一個非空的鏈結串列至少要有一個節點。 串列的元素可以新增或刪除，所以有可能碰到串列沒有元素的情況，這時候存在的就是一個空串列。
![[檢查鏈結串列是否為空的(isEmpty)]](http://slidesplayer.com/slide/16593575/96/images/21/%5B%E6%AA%A2%E6%9F%A5%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E6%98%AF%E5%90%A6%E7%82%BA%E7%A9%BA%E7%9A%84%28isEmpty%29%5D.jpg "簡單地說，只要鏈結串列中沒有任何節點就表示鏈結串列是空的，一個非空的鏈結串列至少要有一個節點。 串列的元素可以新增或刪除，所以有可能碰到串列沒有元素的情況，這時候存在的就是一個空串列。")
22
[插入節點(insert)]
![[插入節點(insert)]](http://slidesplayer.com/slide/16593575/96/images/22/%5B%E6%8F%92%E5%85%A5%E7%AF%80%E9%BB%9E%28insert%29%5D.jpg "[插入節點(insert)]")
23
[刪除節點(delete)]
![[刪除節點(delete)]](http://slidesplayer.com/slide/16593575/96/images/23/%5B%E5%88%AA%E9%99%A4%E7%AF%80%E9%BB%9E%28delete%29%5D.jpg "[刪除節點(delete)]")
24
[鏈結串列的走訪(traversal)]
走訪有很多種目的，我們可能會走訪所有的節點，得到串列中節點的數目，代表串列的長度 (length)；假如想知道串列是否有某個數值，也是要透過走訪，檢視串列元素中儲存的資料，這種操作可以稱為找尋(find)。
![[鏈結串列的走訪(traversal)]](http://slidesplayer.com/slide/16593575/96/images/24/%5B%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E7%9A%84%E8%B5%B0%E8%A8%AA%28traversal%29%5D.jpg "走訪有很多種目的，我們可能會走訪所有的節點，得到串列中節點的數目，代表串列的長度 (length)；假如想知道串列是否有某個數值，也是要透過走訪，檢視串列元素中儲存的資料，這種操作可以稱為找尋(find)。")
25
實作Linked List 使用Java Collections Framework中的Linked List類別實作。
Linked List在Java API架構中的位置： import java.util.*; 宣告Linked List物件 LinkedList <資料型態>物件名 = new LinkedList <資料型態>(); Linked List可以直接輸出 System.out.println(物件名);
26
插入尾端節點(addLast) 使用addLast方法可直接將元素插入原Linked List尾端 程式碼：
1. 產生新節點(data為元素值，link指向null) 2. 將原linked list最尾端link指向新節點。 程式碼： 物件名.add(元素); 例如：obj.addLast(“Joe”); Joe null John null
27
插入前端節點(addFirst) 執行步驟 程式碼： 1. 產生新節點(data為元素值，link指向null)
2. 將新節點的link指向原linked list最前端節點。 程式碼： 物件名.add(元素); 例如：obj.addFirst(“Allen”);
28
插入節點(add) 若無索引值，可將元素插入原Linked List尾端(功能與addLast相同)
1. 產生新節點(data為元素值，link指向null) 2. 將原linked list最尾端link指向新節點。 若有索引值，則可在索引值位置上插入節點 2. 新節點的link指向索引值位置的節點。 3. 索引值的前節點link指向新節點。 程式碼： obj.add(“Martin”); obj.add(1, “Richard”);
29
刪除尾端節點(removeLast) 刪除linked list中的最後節點 程式碼： 將倒數第2個節點的link改為null。
刪除最後節點(回收空間)。 程式碼： obj.removeLast();
30
刪除前端節點(removeFirst) 刪除linked list中的最前端節點 程式碼： 將開頭改為第2個節點。
刪除第1個節點(回收空間)。 程式碼： obj.removeFirst();
31
刪除節點(remove) 給予索引值或元素，刪除該索引值或元素之節點。 程式碼： 將欲刪除節點的前節點，指向下個節點。
刪除節點。(回收空間) 程式碼： obj.remove(“Joe”); obj.remove(1);
32
取得目前長度(size) 使用size方法取得目前鏈結串列長度 其他Linked List相關方法：
obj.size(); 其他Linked List相關方法：
33
-The End-
Similar presentations
