Data Structures
這邊是一個菜鳥對於資料結構的超簡介學習筆記
資料結構: 用不同的排列、組織方法將純值(primitives)儲存起來
程式 = 資料結構 + 演算法 — — Niklaus Wirth
在JS中，用平常常用的 array 與 object 應該可以處裡幾乎全部的問題
但是時間&空間複雜度可能很差的時候，有可能換一個資料結構就會獲得大幅度的改善
線性結構
♟ array
相同類型的資料
有順序的結構
儲存在記憶體裡面連續的位置(js以外的語言需要先宣告陣列長度)
使用index可以找出儲存的位置
因為是連續的，所以尋找資料的時候很快速
(因為是連續的只要知道 index就能快速找出)
但是要插入資料的時候很麻煩，其他資料的index都要被改
陣列可以不只一個維度
accessing elements: O(1)
shift & unshift: O(n)
pop & push: O(1)
remove(從中間): O(n)
♟Linked lists
跟array相似
但不需要放在記憶體裡面連續的位置(儲存位置不連續)
包含兩個property: 頭(head)(指出第一個node)、長度(length) (顯示有幾個node)
每個node包含: value 跟 pointer
使用指標(Pointer)指出下一個節點的位置
- single linked list: SLL 一個pointer，指向next
- doubly linked list: DLL 比SLL多一個pre的 pointer
因為不用連續，所以要插入資料的時候比array容易(只要修改pointer)，時間複雜度是O(1)
但要尋找資料的時候比較麻煩(要從頭開始一個連去下一個看)，時間複雜度是O(n)，在硬體上CPU要搜尋也比較麻煩
js 沒有內建這個資料結構，要自己寫，自己寫一個linked list 的詳細code放在我的gitHub上 linkedList
accessing elements: O(n)
shift & unshift: O(1)
pop & push: O(n)
remove(從中間): O(n)
linked list 參考資料:
- 基礎演算法系列 — 基礎資料結構 Linked-list 與 Array
- 因為不是常用到的資料結構，我有特別挑一些題目來練習，要看實戰解題可以參考我的 Linked list系列leetCode題
Abstract 抽象資料類型
♟ Stacks
一種概念(concepts)，可以用不同方法實踐(可用linkList 或 array等實做出來)
有順序排列但是單邊進(push)出(pop)
而且是後進先出（LIFO, Last In First Out）
有size(裡面有幾個)但在裡面的東西沒有index
a finite ordered list with zero or more elements
stack(MaxStacksize = defaultSize)
boolean: isFall(), isEmpty()
void add()(push)
KeyType delete()(pop or delete)
可以用array 或 linked list 實作(implyment)出來
實作一個stack的code(用linked list 實作)請見 gitHub
實作的敘述:
用物件導向的方法先寫好，要用的時候在繼承
建立 Stack，只放使用 .pop( ) 跟 .push( )
然後建立 MyStack = new Stack (直接繼承來用)
實際應用的概念:
1. JS 裡面的 Call stack 就是使用這種結構
2. 迷宮紀錄: 往下走發現不對要往回走，每次往回走一步: 用stact紀錄正好
♟ queues
也是一種概念(concepts)
有順序排列，有size，但是也沒有index
不同邊進出, 使用兩個 pointer: 後端（rear）進行加入操作，前端（front）(最前頭的前一個)進行移除操作
而且是先進先出（FIFO, First In First Out）
增加東西: Enqueues，移除東西: Dequeues
a finite ordered list with zero or more elements
Queue(MaxQueueSize = defaultSize)
boolean: isFull(), isEmpty()
void add()
KeyType delete()
(像排隊隊伍XD)
是抽象結構，可以用其他資料結構實作出來，常見用 array 或 linked list
實際使用上可以有很多變化
譬如說 priority queue、 circular queue
liner queue: 跟 circular比全塞滿不會有難判斷的問題
但是delete的時候可能要做資料搬動的麻煩
circular queue: full跟empty比較難判斷，全塞滿會難判斷
front = rear => empty
rear+1 = front =>full
_______________________________
進階一點:
♠ Deque
double end queue
長的像 stack 跟 queues 的混合體:
(白話來說)頭尾都可以加跟移除東西，但是不能在中間
♠ priority queue
比一般的 Queue 多一個優先權的 associate
優先權會高於一般單純的先進先出順序
舉例的話像是急診室看診順序! 嚴重的優先權比較高 = 先看
實作 priority queue 這總概念效率最好的是 max heap
(可參考下面 binary tree 的 heap)
簡單來說用max heap 來做 big O 比較好
使用不同資料結構做 priority queue的big O:
→ max heap:
Enqueue: O(log n)
Dequeue: O(log n)
→ array or linked list:
Enqueue: O(n) (在原本排列好的array裡用 insertion sort插入的big O)
Dequeue: O(1)(linked list) or O(n)(array)
♟ Trees (binary trees and heaps)
是一種Graphs 但沒有 loop(cycle)
有根結點 root (而且只能有一個)
階層關係
真實世界常見這種資料結構在….:
- DOM
- 電腦資料夾結構
🧠 Tree travertsal:
夾帶相關的演算法XD
實作可參考下面 BST 實做的code裡有寫
解題的時候選正確的遍歷方法有幫助
breadth-first tree traversal:(BFTT)(或BFS)
可用Queue 或 array實作
deep-first tree traversal: (DFTT)(或DFS)
可用 stack 或 array實作
PreOrder: root left right (root 最先)
InOrder: left root right (root 中間)
PostOrder: left right root (root 最後)
Tree 相關的演算法以及以上詳細，請參考Algorithm 文章
BFT、DFT、Greedy Algorithm相關演算法
參考資料:
【Day14】[資料結構]-二元樹走訪Binary Tree Traversal
_________________________
進階一點的相關資料結構:
♠ Binary trees
分2岔的樹
每個節點最多只能有兩個children可以有左小孩和右小孩
每個節點可以有0、1、2小孩
child node 位置公式(parent node idx = n):
n *2+1, n *2+2
______________________
進階一點:
♠ Binary Search Tree (BST)
實做的code 參考 這邊
也是一種binary tree，符合所有 binary tree的定義
有額外的規定: left child < root < right child
適合用來做未知會擴展到多大的資料結構
balanced v.s. unbalance bst
worst case performance: O(n)
best case performance: O(1)
averagy case performance: O(log n)
♠ Complete Binary trees
每一個node都滿了， 除了
(not full) 最右邊最底層可以容許一些空者
♠ Full Binary trees
所有的leaf node 深度都一樣
縮寫FBT
♠ Heap(Binary heap )
極值資料結構(堆疊)
是一個完全二元樹 (complete binary tree)
最小堆疊(所有父都比子小)、最大堆疊(max heap)(所有父都比子大)
求極值特別方便
♠ minimal spanning tree (MST)
graphs 移除部分edges 變成的 spanning tree
所有 edges 相加最小的 sapnning tree 就是 MST
♟ Graphs
抽象資料類型
有限的資料(finite set of verticcs(nodes))，相連的地方稱作 edges(link)
(白話): 一個graphs包含許多資料點，用 edges 相連
edges分兩種: 有方向性(direct graphs)、沒有方向性(undirect graphs)
edges 有值得稱作 weighted
沒有根結點
沒有階層關係
實作graphs的常見方法有兩種:
1. 二維陣列: 用0(不相連)或1(相連)來表示是否有關連
2. linked list
相關的演算法很多，參考Algorithm 文章裡
BFT、DFT、Dynamic programming 相關演算法
♟ Hashtables
key-value pair
省時間(收尋資料只要O(1))省空間 (說明在最下面)
舉例實際的應用:
1. password hashing 密碼加密(hash function)
2. JS 裡面object 跟 array 其實都 hash過
3. Python 裡面的 dictionaries
4. JAVA裡面的 hashSet、hashMap、linkedHashSet、linkedHashMap
可以用array實作 (實作的code 放在這)
🧠 hash function:
m: size of hash table
1. division method: Index = Key mod m
優點: 速度快
缺點:
1. m值絕對不可以選到 2^x
2. 用名稱(非數字)去轉換時要考慮命名規則是否會有像似度高的問題，不然會出現超多 collision
2. Multipication method: Index = [m(keyA%1)]
A = (√5 -1) / 2 (約等於0.618033…….)(是一個無理數)
優點: 產生出來的值是比較隨機的
______________________
名詞解釋:
collision:兩個以上個值會被hash進同一個index時
解決方法:
Chaining: 有 collision的位置直接做成二維array，每個值都塞進來
load factor: ratio: n/m
— — — — — — — — — — ——
沒有數字可以當hash key的時候, 常用的解決辦法:
轉成數字要夠隨機，越隨機將來的collision機會就越低
舉例，只有string的時候:
- (最差) 直接把string length 當作 key
- 把string中每個字的 ASCII value 相加然後當作 key (比上面的好多)
(參考parse() function) - 把string中每個字做洗牌(自己設計)，然後再設計公式去加減乘除每個字的 ASCII value (加密演算法中常見的方法)
_________________________
hashTable的searching時間複雜度: O(1)
前提假設:
1. hash function 在 hash 任何key 時，時間複雜度為 O(1) (其實在key不為number時，不一定為O(1))
2. 假設每個位置都平均的分配到值(doing simple uniform hashing)
load factor: n/m = ∝
m = θ(n)
∝ = O(1)
hash table runing time O(1+ ∝) → O(1)
♟ set
裡面的元素不可重複
使用set:
set.size 裡面元素數量
set.add() 增加元素
set.delete(‘a’) 移除'a'
set.has(‘a’) 查詢裡面是否有’a’，回傳boolean
________________________
參考資料:
2–1 U18
[Data Structure] 2019鐵人賽文章
