---
# System prepended metadata

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

---

# 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