3. 線性串列

關於線性串列(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

總結

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

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