關於線性串列(Linear list)本篇將討論以下幾個項目
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
