基礎演算法系列 — 基礎資料結構 Linked-list 與 Array
Linked List 與 Array 是最常拿來比較，也是兩種基本的資料結構，它們都可以用來儲存資料，但是在使用情境不同的情況下，使用 Linked List 或是Array 都會有著各自不同的好處與壞處。
Array (陣列)
- 是由相同類型的元素（element）的集合所組成的資料結構
- 一個 Array 會分配一塊連續的記憶體來儲存
- 必須預先知道整體資料大小來分配記憶體
- 利用元素的索引（index）可以計算出該元素對應的儲存位址
- 可以有一維與多維的陣列
- 可以透過 index 直接存取各個元素的值
Linked List (鏈結串列)
- 各節點的資料型態不必一定相同
- 每個點放在不同記憶體位置，不會按線性的順序儲存資料
- 記憶體非連續，不需事先知道整體資料大小
- 每一個節點裡存有到下一個節點記憶體位置的 pointer
- 可以有單向或是雙向的 linked list
- 能夠被直接存取的節點只有最前面的第一個節點
Search, Insert and Delete
實務上最常用到的就是處理 array 與 linked list 的各項資料操作，如搜尋某一值(節點)的位置、插入一個新的值(節點)，或是刪除現有的值(節點)。
資料結構
以剛剛的兩張圖來當例子，先來看看 array 與 linked list 的結構：
Array
const a = [10, 24, 1, 5, 8];Linked list
在宣告 linked list 的時候，每一個節點都必須要告訴他的下一個節點是誰，所以會如以上所示。
Search
當我們想要從 array 或是 linked list 找出第三個值的時候，array 可以很輕易地直接透過 index = 2 ，就可以取出第三個值，而 linked list 需要先從第一個點 node1 得到 node2 的位置，再從 node2 得到 node3 的位置，最後才可以取出 node3 的值。
Array
a[2]Linked list
node1.next.next.valueInsert
當我們想要在本來的第三個位置，插入一個新的值 100 ，這時候在 array 上就比較麻煩了，雖然我們可以很快地找到第三個位置，但必須要將後面其他的值，全部往後推一格。在 linked list 就發揮他動態的強項了，只要我們找到第二個節點的時候，把 node2.next 替換成新的點，再把新的點的 next 接回去本來的舊的第三個點，就大功告成囉。
Array
Linked list
Delete
刪除一個節點的作法跟 insert 的概念差不多，在 array 要把被刪除點之後的點全部往前移動一格，linked list 則只需要改變 pointer 即可。
Array
Linked list
以上就是非常基本的 Array 與 Linked list 的複習筆記，更多演算法與資料結構文章：
