Featured image of post 【資料結構 Data Structure】Linked List 鏈結串列:Singly & DoublyLinked List 定義、Linked List 優點、Array 和 Linked List 的差異

【資料結構 Data Structure】Linked List 鏈結串列:Singly & DoublyLinked List 定義、Linked List 優點、Array 和 Linked List 的差異

【資料結構 Data Structure】Linked List 鏈結串列:Singly & DoublyLinked List 定義、Linked List 優點、Array 和 Linked List 的差異

Image by macrovector on Freepik

Singly Linked List 定義

  • 每個 Node 會包含 value 和 next 的資訊
  • Linked List 會包含 head, tail 的資訊
  • Linked List 包含 append, prepend, insert, remove, printList 的方法

Doubly Linked List 定義

  • 每個節點(Node)包含了 next, prev 和 value
  • Linked List 會紀錄 head, tail 的資訊
  • Linked List 實作了 append, prepend, insert, remove printList 的方法

Linked List 鏈結串列

Linked List 優點

使用 Linked List 的資料結構可以更有效率的使用記憶體,因為每一個元素都是獨立,彼此之間是透過 next 和 prev 來關聯在一起

Array 和 Linked List 的差異

Linked List Array
說明 類似把很多個物件關聯起來,並有順序性 同一記憶體空間的一個區間
記憶體 不需要連續的記憶體空間,因此不需要預留空間 需要連續的記憶體空間,宣告時就需要決定空間大小
資料插入/刪除 相對快,插入和刪除本身是 O(1),但有時需要先搭配搜尋 O(n) 來找到節點位置 相對慢,插入與刪除均為 O(n)
資料取出 相對慢,要從頭開始找 O(n) 到後取出 相對快,可以直接使用索引(index)取出
適用時機 1. 無法預期資料數量時 2. 需要頻繁增刪資料時 3. 不需要頻繁查詢並取出資料時 1. 需要快速取出資料時 2. 不需要頻繁增刪資料時 3. 資料的數量不會有太大變更時

參考資料

Donate KJ 贊助作者喝咖啡

如果這篇文章對你有幫助的話,可以透過下面支付方式贊助作者喝咖啡,如果有什麼建議或想說的話可以贊助並留言給我
If this article has been helpful to you, you can support the author by treating them to a coffee through the payment options below. If you have any suggestions or comments, feel free to sponsor and leave a message for me!
方式 Method 贊助 Donate
PayPal https://paypal.me/kejyun
綠界 ECPay https://p.ecpay.com.tw/AC218F1
歐付寶 OPay https://payment.opay.tw/Broadcaster/Donate/BD2BD896029F2155041C8C8FAED3A6F8
All rights reserved,未經允許不得隨意轉載
Built with Hugo
Theme Stack designed by Jimmy