# 1.1 學習演算法與刷題的概念框架

## 1.1.1 資料結構的貯存方式
- 底層實作僅有兩種: Array & Linked List
- 其他資料型態: Hash table, stack, queue, heap, tree, graph, etc.
- Array:
- Pros: 允許隨機存取
- Cons: 擴容/縮容
- Linked list:
- Pros: 不存在擴容問題
- Cons: 不能隨機存取
- Queue / Stack:
- Array: 擴容/縮容
- Cons: new memory for pointer address
- Graph:
- Adj. matrix (array): Usually faster due to its random access support.
- Adj. List (Linked list): Space efficient for sparse graph.
- Hash table (Hash function's overflow handling):
- Linear probing (線性探測法)= Open Addressing:
- 當兩筆資 x 與 y，代入雜湊函式 H(x) 與 H(y) 之後，若得到相同的雜湊值，則會發生溢位，此時可以將雜湊值依序 + 1，一格一格往後尋找有沒有其它空位，直到找到空位，或是儲存空間皆存滿為止
- 缺點：搜尋空位的時間不穩定，可能會有一堆資料存在附近，要往後找很久才找到空位
- Chaining:
- 雜湊表一開始會在每個位置準備各自的串列，同一個位置可存放多筆資料，以連結串列相接起來
- Tree:
- Array: Heap (complete binary tree with root always < or > sub-nodes)
- Linked list: tree/binary search tree/AVL tree/ red black tree / B tree, etc.

## 1.1.2 資料結構的基本操作
- 資料結構的種類繁多，存在的目的無非在不同的應用場景下，盡可能有效地增、刪、查、改 (CRUD)。
- CURD: creat(增), update(改), read (查), delete(刪)
- 資料結構的尋訪、存取
- 線性: for/while
- 非線性: recursive
- Frameworks:
- Linear: for/while
- Recursive:
- Linked list: pre-order / post-order
- Binary tree: pre order / in order / post order
- graph = N-tree: visited for circle.
## 1.1.3 Guide for leetcode training
- Binary tree first
- Essentially, question is a kind of N-tree traverse
- Recursive question ~= tree questions