iT邦幫忙

2021 iThome 鐵人賽

DAY 3
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 3

【Day3】[資料結構]-鏈結串列Linked List

鏈結串列(Linked List)常用來處理相同類型資料,在不連續的記憶體位置,以隨機的方式儲存,由於不用事先宣告一塊連續記憶體空間,所以較不會造成記憶體的浪費。

由許多節點組成,每個節點包含資料欄指標欄,指標欄會指向下一個資料所在的記憶體位置。因此再追加或刪除資料相當方便,因為只需要更動指標的指向,但在讀取資料就會較費時,因為必須從串列的頭開始尋找。

可以想像一輛火車,透過掛勾將車廂一節一節地串起來,能夠依乘客需求多寡來使用掛勾更動車廂數量。


單向鏈結串列Singly Linked List

基本的鏈結串列結構,從串列頭(Head)開始依序指向下一筆資料,串列尾(Tail)為最後一筆資料指向空值(Null)。
https://ithelp.ithome.com.tw/upload/images/20210914/20121027KfaEdl6AVY.jpg

追加資料的步驟

只需要更動指標的指向。
https://ithelp.ithome.com.tw/upload/images/20210914/20121027Fuy64ZBv9p.jpg


雙向鏈結串列Doubly Linked List

每個節點會變成一個資料欄兩個指標欄,讓資料可以從頭或尾巴開始找,優點是可以讓被破壞或遺失的節點被找回來,但在追加或刪除資料時,必須更動比單向鏈結串列更多的指標次數
https://ithelp.ithome.com.tw/upload/images/20210914/20121027GQdhacYTQ0.jpg


環狀鏈結串列 Circular Linked List

在單向鏈結串列中,萬一某節點被破壞或遺失,整個串列將會沒作用,因此如果把串列最後一個節點指向串列頭,這樣每個節點都可以是串列頭
https://ithelp.ithome.com.tw/upload/images/20210914/20121027lkG5jI8XoZ.jpg


陣列與鏈結串列的優缺點比較

https://ithelp.ithome.com.tw/upload/images/20210914/20121027POuiLls7tO.jpg

陣列的介紹可以參考此篇


上一篇
【Day2】[資料結構]-陣列Array
下一篇
【Day4】[資料結構]-鏈結串列Linked List-實作
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言