資料結構/權衡
< 資料結構
在選擇資料結構之前，全面理解需要解決的問題非常重要，因為每個結構都針對特定任務進行了最佳化。例如，雜湊表優先考慮快速查詢時間而不是記憶體使用，而陣列則緊湊且不靈活。其他結構，如堆疊，則最佳化為在整個程式執行過程中對資料新增、刪除和訪問方式實施嚴格的規則。對資料結構的良好理解是基礎，因為它為我們提供了以結構化方式思考程式行為的工具。
[TODO:] Use asymptotic behaviour to decide, most importantly seeing how the structure will be used: an infrequent operation does not need to be fast if it means everything else will be much faster
[TODO:] Can use a table like this one to compare the asymptotic behaviour of every structure for every operation on it.
| 陣列 | 動態陣列 | 陣列雙端佇列 | 單鏈表 | 雙鏈表 | |
|---|---|---|---|---|---|
| 推入（前端） | - | O(n) | O(1) | O(1) | O(1) |
| 彈出（前端） | - | O(n) | O(1) | O(1) | O(1) |
| 推入（後端） | - | O(1) | O(1) | O(n)，可能為 O(1)* | O(1) |
| 彈出（後端） | - | O(1) | O(1) | O(n) | O(1) |
| 在（給定迭代器）之前插入 | - | O(n) | O(n) | O(n) | O(1) |
| 刪除（給定迭代器） | O(n) | O(n) | O(n) | O(1) | |
| 在（給定迭代器）之後插入 | O(n) | O(n) | O(1) | O(1) | |
| 在（給定迭代器）之後刪除 | - | O(n) | O(n) | O(1) | O(1) |
| 獲取第 n 個元素（隨機訪問） | O(1) | O(1) | O(1) | O(n) | O(n) |
| 適合實現堆疊 | 否 | 是（後端為頂部） | 是 | 是（前端為頂部） | 是 |
| 適合實現佇列 | 否 | 否 | 是 | 可能* | 是 |
| C++ STL | std::array
|
std::vector
|
std::deque
|
std::forward_list
|
std::list
|
| Java 集合 | java.util.Array
|
java.util.ArrayList
|
java.util.ArrayDeque
|
- | java.util.LinkedList
|
* singly-linked lists can push to the back in O(1) with the modification that you keep a pointer to the last node
| 排序陣列 | 排序連結串列 | 自平衡二叉搜尋樹 | 雜湊表 | |
|---|---|---|---|---|
| 查詢鍵 | O(log n) | O(n) | O(log n) | 平均 O(1) 最差 O(n) |
| 插入元素 | O(n) | O(n) | O(log n) | 平均 O(1) 最差 O(n) |
| 刪除鍵 | O(n) | O(n) | O(log n) | 平均 O(1) 最差 O(n) |
| 刪除元素（給定迭代器） | O(n) | O(1) | O(1) | O(1) |
| 可以按排序順序遍歷嗎？ | 是 | 是 | 是 | 否 |
| 需要 | 比較函式 | 比較函式 | 比較函式 | 雜湊函式 |
| C++ STL | - | - | std::setstd::mapstd::multiset
|
std::unordered_setstd::unordered_mapstd::unordered_multiset
|
| Java 集合 | - | - | java.util.TreeSet
|
java.util.HashSet
|
- 請更正任何錯誤
| 二分搜尋 | AVL 樹 | 二叉堆（最小堆） | 二項佇列（最小堆） | |
|---|---|---|---|---|
| 插入元素 | O(log n) | O(log n) | O(log n) | O(1)（平均） |
| 刪除元素 | O(log n) | O(log n) | 不可用 | 不可用 |
| 刪除最小元素 | O(log n) | O(log n) | O(log n) | O(log n) |
| 查詢最小元素 | O(log n) | O(log n) | O(1) | O(log n)（如果指向最小值的指標則可以為 O(1)） |
| 增加鍵 | 不可用 | 不可用 | O(log n) | O(log n) |
| 減少鍵 | 不可用 | 不可用 | O(log n) | O(log n) |
| 查詢 | O(log n) | O(log n) | 不可用 | 不可用 |
| 刪除元素 | O(log n) | O(log n) | 不可用 | 不可用 |
| 建立 | O(1) | O(1) | O(1) | O(1) |
| 查詢第 k 小的元素 | O(log n) | O(log n) | O((k-1)*log n) | O(k*log n) |
| 雜湊表（雜湊對映） | |
|---|---|
| 設定值 | Ω(1)，O(n) |
| 獲取值 | Ω(1)，O(n) |
| 刪除 | Ω(1)，O(n) |
[TODO:] Can also add a table that specifies the best structure for some specific need e.g. For queues, double linked. For stacks, single linked. For sets, hash tables. etc...
[TODO:] Could also contain table with space complexity information (there is a significative cost in using hashtables or lists implemented via arrays, for example).