資料結構:
- 如何在電腦中儲存資料。
- 是一種工具，如:演算法搭配適合的資料結構。
選擇不同的資料結構:
- 時間複雜度:非常頻繁拿、取，希望時間可以短一點。
- 空間複雜度:需要另外用空間來加速，那空間可能要比較多。
- coding複雜度:比如有兩種結構可以實作這程式，那選較容易、不容易出錯的那個。
常見操作
push放入一個元素、pop取出一個元素、query查詢
堆疊
堆疊(stack，FILO，first in last out)，先進後出，如碟盤子。
實作搭配linked list
push:在head插入一個節點
pop:刪除head指向的節點
時間複雜度:
push:O(1)
pop:O(1)
佇列
佇列(queue，FIFO，first in first out)，先進先出，如排隊。有環狀、單向之分。
實作搭配linked list或環狀佇列。
push:在end後面插入一個節點
pop:刪除head指向的節點
時間複雜度:
enqueue:O(1)
dequeue:O(1)
鏈結串列
鏈結串列(linked list)。
基本單元:Node(data+pointer)
將很多Node接起。
head指向第一個node，最後一個指標指向NULL。
性質:
- 每個元素只記錄他下一個元素，外部只記錄起點(head)
- 動態宣告記憶體，需要時就要，不需要就還給系統
- 分類:單向、雙向、環狀
- 不能隨機存取，因為外部只記錄起點(head)，所以只能從頭去一個一個下去找，第一個告訴我第二個在哪，第二個告訴我第三個在哪…。
操作:
insert新增元素，在兩個元素間，或是頭、尾插入
delete刪除元素
時間複雜度:
insert:O(1)，只要重新更改pointer指向
delete:O(1)，只要重新更改pointer指向
為什麼不用陣列，還能隨機存取?
1.避免記憶體浪費，但array的dynamic array也能做到
2.可以快速刪除、插入節點，這array沒辦法做到。
下面兩個是延伸，不過要控制的資料變多，可能維護下來除起bug的機率會高。
雙向鏈結串列
環狀鏈結串列
時間複雜度比較
此外，兩個linked list合併速度很快，因為只要指向另一個的頭即可，只要O(1)。
總結
從這章中理解到為什麼要用資料結構，選用適合的資料結構可以改善程式的速度、程式碼難易度。在前面這幾篇中預計以理解原理為主，底層實作則未來有時間再另外拿出來寫。
如果是頻繁讀取，可以用array；如果頻繁新增、刪除，可以用linked list。