鏈結串列(Linked List)

Da-Wei Chiang

大綱

• 何謂鏈結串列
• 查看記憶體位置
• 圖例鏈結串列
  • 鏈結串列的結構
  • 鏈結串列資料讀取
  • 鏈結串列資料插入
  • 鏈結串列資料刪除
• 實作練習
• 時間複雜度總整理
• 鏈結串列的進階結構
• 圖例鏈結串列的進階結構
• 實作練習

何謂鏈結串列

• 鏈結串列：每一個資料點會紀錄下一個資料點所在的記憶體位置.
• 基於上述的特性, 鏈結串列的資料散佈於記憶體的各個地方
• 鏈結串列的每一個資料節點均包含「資料與下一個資料的記憶體位置」
• 鏈結串列的進階結構
  • 雙向鏈結串列(Double Linked List)
  • 循環鏈結串列(Circle Linked List)

查看記憶體位置

• python中查看記憶體位置可以使用內建函數id

##範例

my_int_one = 10
print(id(my_int_one))
my_int_two = 11
print(id(my_int_two))
my_int_three = 10
print(id(my_int_three))  #python節省記憶體空間機制
my_int_three = 12
print(id(my_int_three))
print('- - - - - - -')
my_list_one = [1, 2, 3]
print(id(my_list_one))
my_list_two = my_list_one
print(id(my_list_two))
my_list_two = my_list_one[:]  #淺拷貝
print(id(my_list_two))

4311530576
4311530608
4311530576
4311530640
- - - - - - -
4352358272
4352358272
4352328560

鏈結串列的結構

• 鏈結串列的結構就像一列火車, 車廂(資料)與車廂(資料)之間有所關聯.

鏈結串列資料讀取

• 鏈結串列的資料讀取須從頭開始.
  • 如：要讀取台南的資料須從『台北開始經過台中才能讀取到台南』。
• 因為需要經過每個節點，故時間複雜度為O(n)

鏈結串列插入新資料

• 將欲插入位置節點的上一個節點指向新節點, 並將新節點指向預插入位置的下一個節點
• 由於插入節點
  • 插入第一個節點與中間的節點，不需遍歷整個鏈結串列，故時間複雜度為O(1)
  • 插入最後一個節點需走訪整個鏈結串列，故時間複雜度為O(n)

鏈結串列刪除資料

• 將欲刪除位置節點的上一個節點指向預刪除位置的下一個節點即可
• 雖然被刪除的節點仍存在於鏈結串列的記憶體中, 但已無法進行走訪.故等於刪除節點
• 由於刪除節點需遍歷整個鏈結串列才能知道要刪除的位置，故時間複雜度為O(n)

實作練習

• 建立節點類別
• 建立鏈結串列類別
• 於第一個位置插入資料
• 於最後一個位置插入資料
• 於中間位置插入資料
• 刪除資料

練習

• 建立一個節點的類別, 透過節點類別所建構的物件建立一個鏈結串列
• 試著建立資料為Taipei, Taichung, Tainan的資料點並串成一個linkedlist透過while迴圈走訪

練習

• 承上題練習題
• 建構一個LinkedList的類別, 可透過這個類別建構的物件去輸出整個LinkedList的結果

練習

• 承上題練習題
• 新增LinkedList類別的功能, 於第一個節點插入資料

練習

• 承上題練習題
• 新增LinkedList類別的功能, 於最後一個節點插入資料

練習

• 承上題練習題
• 新增LinkedList類別的功能, 指定於哪個節點下插入新節點

如：
link_variable.add_mid_Node(n2, value)   #在n2節點後新增一個節點, 其資料為value

練習

• 承上題練習題
• 新增LinkedList類別的功能, 指定資料刪除相應的節點

時間複雜度總整理

• 資料讀取
  • O(n)
• 資料插入
  • O(1)
• 若插入資料需搜尋節點
  • O(n)
• 資料刪除
  • O(1)
• 若刪除資料需搜尋節點
  • O(n)

鏈結串列的進階結構

• 循環鏈結串列(Circle Linked List)
• 雙向鏈結串列(Double Linked List)

循環鏈結串列(Circle Linked List)圖例

• 串列的最後一個元素連接至串列的第一個元素

雙向鏈結串列(Double Linked List)圖例

• 串列中的每個元素除了指向下一個元素, 同時也指向上一個元素

實作練習

• 建構循環鏈結串列
• 建構雙向鏈結串列

練習

• 建構一個循環鏈結串列的結構
• 試著建立串列的三個節點分別為Taipei, Taichung, Tainan
• 撰寫一個方法帶入相應的次數, 可印出這個串列相應的次數值. 如：該方法帶入次數5則印出Taipei, Taichung, Tainan, Taipei, Taichung

練習

• 建構一個循環鏈結串列的結構
• 試著建立串列的三個節點分別為Taipei, Taichung, Tainan
• 撰寫兩個方法如下
  • 從頭走訪這個串列. 印出Taipei, Taichung, Tainan
  • 從尾走訪這個串列. 印出Tainan, Taichung, Taipei