# Data structure  資料結構

# 簡介 Intro

在開始講演算法的最入門，需要先講講資料結構。不同的資料結構，延伸出了不同的演算法。
這邊先列舉幾個常見的資料結構：

- Linear data structures 線性資料結構
  - List 列表
  - Array 陣列
  - Queue 佇列
  - Stack 堆疊
- Tree 二元樹
  - Heap 堆積
- Hash Table 雜湊表
- Graph 圖

## Linear Structure 線性結構

### List 列表

List 是將資料排成一直線，易於添加和刪除，但要存取資料卻很費時。此種資料結構具有順序性，不具有唯一性(資料可重複)。

前一筆資料，會使用指標(Pointer)指向下一筆資料的記憶體位址。當要添加或刪除資料時，只需要將前一筆的指標修改，並將當前資料的指標也做修改。

可是當要存取某一筆資料時，卻需要從開頭一筆一筆找下來，所以其複雜度會到 `O(n)`。

- Add / Delete：`O(1)`
- Get：`O(n)`

![List](https://upload.wikimedia.org/wikipedia/commons/3/37/Singly_linked_list.png?1630726014795)

List 只是基本的資料結構，它還有其他延伸的結構：

- Circular list 循環列表
- Bidirectional list 雙向列表：前後筆資料會互相指向

### Array 陣列

類似 List，但是更方便存取，添加和刪除較費力。資料是依序儲存在連續的記憶體位址，因此能用索引來計算記憶體位址，直接存取每個資料。

```text
a[0]  a[1]  a[2]
Blue Yellow Red
```

要添加或刪除資料時，需要將後面的資料都做移動，才能將資料添加到該索引或是移除該資料

- Add / Delete：`O(n)`，修改時的複雜度，最差情況下是從陣列的開頭修改
- Get：`O(1)`，存取時的複雜度，因為可用索引直接讀取

### Stack 堆疊

與 List 和 Array 類似，都是將資料排成一列，但是只有一個方面的開口

可以想像堆疊是一個紙箱，資料是由下往上增加，只能從最新增加的資料(紙箱最上層)開始存取。其原理是「後進先出」Last In First Out(LIFO)

增加資料稱為 `push`，取出最上一筆資料稱為 `pop`。

### Queue 佇列

Queue 也是將資料排成一列，其概念類似於排隊。只能從後面添加、從前面移除。不能從中間修改。其原理是「先進先出」First In First Out(FIFO)

增加資料稱為 `enqueue`，取出最新一筆資料稱為 `dequeue`

## Hash Table 雜湊表

雜湊函數：主要是將不定長度訊息的輸入，演算成固定長度雜湊值的輸出，且所計算出來的雜湊值必須符合兩個主要條件：

- 由雜湊值是無法反推出原來的訊息
- 雜湊值必須隨內容改變而改變

Hash Table 是儲存成對資料的結構之一。資料為成對的「鍵 Key」和「值 Value」。用雜湊函數運算出來的雜湊值，根據鍵 (key) 來儲存在資料結構中。而存放這些記錄的陣列就稱為雜湊表。

## Tree Structure 樹狀結構

### Binary Tree 二元樹

樹狀結構的資料結構之ㄧ，有兩個特性。

1. 所有節點上的值都會**大於**連結在其左側子節點的值
2. 所有節點上的值都會**小於**連結在其右側子節點的值

依照這兩個特性，可以知道最小值，會在最左側。最大值會在最右側。

#### 刪除資料

1. 情境ㄧ：刪除沒有子節點的節點，直接刪除即可
2. 情境二：刪除只有一個子節點的節點，將子節點替換上來被刪除的節點即可
3. 情境三：刪除有兩個子節點的節點，將被刪除節點的左側子節點中的最大值替換即可

### Heap 堆積

Heap 是樹狀結構之一，用於實踐「優先佇列」(priority queue)。堆積的每個節點最多可以擁有兩個子節點。資料從最上層開始添加、同一層左方開始。其子節點的資料必定要大於父節點。

資料依 1, 3, 6, 4, 8, 7 順序加入

```text
      1
     /  \
   3    6 
  / \   /
4  8 7
```

現在要添加資料 5，依照順序會加到 6 的右側子節點。但是因為父節點不能比子節點。所以 5 和 6 需要對調

```text
      1
     /  \
   3    5 
  / \   / \
4  8 7  6
```

## Graph Structure 圖形結構