LeetCode資料結構

Array跟LinkedList之間差異

Array是index based的結構，LinkedList則是Reference based。
Array會存在sequential memory locations，LinkedList則是sequence of the elements，每一個element都會link下一個element。(Array節省記憶體使用空間，LinkedList需要儲存pointer，所以需要較大的空間。)
Array裡面會儲存同樣結構的資料，LinkedList裡面每個儲存的Object都會包含Data與Link。
Array必須先宣告要多大的空間，LinkedList則不受限。
Array存取資料需要index，LinkedList需要從頭開始尋找資料。

Array：Random Access即是隨機存取，又被大家稱為直接存取。在compile的時候，便分配好空間，因此是固定的。在記憶體儲存是連續的。

Array:O(1), 直接存取或隨機存取

LinkedList：Sequencial Access則是需要循序走訪才能到達指定的目標。在run time的時候分配空間，因此是彈性的。記憶體中隨機儲存位置。

LinkedList:O(n), 每次存取資料都需要循序走訪

https://visualgo.net/en/list

單鏈串列與雙鏈串列的比較

單鏈串列

優點:

1.較節省空間

2.插入與刪除節點時，需要修改的鏈結個

數較少

缺點:

1.插入與刪除節點時，需提供前一節點的指標

2.不能雙向移動

雙鏈串列

優點:

1.雙向移動

2.插入與刪除節點時，不需要給前一節點指標 (可以用前一個節點或後一個節點取得)

缺點:

1.較佔用空間

2.插入與刪除時，需要改變較多的鏈結欄位

Array 優點在於有Index可更快速存取但相應預先定義好的固定大小帶來空間利用與新增移除元素容易造成浪費空間跟較不彈性

LinkedList較容易新增與移除元素但缺點就在於只能依序讀取且要多一個空間紀錄下一個node位置。

LeetCode常見題目

Ref:

Linked List vs Array

https://www.geeksforgeeks.org/linked-list-vs-array/

https://medium.com/analytics-vidhya/a-brief-overview-of-linked-list-in-python-eaf4aa8821be

第25個冬天