iT邦幫忙

2021 iThome 鐵人賽

DAY 19
0
自我挑戰組

一個月的演算法挑戰系列 第 19

Day19:鏈接串列(Linked List)

鏈接串列(Linked List)

鏈接串列是一種線性表,使用Pointer串接資料,好處是找到目標位置後,可以有效率的插入或刪除元素,陣列不適合在中間位置插入或刪除資料(耗費較多時間),適合在兩端執行插入或刪除。
鏈接串列不能隨機讀取目標資料,只能逐個走到指定位置才能讀取,但陣列可以使用索引,兩者各有優缺點,可以視需求使用。

https://ithelp.ithome.com.tw/upload/images/20210917/20128286IRQSn6kwJ3.png

延伸閱讀:https://medium.com/@tobby168/%E7%94%A8python%E5%AF%A6%E4%BD%9Clinked-list-524441133d4d


環狀鏈接串列(Circular Linked List)

環狀鏈接串列式使用Pointer串接資料,最後一個element可以連接到第一個element。
使用Circular Linked List的好處是是找到指定元素後,可以快速的執行插入或刪除。
如下圖:

https://ithelp.ithome.com.tw/upload/images/20210917/20128286sYE9uTkrBO.png

延伸閱讀:https://www.geeksforgeeks.org/circular-linked-list-set-2-traversal/


雙向鏈接串列(Double Linked List)

雙向鏈接串列式使用Pointer串接資料,好處是找到目標位置後,可以很有效率的執行插入或刪除動作,也很容易找到node的前一個或後一個element。壞處是不能隨機讀取指定位置的element,只能從前往後或從後往前一個個找到目標位置。

https://ithelp.ithome.com.tw/upload/images/20210917/20128286mtzkvafOPf.png

延伸閱讀:https://favtutor.com/blogs/doubly-linked-list-python


上一篇
Day18:圖形搜尋-戴克斯特拉演算法(Dijkstra's algorithm)
下一篇
Day20:安全性和演算法-雜湊函數(hash function)
系列文
一個月的演算法挑戰30

尚未有邦友留言

立即登入留言