# 資料結構&演算法 3. 線性串列

###### tags: `資料結構&演算法`

## 關於線性串列(Linear list)本篇將討論以下幾個項目
:::info
### 1. 什麼是線性串列(Linear list)？
### 2. Array (陣列)
### 3. Linked List (鏈結串列、鏈表)
### 4. 比較 Array & Linked List
:::

---
## 測試環境：
> OS：Windows 10
> IDE：Visual Studio 2019

---
## 1. 什麼是線性串列(Linear list)？
### 簡單來說，就是將資料元素排成一列，每個元素「最多」只和左、右元素相鄰


---
## 2. Array (陣列)
### 特性：
> ### 1. 使用連續的記憶體空間
> ### 2. 相同型別的資料元素
#### 範例：


上圖 Array a 為型別 int 且內含 10 個元素
### 優點：高效率的隨機訪問
上述兩個特性使 Array 能高效率的「隨機訪問」，透過簡單的計算就能快速取得 Array 中第 n 個元素的位置

// a[n]的記憶體位置 = 第一個元素的記憶體位置 + n * 資料大小

時間複雜度：O(1)

### 缺點：Insert & Delete 效率很差
因為 Array 儲存於連續的記憶體空間，使得 Insert & Delete 效率很差
#### 範例 1：


### Array Insert 三步驟：
> #### 假設 Array 長度 n，且 0 ≤ i ≤ n
> #### 1. a[i] 之後元素(a[i+1] ~ a[n])全部往後挪一個位置
> #### 2. 將欲寫入元素放入 a[i]
> #### 3. 記憶體位置保持連續
#### 範例 2：


### Array Delete 三步驟：
> #### 1. 刪除 a[i] 元素
> #### 2. 將 a[i] 之後元素(a[i+1] ~ a[n])全部往前挪一個位置
> #### 3. 記憶體位置保持連續

時間複雜度：

    1. 最好情況：O(1)

    2. 最壞情況：O(n)

    3. 平均情況：O(n)


最好情況：
    
    1. Insert 至 Array 最後(a[n+1])
    2. Delete Array 最後一個元素(a[n])


最壞情況：
    1. Insert 至 Array 第一個位置(a[1])
    2. Delete Array 第一個元素(a[1])

---
## 3. Linked List (鏈結串列、鏈表)
### 特性：
> ### 1. 不需要連續的記憶體空間
> ### 2. 使用指標紀錄相鄰結點位置
### 在分析優缺點之前，我們先來介紹三種常見 Linked List：
> ### 1. 單向鏈結串列
> ### 2. 環狀鏈結串列
> ### 3. 雙向鏈結串列
### 1. 單向鏈結串列：


如上圖，除了原本結點的資料(a1、a2、a3)外，還包含了紀錄下一個結點位置的，後繼結點指標「RLink」

頭結點「Head」中記錄著 Linked List 的起始位置，在最末結點 a3 將後繼結點指標 RLink 指向「null」，來表示這是 Linked List 的最後一個結點

### 2. 環狀鏈結串列：


基本上與單向鏈結串列相同，除了最末結點 a3 的後繼結點指標 RLink 並非指向「null」而是指向頭結點 a1 的位置

### 3. 雙向鏈結串列：


比起環狀鏈結串列，除了紀錄後繼結點位置外，再多了一個紀錄前一結點位置的，前驅結點指標「LLink」
### 優點：高效率的 Insert & Delete
因為不使用連續記憶體空間，而是記錄下一個結點的記憶體位置，沒有搬移資料的問題，所以在 Insert/Delete 上有較高的效率

時間複雜度：O(1)

### 缺點：隨機訪問效率很差
不連續的記憶體空間使 Linked List 必須以遍歷方式進行「隨機訪問」，透過逐項取得後繼結點指標 RLink 找到第 n 個元素的位置

使用指標方式儲存後繼(前驅)結點位置，使得即便是相同資料亦需使用更多的記憶體空間來儲存

時間複雜度：O(n)

#### 範例 1：


### Linked List Insert 三步驟：
> #### 假設 Linked List 長度 n，且 0 ≤ i ≤ n
> #### 1. a[i-1] 的後繼結點指標 RLink 改為指向新元素
> #### 2. 新元素的後繼結點指標 RLink 指向原 a[i]
> #### 3. 完成 Insert 且無須連續記憶體空間
#### 範例 2：


### Linked List Delete 兩步驟：
> #### 1. a[i-1] 後繼結點指標 RLink 改為指向 a[i+1]
> #### 2. 完成 Delete 且無須連續記憶體空間

---
## 4. 比較 Array & Linked List


上表中很容易可以看出兩者的時間複雜度剛好相反，不過實際應用時不能單看時間複雜度就決定使用哪一種結構

像是 Array 必須在創建實體時就決定容量，創建後不論有沒有使用都會占用著記憶體空間，Linked List 則是能輕易的動態調整容量等等差異

實際應用時應多比較分析後再決定使用 Array 或是 Linked List

---
## 總結
### 本篇以了解特性的角度來介紹了 Array 跟 Linked List，相信許多人平常都是直接使用習慣結構或是使用各語言包裝過後的(例：C# List<T>)，對兩者差異或是底層實作並不熟悉，讀完本篇後應該對兩者有了更多的認識。

---

## 新手上路，若有錯誤還請告知，謝謝