## 定義
Linked List 鏈結串列是線性的資料結構，並且可以根據當前元素得知前後元素
所有元素串在一起，好像是鎖鏈一樣，相鄰元素一環扣一環，所以叫做鏈結串列
相較於最基礎的線性結構-array，Linked List 的插入、刪除和空間大小比較靈活
複習一下，若我們想在 array 中做到插入、刪除，那時間複雜度會是 $O(n)$
而 Linked List 在處理某個節點時，只會影響到前後兩個節點
所以在插入與刪除的過程中，完成操作只需要時間複雜度 $O(1)$
不過也因為這種特性，假設我們需要找第 $i$ 個元素，不能直接查詢
需要從第 $0$ 個然後去找第 $1$ 個接著找第 $2$ 個，以此類推
所以查詢第 $i$ 個元素的時間複雜度會是 $O(n)$
只要在不需要查詢位置的情況下，插入與刪去的效率就會比陣列操作更快
要達成這樣的操作，每個元素除了紀錄自己本身的值還需要紀錄前後的節點
而且為了方便在空串列的情況下快速的初始化，我們可以多加兩個節點
一個節點是 head，一個是 tail，分別代表整個串列的最開頭與最尾端
(提供一個比喻: 像是小吃攤的老闆，與最後方舉著還要xx分鐘的實習生)
(老闆面前就是第一個顧客，實習生旁邊就是最後一個客人)

## Linked List 陣列實作
在比較簡單的實作上，我們可以偷懶用多個陣列去實現這個功能
因為比賽或檢定大部分是有限制時間的，不太可能用指標實作，以下是陣列實作的程式碼

#include<bits/stdc++.h>
using namespace std ;

int num[100], nxt[100], pre[100] ;
int head = 0, tail = 99, pt ;

void init_list() {
    pt = 1 ; // 因 head 是 0
    nxt[head] = tail ;
    pre[tail] = head ;
}

void go() { // 遍歷並輸出裡面的所有元素
    for (int now=nxt[head];now!=tail;now=nxt[now])
        cout << num[now] << ' ' ;
    cout << '\n' ;
}

int find_i(int i) { // 找到第 i 個元素
    int now = head, idx = i ;
    while (i--)
        now = nxt[now] ;
    return num[now] ;
}

void erase_i(int i) { // 刪除第 i 個元素
    int prev = find_i(i-1) ;
    int next = nxt[nxt[prev]] ;
    nxt[prev] = next ;
    pre[next] = prev ;
}

void insert_i(int value, int i) { // 插入到第 i 個元素原本的位置
    int prev = find_i(i-1) ;
    int now = nxt[prev] ;
    nxt[prev] = pre[now] = value ;
    pre[pt] = prev ;
    nxt[pt] = now ;
    num[pt] = value ;
    pt++ ;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;
    int n, x ; // 總共有 n 個節點 每個節點的值是 x
    cin >> n ;

    init_list() ;
    for (int i=0;i<n;i++) { // 插入到最後方
        cin >> x ;
        insert_i(x, pt) ;
    }

    go() ;

    int now = find_i(3) ; // 找到第三項
    cout << "index 3 is " << now << '\n' ;

    erase_i(3) ; // 清除第三項
    go() ;
    return 0 ;
}

這段程式碼有很多功能沒有實現，因為只是想做到上面三個功能而已
較為正確的作法會是，在每次需要新的節點(需要插入某個節點)時，使用 new
在 C 語言中會需要用 malloc() 來處理，某些細節不太一樣，但都是動態分配記憶體
這樣就可以讓儲存空間的使用達到最好的利用，能插入的次數也不會被固定
但是這樣的方式也會比較慢，因為需要動態分配記憶體，效率不高
而且主要還分成幾種概念，下面會一一介紹，但最後只會實作一種
1. 單向 Linked List (只能往後或往前)
2. 雙向 Linked List (可同時往後與往前)
3. 循環 Linked List (頭尾相連)

## Linked List 陣列實作-單向 Linked List
單向 Linked List 占用的空間最小，因為只有一個方向，所以每一個節點都可以少一個指標
以下就是只能往後的陣列實作，在插入最前方的功能比較簡單，因為能直接放在 head 後方

#include<bits/stdc++.h>
using namespace std ;

struct node {
    int value ;
    node* next ;
} ;

void init_List(node* head, int* lenp) { // 初始化
    head->next = NULL ;
    *lenp = 0 ;
    return ;
}

node* find_before(node* head, node* prt) { // 找到元素 ptr 前方的元素
    while (head->next != prt)
        head = head->next ;
    return head ;
}

void insert_node(int x, node* nd, int* lenp) { // 插在 nd 後方
    // 定義新節點
    node* new_node = new node ;
    new_node->value = x ;
    new_node->next = nd->next ;

    // 修改前節點
    nd->next = new_node ;
    (*lenp)++ ;
    return ;
}

void print_node(node* head) { // 輸出所有節點
    node* now = head->next ;
    while (now != NULL) {
        cout << now->value << ' ' ;
        now = now->next ;
    }
    cout << '\n' ;

    return ;
}

void delete_node(node* ptr1, node* ptr2, int* lenp) { // 刪除節點 ptr2
    // 更新前節點
    ptr1->next = ptr2->next ;

    // 刪除節點
    (*lenp)-- ;
    delete ptr2 ;
    return ;
}

int main() {
//    ios::sync_with_stdio(0), cin.tie(0) ;

    int len = 0 ;
    node* head = new node ;
    init_List(head, &len) ;

    int n, x ;
    cin >> n ;
    for (int i=0;i<n;i++) {
        cin >> x ;
        node* nback = find_before(head, NULL) ;
        insert_node(x, nback, &len) ;
    }
    cout << "The size of Linked List is " << len << '\n' ;

    print_node(head) ;

    node* nback = find_before(head, NULL) ;
    node* bback = find_before(head, nback) ;
    delete_node(bback, nback, &len) ; // 刪除 nback (最尾端元素)
    print_node(head) ;
    return 0 ;
}

要加入 tail 讓實作更容易也可以，記得要注意 head 跟 tail 的更新就好
最典型的應用就是模擬 stack，top 放在 head 後方，最下面的元素就是 tail
## Linked List 陣列實作-雙向 Linked List
雙向 Linked List 需要注意插入、刪除時的前後節點操作，功能相對完整一點

#include<bits/stdc++.h>
using namespace std ;

struct node {
    int value ;
    node* next ;
    node* prev ;
} ;

void init_List(node* head, node* tail, int* lenp) { // 初始化
    head->next = tail ;
    tail->prev = head ;
    head->prev = tail->next = NULL ;
    *lenp = 0 ;
    return ;
}

node* find_from_head(node* head, int idx, int len) { // 從 head 開始 find
    if (idx > len) {
        cout << "can't find index: " << idx << '\n' ;
        return NULL ;
    }

    node* now = head ;
    while (idx--)
        now = now->next ;
    return now ;
}

node* find_from_tail(node* tail, int idx, int len) { // 從 tail 開始 find
    if (idx > len) {
        cout << "can't find index: " << idx << '\n' ;
        return NULL ;
    }

    node* now = tail ;
    while (idx--)
        now = now->prev ;
    return now ;
}

void insert_back_node(int x, node* nd, int* lenp) { // 插在 nd 後方
    // 定義新節點
    node* new_node = new node ;
    new_node->value = x ;
    new_node->prev = nd ;
    new_node->next = nd->next ;

    // 修改前後方節點
    nd->next->prev = new_node ;
    nd->next = new_node ;
    (*lenp)++ ;
    return ;
}

void insert_front_node(int x, node* nd, int* lenp) { // 插在 nd 前方
    // 定義新節點
    node* new_node = new node ;
    new_node->value = x ;
    new_node->next = nd ;
    new_node->prev = nd->prev ;

    // 修改前後方節點
    nd->next->prev = new_node ;
    nd->prev = new_node ;
    (*lenp)++ ;
    return ;
}

void print_node(node* head, node* tail) { // 輸出所有節點
    node* now = head->next ;
    while (now != tail) {
        cout << now->value << ' ' ;
        now = now->next ;
    }
    cout << '\n' ;

    return ;
}

void delete_node(node* nd, int* lenp) { // 刪除節點 nd
    if (nd == NULL) {
        cout << "can't delete NULL node\n" ;
        return ;
    }
    node* bk = nd->prev ; // back nd
    node* ft = nd->next ; // front nd

    bk->next = ft ;
    ft->prev = bk ;

    // 刪除節點
    (*lenp)-- ;
    delete nd ;
    return ;
}

int main() {
//    ios::sync_with_stdio(0), cin.tie(0) ;

    int len = 0 ;
    node* head = new node ;
    node* tail = new node ;
    init_List(head, tail, &len) ;

    int n, x ;
    cin >> n ;
    for (int i=0;i<n;i++) {
        cin >> x ;
        node* nback = tail->prev ; // 插入到最後方
        insert_back_node(x, nback, &len) ;
    }
    cout << "The size of Linked List is " << len << '\n' ;

    print_node(head, tail) ;

    node* nd1 = find_from_head(head, 3, len) ;
    delete_node(nd1, &len) ; // 刪除 nd1
    print_node(head, tail) ;

    node* nd2 = find_from_tail(head, 5, len) ;
    delete_node(nd2, &len) ; // 刪除 nd1

    print_node(head, tail) ;
    return 0 ;
}

典型例子是文字編輯時可以往上(下)，home 回到最上端，end 回到最下端，對應 head、tail

---
由於循環 Linked List 從雙向 Linked List 改一下就行(head 跟 tail 相連)
其典型例子是大富翁的地圖，大富翁的地圖跑完會回到起點，至於是否雙向取決於想要實現的功能

## 常見錯誤
一般在寫 Linked List 有幾個常見的錯誤，由於 debug 起來比較複雜，所以這裡整理起來
1. 忘記釋放記憶體(使用 delete)
2. 指標更新錯誤(在插入、刪除時)
3. 使用未初始化或值為 NULL 的指標
4. 無限迴圈

第一點，雖然我上方沒有特別去做，但是在"之後完全用不到指標"的時候，就應該將記憶體釋放掉
比如程式碼最後就必須將 head、tail 給釋放掉，還有在刪除節點時必須將該節點記憶體釋放掉
第二點可以透過重新推理當前節點與前後節點共三個節點在更新前後的關係，可以透過輸出值來 debug
第三點只要記得任何需要加入 Linked List 的新節點，都必須先初始化
然後可以用 if 去判斷當前的指標值是否是 NULL，來避免使用到 NULL
第四點只有在循環 Linked List 時使用，可以透過中斷點判斷來避免
中斷點可以是一個新的參數，也可以是 head、tail，也是搭配 if 使用

## Linked List 和 array 的複雜度比較
假設結構的長度為 $n$，以下是 Linked List 和 array 的時間複雜度比較

| | 插入 | 刪除 | 查找 | 第 $i$ 個元素 | 遍歷 |
| ----------- | ---- | ---- | ---- | --- | ---- |
| Linked List | O(1) | O(1) | O(n) | O(n) | O(n) |
| Array | O(n) | O(n) | O(n) | O(1) | O(n) |

從以上表格就可以得知
如果要大量插入(刪除)的操作/新增空間，就使用 Linked List
若只需要用固定空間，查找第 i 個元素，不需要插入與刪除的操作，就使用 Array
當然，如果只需要拓展空間但不需要插入(刪除)，那就只需要用 vector
至於空間複雜度都是 $O(n)$，但 Linked List 可以動態調整空間大小，不過實際使用空間較大

## 進階-XOR Linked List
首先要一些背景知識，$A\oplus0 = A$、$A\oplus B =C$、$C \oplus A = A \oplus B \oplus A = A \oplus A \oplus B = B$
這些背景知識前面說過的雙向 Linked list 需要兩個指標去紀錄前後的地址
如果節點數量很大，花費的空間也會跟著變多，於是就出現用 XOR 特性紀錄地址
所謂的 XOR Linked List 就是將兩個指標用 XOR 縮減成一個指標 neighbors
`neighbors = next ^ prev`，不過知道怎麼結合也要知道如何拆開
因為本質上我們還是需要單獨用到 prev 或 next 去執行運算
這時候背景知識就會用上了，`next ^ prev ^ prev == next`
反之也是一樣，所以當我們需要 next，就做 `prev ^ neighbors`
如果我們需要的是 prev，就做 `next ^ neighbors`
其餘的部分就跟雙向 Linked List 差不多，主要就差在這個概念
唯一比較需要注意的是，地址本身不能做 XOR，需要用兩次強轉 type 去完成操作
`(Node*)((uintptr_t)node->nei ^ (uintptr_t)bnei) ;`
以下是 C++ 參考範例，實際結構、功能需要根據需求去做更改，通常不能直接複製貼上(與 C 有差異)

#include<bits/stdc++.h>

struct Node { // Linked List 的結構
    int data ;
    Node* nei ; // neighbors
} ;

// 初始化
void Init_XOR_Linked_List(Node* head, Node* tail) {
    head->nei = tail ;
    tail->nei = head ;

    return ;
}

// 找出 node 的 next、prev，取決於你輸入的 bnei
Node* Run_Node(Node* node, Node* bnei) {
    return (Node*)((uintptr_t)node->nei ^ (uintptr_t)bnei) ;
}

// 設立新節點，需輸入 neighbors
Node* New_Node(Node* nei, int data) {
    Node* new_node = new Node ;
    new_node->data = data ;
    new_node->nei = nei ;
    return new_node ;
}

// 在 node 後方插入新 node，prev 是 node 前方 node 的地址
void Insert_After(Node* node, Node* prev, int data) {
    Node* next = Run_Node(node, prev) ;
    Node* newNode = New_Node((Node*)((uintptr_t)next ^ (uintptr_t)node), data) ;

    node->nei = (Node*)((uintptr_t)prev ^ (uintptr_t)newNode) ;
    return ;
}

// 移除 node，prev 是 node 的前一個節點
void Remove_Here(Node* node, Node* prev) {
    struct Node* next = Run_Node(node, prev);

    // 將前後兩 node 連接
    prev->nei = (Node*)((uintptr_t)prev->nei ^ (uintptr_t)node ^ (uintptr_t)next);
    next->nei = (struct Node*)((uintptr_t)next->nei ^ (uintptr_t)node ^ (uintptr_t)prev);

    delete node ;
    return ;
}

// 反轉區間 [L, R] 內所有節點，prev 是 L 前方的 node，next 是 R 後方的 node
void Reverse(struct Node* prev, struct Node* L, struct Node* R, struct Node* next) {
    prev->nei = (Node*)((uintptr_t)prev->nei ^ (uintptr_t)L ^ (uintptr_t)R) ;

    L->nei = (Node*)((uintptr_t)L->nei ^ (uintptr_t)prev ^ (uintptr_t)next) ;
    R->nei = (Node*)((uintptr_t)R->nei ^ (uintptr_t)next ^ (uintptr_t)prev) ;

    next->nei = (Node*)((uintptr_t)next->nei ^ (uintptr_t)R ^ (uintptr_t)L) ;
    return ;
}

int main() {
    Node* head ;
    Node* tail ;

    Init_XOR_Linked_List(head, tail) ; // 初始化
    return 0 ;
}

## 例題-ZJ n371. 5. 隔山打牛
[題目連結](https://zerojudge.tw/ShowProblem?problemid=n371)
解題思路 :
基本上要在比賽這種限定時間的場合下，不太可能搓出功能完整的 Linked List
所以只要有需要的功能即可，比如這題就是只要能夠找到某節點往後的第二個節點
所以我們只需要單向無循環串列，並且因為我們需要輸出的是師傅的編號
其實對於所有節點來說，所謂的編號就是節點本身的 index，所以編號也不需要額外紀錄
我們用一個陣列 $A$ 去紀錄下一個師傅的編號，這樣的方式會有如下表格

| index | 1 | 2 | 3 | 4 | ... | n |
| ----- | --- | --- | --- | --- | --- | --- |
| value | 2 | 3 | 4 | 5 | ... | n+1 |

對於師傅 $x$ 來說，下一個師傅的 index 是 `A[i]`，下下一個是 `A[A[i]]`
這樣就可以很容易地知道要打的師傅的 index，接下來要處理特例
對於倒數第一與倒數第二的師傅，他們都沒辦法打到師傅
可以設立一些特殊值來代表原本就沒有師父的位置，比如 $-1$
而對於被擊倒的師傅，我們也可以設立一個特殊值 $0$
接著說一下刪除的部分，單向串列的節點刪除會影響到前一個節點
因為前一個節點 $N$ 的"下一個節點"要更新成原本 $N$ 的下下一個節點
這裡意思就是 `A[i]` 必須更新成 `A[A[i]]`，`A[i] = A[A[i]]`

#include<bits/stdc++.h>
using namespace std ;

int nxt[1000005] ; // List 指向下一個節點
int n, m ;

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    cin >> n >> m ;
    for (int i=1;i<=n+1;i++) // 初始化 List
        nxt[i] = i+1 ;

    int x ;
    for (int i=0;i<m;i++) {
        cin >> x ;

        int &ans = nxt[nxt[x]] ;    // 被刪除節點的 index
        if (nxt[x] == 0)                // x 已被刪除
            cout << "我大意了啊~沒有閃\n" ;
        else if (nxt[x] > n || ans > n) // 超出範圍
            cout << "來~ 騙\n" ;
        else {
            cout << ans << '\n' ;
            int tmp = ans ;
            ans = nxt[ans] ; // 修改 x 的下一個節點
            nxt[tmp] = 0 ; // 被刪除的節點當作 0
        }
    }
    return 0 ;
}

## 例題-ZJ i524. 11988: Broken Keyboard
[題目連結](https://zerojudge.tw/ShowProblem?problemid=i524)
解題思路 :
這題主要是要將字串存入 Linked List，然後插入分為開頭、結尾、順序
如果遇到左括號就是插入開頭，右括號插入結尾，其餘根據順序插入
假設我們的插入是插入到某節點 $X$ 後方，那前面的三種就是去改變 $X$
最後遍歷 Linked List 裡儲存的字串，一一輸出

#include<bits/stdc++.h>
using namespace std ;

int nxt[100005], head, tail, len, idx ;
string ss[100005] ;

void init() { // 初始化 List
    head = 0, tail = 1, idx = 2 ;
    nxt[head] = tail ;
}

int insert_f(string& s, int pt) { // 插入到 pt 後方
    ss[idx] = s ;        // 新節點的 string
    nxt[idx] = nxt[pt] ; // 更新 新節點
    nxt[pt] = idx ;      // 更新 舊節點

    return idx++ ;       // 下一個(可能存在)新節點編號
}

int insert_b() { // 找到 tail 的前一個節點
    int pt = head ;
    while (nxt[pt] != tail)
        pt = nxt[pt] ;

    return pt ;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    string s ;
    while (cin >> s) {
        string now = "" ;
        init() ;
        len = s.size() ;
        int pt = head ;
        for (int i=0;i<len;i++) {
            if (s[i] == '[' || s[i] == ']') { // 字串結束
                insert_f(now, pt) ; // 插入
                if (s[i] == '[')    // 回到開頭
                    pt = head ;
                else                // 到最後面
                    pt = insert_b() ;
                now = "" ;
            }
            else
                now += s[i] ;      // 更新字串
        }
        insert_f(now, pt) ; // 最後一個字串結束後插入
        pt = nxt[head] ;    
        while (pt != tail) { // 從頭遍歷
            cout << ss[pt] ;
            pt = nxt[pt] ;
        }
        cout << '\n' ;
    }

    return 0 ;
}

## c073. 00101 - The Blocks Problem
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c073)
解題思路 :
移動 $a$ (或 $a$ 與其上方所有節點) 到 $b$ (或 $b$ 最上方的節點)
基本上是可以當作兩個 Linked List 串在一起，所以每個節點一開始都是一個 Linked List
而 "將 $n$ 節點上方所有節點都回歸原位"，就是字面意義上的操作
所以題目要求的四個操作基本上可以用三種操作完成
1. 將某點上方的所有節點回歸原位
2. 找到在 $b$ 上方的節點中，最上方的那個節點
3. 將兩個節點串在一起

比如 "move $a$ onto $b$" 就是做 $1_a、1_b \rightarrow 3_{a,b}$ 其他操作也是這種概念
而且因為 head、tail 本身不儲存值，所以全部的 Linked List 可以共用
(可以用畫圖去幫助理解、畫一個圖表示共用、轉移過程、回歸原位等等的操作)
還有一個要求是"如果兩個節點在同一堆積木中，當作無效操作"
這個只要去找某個節點上方是否有另一個節點，不過我這裡是用找根的概念
把每一堆積木最下方的積木當成根，然後用一個陣列儲存每個節點的根
只要判斷根是否相同就可以知道兩節點是否在同一堆積木當中

#include<bits/stdc++.h>
using namespace std ;
vector<int> nxt(25), pre(25), rot(25) ;
int head = -2, tail = -1 ;

void init(int n) { // 初始化
    for (int i=0;i<n;i++)
        nxt[i] = tail, pre[i] = head, rot[i] = i ;
    return ;
}

void clear_over(int n) { // 清除 n 上方所有 node
    int pt = nxt[n] ;
    nxt[n] = tail ; // 調整 n 節點上方

    // 把 n 上方的所有點都放回桌上
    while (pt != tail) {
        int npt = nxt[pt] ;
        nxt[pt] = tail ;
        pre[pt] = head ;
        rot[pt] = pt ;
        pt = npt ;
    }
    return ;
}

void move_node(int a, int b) { // move a onto b in tree r
    if (pre[a] != head) // 更新 a 下方的點
        nxt[pre[a]] = tail ;

    nxt[b] = a, pre[a] = b, rot[a] = rot[b] ;
    int pt = nxt[a] ;
    while (pt != tail) {
        rot[pt] = rot[b] ;
        pt = nxt[pt] ;
    }
    return ;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    int n ;
    while (cin >> n && n) {
        init(n) ; // 初始化
        string s1, s2 ;
        while (cin >> s1 && s1 != "quit") {
            int a, b, pt ;
            cin >> a >> s2 >> b ;
            if (a == b || rot[a] == rot[b])
                continue ;
            pt = b ;
            if (s2 == "onto")   // clear b
                clear_over(b) ;
            else {               // pt 到 b 最上面的頂點
                while (nxt[pt] != tail)
                    pt = nxt[pt] ;
            }
            if (s1 == "move")   // clear a
                clear_over(a) ;

            move_node(a, pt) ; // 連接節點
        }
        for (int i=0;i<n;i++) {
            cout << i << ": " ;
            int pt = i ;
            if (rot[i] == i) {
                while (pt != tail) {
                    cout << pt << ' ' ;
                    pt = nxt[pt] ;
                }
            }
            cout << '\n' ;
        }
    }

    return 0 ;
}