# [APCS] 鏈結串列

###### tags: `APCS`

## 鏈結串列的定義和表示法
鏈結串列是一種有序串列（ordered list），各項資料可以儲存在分散的記憶體上。

我們可用兩種方式來表示鏈結串列：
1. 陣列
2. 動態配置

### 陣列表示法
在鏈結串列的陣列表示法中，我們使用兩個陣列分別儲存資料和連結：
* `data`陣列
存放資料
* `link`陣列
存放下一項的位置索引（index）

| | `data` | `link` |
| -------- | -------- | -------- |
|0 | | |
|1|BAT|3|
|2|||
|3|EAT|0|
|4|GAT|6|
|5|||
|6|VAT|1|
|7|CAT|4|

`first` -> CAT -> GAT -> VAT -> BAT -> EAT -> `0`

其中位置0保留來作為指定串列的結尾用，故`data[0]`和`link[0]`也沒有指定值。

在不支援指標的環境中，我們可以使用這種方法來實作鏈結串列，但缺點是記憶體的使用效率不佳（可以注意到陣列中有非常多的空值）。

### 動態配置表示法
使用動態記憶體配置的話，我們不事先配置空間（前面的陣列表示法在宣告陣列的時候就配置了記憶體空間），需要空間的時候配置，不需要的時候再釋放歸還。

## 鏈結串列資料結構
### 串列節點的宣告
在這邊，我們使用模板`template`來讓鏈結串列裡面的資料可以是各種不同的型別，甚至可以是自創的類別。

template <class T>
class ListNode{
friend class LinkedList<T>;  // LinkedList 為鏈結串列本身的類別
private:
    T data;
    ListNode<T> *link;
};

而`LinkedList`類別則宣告如下：

template <class T>
class LinkedList{
public:
    LinkedList(){  // 鏈結串列的建構子
        first = 0;
    }
    // 鏈結串列的其他操作函式放在這裡
private:
    ListNode<T> *first;  // 指向鏈結串列的第一個節點的指標
};

## 鏈結串列上的操作
### 在尾端插入

template <class T>
void LinkedList<T>::InsertBack(const T &e){
// 在 LinkedList 的尾端插入 data 為 e 的節點
    if(first){  // *this 為非空串列
        // 假設最後一個節點的位址已經存在 last 這個指標上了
        last->link = new ListNode<T>(e);
        last = last->link;
    }
    else{  // *this 為空串列
        first = last = new ListNode<T>(e);
    }
}

在這段程式碼裡面，`last->link`相當於`(*last).link`。

### 串接兩個鏈結串列

template <class T>
void LinkedList<T>::Concatenate(LinedList<T> &b){
// 把串列 b 接在 *this 的尾端
    if(first){  // 若 *this 是非空串列
        last->link = b.first;
        last = b.last;
    }
    else{  // 若 *this 是空串列
        first = b.first;
        last = b.last;
    }
    b.first = b.last = 0;  // 把 b 刪除
}

### 反轉鏈結串列
當我們想要把一個串列 $(a_1, a_2, ... a_n)$ 反轉成 $(a_n, a_{n - 1}, ... a_1)$ 的時候，可以使用以下函式：

template <class T>
void LinkedList<T>::Reverse(){
    ListNode<T> *current = first,
                *previous = 0;
    while(current){
        ListNode<T> *r = previous;
        previous = current;
        current = current->link;
        previous->link = r;
    }
    first = previous;
}

### 刪除節點

想刪除一個指定的節點的時候，我們必須先尋訪鏈結串列，直到找到要刪除的那個節點為止。理由是，現在的鏈結串列上的鏈結是單向的，然而刪除時我們必須知道前一個節點的位址（這樣才能斷開這個節點和要刪除的節點的鏈結，並且將它連到待刪節點的下一個節點）。

template <class T>
void LinkedList<T>::Delete(ListNode<T> *x){
    ListNode<T> *current = first,
                *previous = 0;  // 空指標
    while(current != 0 && current != x){
    // 尋訪（traversal）
    // 找到x或current成為空指標，就結束迴圈
        previous = current;
        current = current->link;
    }
    
    if(current == 0){
    // *this為空鏈結串列，或著x不存在*this裡面
    // 擲出例外
        throw "No x in list";
    }
    
    else if(current == first){
    // 要刪除的節點為第一個節點first
        first = current->link;  // 把first一到下一個節點
        delete current;
        current = 0;
        // 刪去指標後讓它指到NULL可避免bug
    }
    else{  // 其餘情況，*this有要刪除的節點且不是first
        previous->link=current->link;
        delete current;
        current = 0;
    }
}

### 複雜度分析
若鏈結串列的長度為 $n$，則顯而易見地，InsertBack和Concatenate是 $O(1)$，而Reverse和Delete因為都牽涉到尋訪，所以是 $O(n)$。

### 陣列和鏈結串列的比較

|| 陣列（array） | 鏈結串列（linked list） |
| -------- | -------- | -------- |
| 佔用記憶體 | 佔用連續記憶體，每個節點佔用空間小 | 不必佔用連續記憶體，但每個節點佔用空間較大（因為需要額外的空間儲存`link`） |
|空間效率|低|高|
|插入/刪除|$O(n)$|$O(1)$ （若不包含尋訪花費的時間）|
|隨機存取|使用位址公式計算，$O(1)$|需尋訪，$O(n)$|
|搜尋|若排序好，可使用二分搜尋法，$O(\log n)$|就算排序好還是只能用尋訪的，$O(n)$|

## 其他種類的鏈結串列
### 單向鏈結串列（singly linked list）
前面講的`LinkedList`類別，都是單向鏈結串列，尋訪時只能由前向後尋訪（單一方向），沒辦法從後面的節點知道前一個節點是誰，因此在刪除節點時必須要透過尋訪，且在尋訪時要使用兩個一前一後的指標（`current`、`previous`）來儲存前一個節點的位址。

### 雙向鏈結串列（doubly linked list）
為了解決「要知道前一個節點需要尋訪」的問題，我們可以在每個節點維護兩個方向的指標：
* 向前（左）：`left`
* 向後（右）：`right`


以下是雙向鏈結串列的ADT：

class DblList;
class DblListNode{
friend DblList;
private:
    int data;
    DblListNode *left, *right;
};

class DblList{
public:
    // 串列操作函式...
private:
    DblListNode *first;  // 指向第一個節點（header）
};

#### 雙向鏈結串列上的刪除

void DblList::Delete(DblListNode *x){
    if (first == 0 || x == 0){
        throw "List is empty or no node to delete";
    }
    if (first == x){  // 若要刪除的是第一個節點
        first = x->right;
    }
    if (x->right != 0){  // 若要刪除的不是最後一個節點
        x->right->left = x->left;
    }
    if (x->left != 0){  // 若要刪除的不是第一個節點
        x->left->right = x->right;
    }
    delete x;
}

* 複雜度分析：
不包含迴圈、不涉及尋訪，故時間複雜度為 $O(1)$。但和單向鏈結串列相較之下，涉及較多的指標更動。

#### 雙向鏈結串列上的插入

void DblList::Delete(DblListNode *p, DblListNode *x){
// 把節點x插入到節點p後面（右邊）的位置
    if (p == 0){  // 節點p不存在，擲出例外
        throw "Previous node cannot be NULL";
    }
    x->right = p->right;
    p->right = x;
    x->left = p;
    if (x->right != 0){
        x->right->left = x;
    }
}

* 複雜度分析：
和刪除相似，時間複雜度為 $O(1)$。

#### 單向鏈結串列和雙向鏈結串列的比較

| | 單向鏈結串列 | 雙向鏈結串列 |
| -------- | -------- | -------- |
| 鏈結 |一個欄位（較省空間）| 兩個欄位（較費空間）|
|移動方向|單向|雙向|
|插入/刪除|要額外提供前一節點之指標，故需尋訪，時間複雜度 $O(n)$，但需要改變的鏈結數量較少|不用額外提供前一節點之指標，已儲存在資料結構當中，所以不需尋訪，時間複雜度 $O(1)$，但要改變的鏈結數量較多|

### 循環鏈結串列（circular linked list）
最後一個節點和第一個節點相互鏈結的鏈結串列。

#### 優點和缺點
* 優點
* 從任意節點開始尋訪，皆可以通過串列上的全部節點
* 釋放全部串列的節點至儲存池（storage pool），只需要花費 $O(1)$ 時間
* 缺點
* 須維持最後一個節點指向第一個節點之特性（也就是說，要維護的指標更多了）