iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
Software Development

少女人妻在廚房裡想不通的演算法系列 第 6

【在廚房想30天的演算法】Day 06 資料結構:連結串列 Linked List

Aloha!又是我少女人妻 Uerica ,今天中秋節大家吃肉了嗎!傳說中后羿的狗狗偷吃了嫦娥吃剩的靈藥,就跟嫦娥一樣一起飛到月亮上,然後把嫦娥跟月亮都吃掉了!恩...狗狗這麼貪吃也合理啦。


連結串列 (Linked List)

好的~今天要來聊一下鏈結串列在記憶體中是如何儲存資料的吧!連結串列與陣列 (Array) 一樣是線性資料結構,但一般的程式語言在宣告陣列時,需要先規定記憶體儲存空間的大小(陣列長度),所以如果不知道資料會增長到多大,常常會碰到不知道如何規定資料大小,或是記憶體預留過多空間,造成空間浪費等情況,此部份在介紹陣列的資料結構會有更詳細的說明。但 JavaScript 所提供的陣列方法並沒有一般語言來得嚴謹,原因是底層作用不太一樣,這部分之後再寫一篇與大家說明瞜~

連結串列定義與特性

連結串列是由多個節點 (node) 所組成,節點之間會用指標 (pointer) 來做連結,所謂的指標就是紀錄指向的另一個節點在記憶體中的位置,如果沒有下一個節點則為 null。而每個節點中會紀錄需要被存取的資料元素。

節點 (node) 中存取的資料:

  • 資料元素 (:需要被存取的一筆資料
  • 指標:指向的節點在記憶體中的位置

mrNC351

而連結串列的特性是便於插入或刪除節點,但在存取數據時,一筆資料元素的存取會佔較多記憶體空間也較為費時。不過因為擁有指標,所以不用像陣列一樣連續式的儲存在記憶體內,而是可以分散在不同地方。

  • 優點
    • 便於資料元素插入、刪除
    • 非佔用連續記憶體空間,無須先定義資料大小與長度
  • 缺點
    • 由於節點是被分散在記憶體各個角落,且要依照指標才能找到下一個節點,所以只能用順序存取 (sequential access) 的方式。
    • 在增加一個資料元素時,因除了寫入資料元素在節點外還需要寫入指向的指標,所以增加一個節點比起陣列單純增加資料元素佔較多記憶體空間。

連結串列是由一連串結點所組成
mn1jpgY
實際在記憶體中會是這個樣子,無需連續儲存
db2xze3

常見的基本操作

插入新節點

連結串列若要插入新節點(如圖示的 Node New 要插入 Node A 與 Node B 之間),只需改變 Node A 指標指向的位置,以及在 Node New 寫入Node B 位置即可。

將 Node New 插入 Node A 與 Node B 之間
Jb2Bnhl
只需改寫或增加下一個 node 的位置
QYdfFut

刪除節點

承上圖,假設現在我們要刪除 Node B ,則將 Node New 的指標指向 Node C 的位置即可。
teLAfMa
此時 Node B 已無法存取,可刪除或持續保留在記憶體中,這邊也可發現若有兩個 Node 指向同一個 Node 是可行的,這也是連結串列中資料可共享的優勢。

連結串列類型

單向連結串列(Singly Linked List)

單向連結串列,也是最基本的連結串列,每個節點的指標指向下一個節點,存取時只能使用順序存取的方式從頭開始依序往下讀取。
ytx08xh

雙向連結串列(Doubly Linked List)

雙向連結串列與單向不同的是,每個節點都有指向上一個節點與下一個節點的指標,所以在存取時可從任一節點開始。
g5IEF4k

迴圈連結串列(Circularly Linked List)

迴圈連結串列與雙向連結串列類似,但迴圈連結串列頭尾節點的指標會再指向對方並連成一個環。
gqQ6dlL

關於連結串列的時間複雜度

由於連結串列屬於線性關係,所以在資料存取需要 O(n) 的時間複雜度,不過插入與刪除通常只需要 O(1) 的時間複雜度。


參考資料:

Linked list Javascript實作及Leet code題目解析

JavaScript 學演算法(五)- 鏈結串列 Linked list

維基百科 - 連結串列

資料結構: Pointer 指標與Link-link實作 youtube影片


感謝各位閱讀!最近寫文章很少陪狗狗玩,再不帶她出門遛遛我可能也會被吃了!哈哈哈哈,明天見啦掰掰~


上一篇
【在廚房想30天的演算法】Day 05 資料結構之冰箱整理術
下一篇
【在廚房想30天的演算法】Day 07 資料結構:陣列 Array
系列文
少女人妻在廚房裡想不通的演算法30

尚未有邦友留言

立即登入留言