【C++】競程筆記（資料結構：linked-list）
===

[TOC]

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

鏈結串列（linked-list）
---

一般的陣列會是在連續的記憶體空間中儲存資料，而鏈結串列雖與陣列同為線性資料結構，但他可以將資料儲存在一個 ***不連續***（non-contiguous） 的記憶體空間中。

linked-list 的定義為數個節點（nodes）的集合，而一個節點就由兩個成員所組成，也就是值跟前後的指標（value and previous / next pointer）。

linked-list 可以有三種型態：

1. 單向鏈結串列（Singly Linked List）
2. 雙向鏈結串列（Doubly Linked List）
3. 循環鏈結串列（Circular Linked List）

那首先最簡單的當然就是單向的 linked-list 了，要如何簡單的理解 linked-list 呢？就如同上課傳紙條一樣，假設有一排座位，某個同學要傳紙條到最前面的同學，勢必要點他前面同學的肩膀叫他接力下去，就有點像下圖那樣：


圖：作者繪製

Head 就是這個鏈結串列的開頭，A 同學經過一連串的同學接力傳紙條後，直到傳給 F 同學為止，而最終鏈結串列結束時要指向空指標 NULL，此時我們可以假設講台是 NULL。

那在這時候（「單向」的鏈結串列）只能朝向一個方向，也就是 Next，並不能往前（Previous）。

而雙向鏈結串列就有點像是點同學肩膀然後那個同學回頭一樣，多了一個往前（Previous）的動作，像是往回看點人的同學，如下圖：


由於雙向鏈結串列多了 Prev 的動作，所以 A 作為開頭也能做 Prev 的動作，只不過 Prev 後就沒東西了，所以是 NULL。

最後是循環鏈結串列，其實他跟單向鏈結串列差不多，只是跑到最後一個節點會回到第一個節點去。

一樣是舉傳紙條的例子，傳到最後一個人的時候，F 同學可能看到某些勁爆的內容，很生氣地把紙條丟回去給 A 同學 XD。


### C++ 實作鏈結串列
---

可用 OOP 實作。

初始化一個節點（Node），包含 data、pointer。

#include <iostream>
using namespace std;

class Node {
public:
    int data;       // 儲存節點資料
    Node* next;     // 指向下一節點

    // 建構子：初始化資料與指標
    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

基本操作：

1. 串列頭插入節點

void insertAtHead(int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
}

把新節點的 next 指向原本的 head，再更新 head 就行。

2. 串列尾插入節點

void insertAtTail(int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

要先遍歷完整個鏈結串列，直到最後一個節點，把 next 指向新節點；若串列為空，則直接更新 head 就好。

3. 刪除串列之頭節點

直接將 head 指向 head->next，並釋放原本的頭節點記憶體。

void deleteHead() {
    if (head == nullptr) return;
    Node* temp = head;
    head = head->next;
    delete temp;
}

4. 遍歷鏈結串列並且印出

void printList() {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

遍歷由 head 開始，依序存取每個節點的 data，直到節點指標為 nullptr 為止。

最後我們把它合起來變成一個完整的程式碼，如下：

#include <iostream>
using namespace std;

// 節點類別
class Node {
public:
    int data;
    Node* next;
    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

// 鏈結串列類別
class LinkedList {
private:
    Node* head;

public:
    LinkedList() { head = nullptr; } // 建構子

    // 在頭插入
    void insertAtHead(int value) {
        Node* newNode = new Node(value);
        newNode->next = head; // 等同 (*newNode).next = head;
        head = newNode;
    }

    // 在尾插入
    void insertAtTail(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) temp = temp->next;
        temp->next = newNode;
    }

    // 刪除頭節點
    void deleteHead() {
        if (head == nullptr) return;
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    // 刪除指定位置節點（1-based）
    void deleteAtPosition(int pos) {
        if (head == nullptr || pos < 1) return;
        if (pos == 1) {
            deleteHead();
            return;
        }
        Node* current = head;
        for (int i = 1; i < pos - 1 && current->next != nullptr; i++) {
            current = current->next;
        }
        if (current->next == nullptr) return;  // 超出長度
        Node* temp = current->next;
        current->next = temp->next;
        delete temp;
    }

    // 列印串列
    void printList() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    // 範例操作
    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtTail(4);
    list.insertAtTail(5);
    cout << "Initial list: ";
    list.printList();                 // 2 3 4 5

    list.deleteAtPosition(2); // 移除索引為 2 的元素
    cout << "After deleting position 2: ";
    list.printList();                 // 2 4 5

    list.deleteHead();
    cout << "After deleting head: ";
    list.printList();                 // 4 5

    return 0;
}

:::info
註：此程式的鏈結串列是以 1 作為起始索引。
:::

至於在指定位置插入節點的方式，可結合前兩種方式（在串列頭插入節點、在串列尾插入節點）：

先遍歷至目標的前一個位置，再調整指標串接新節點。若位置（索引）為 1 則與串列頭插入的方式相同；若超出串列長度則將插入方式改為在串列尾插入節點。

---

而於指定位置刪除節點的方式：

若位置為 1，與刪除串列頭節點相同；否則遍歷至目標前一個節點，調整其 next 指向目標節點的下一節點，並刪除目標節點記憶體。

### C++ STL linked-list
---

C++ 的 STL 函式庫中也提供了 linked-list 的容器，在 STL 中是一個雙向鏈結串列的實作容器。

使用前需要引入標頭檔 `#include <list>`。

相關操作如下：

* `push_back()`：將元素增加到尾端。
* `push_front()`：將元素增加到頭端。
* `pop_back()`：將元素從尾端移除。
* `pop_front()`：將元素從頭端移除。
* `insert()`：插入元素。
* `erase()`：移除某個位置的元素，也可以移除某段範圍的元素。
* `clear()`：清空容器內的所有元素。
* `empty()`：回傳容器是否為空。
* `size()`：回傳容器長度。
* `front()`：存取頭端元素。
* `back()`：存取尾端元素。

#include <list>
#include <iostream>

using namespace std;

class LinkedList {
private:
    list<int> lst;

public:
    // 插入頭節點
    void insertHead(int value) {
        lst.push_front(value);
    }

    // 插入尾節點
    void insertTail(int value) {
        lst.push_back(value);
    }

    // 插入指定位置節點
    bool insertAt(int index, int value) {
        if (index < 0 || index > lst.size()) {
            return false;
        }
        auto it = lst.begin();
        // advance(iterator, distance)
        // 表示在迭代器 iterator 中前進 distance 個距離
        advance(it, index);
        lst.insert(it, value);
        return true;
    }

    // 刪除頭節點
    bool deleteHead() {
        if (lst.empty()) {
            return false;
        }
        lst.pop_front();
        return true;
    }

    // 刪除尾節點
    bool deleteTail() {
        if (lst.empty()) {
            return false;
        }
        lst.pop_back();
        return true;
    }

    // 刪除指定位置節點
    bool deleteAt(int index) {
        if (index < 0 || index >= lst.size()) {
            return false;
        }
        auto it = lst.begin();
        advance(it, index);
        lst.erase(it);
        return true;
    }

    // 顯示鏈結串列內容
    void display() {
        if (lst.empty()) {
            cout << "List is empty" << endl;
            return;
        }
        for (const auto& val : lst) {
            cout << val << " ";
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;

    // 插入
    list.insertHead(1);      // 1
    list.insertTail(3);      // 1 3
    list.insertAt(1, 2);     // 1 2 3
    cout << "After insertions: ";
    list.display();

    // 刪除
    list.deleteHead();       // 2 3
    cout << "After deleting head: ";
    list.display();

    list.deleteTail();       // 2
    cout << "After deleting tail: ";
    list.display();

    list.insertTail(4);      // 2 4
    list.insertHead(1);      // 1 2 4
    list.deleteAt(1);        // 1 4
    cout << "After deleting at index 1: ";
    list.display();

    return 0;
}

### Linked-list 與 array 時間複雜度
---

| 操作類型 | Array（陣列） | Linked List（鏈結串列） |
|------------------|----------------------|-------------------------|
| 存取（Access） | O(1) | O(n) |
| 搜尋（Search） | O(n) | O(n) |
| 插入（Insert） | | |
| - 開頭 | O(n)（需移動元素） | O(1) |
| - 中間 | O(n)（需移動元素） | O(n)（需遍歷） |
| - 尾端 | O(1)（若空間足夠） | O(1)（在 tail 指標下） |
| 刪除（Delete） | | |
| - 開頭 | O(n)（需移動元素） | O(1) |
| - 中間 | O(n)（需移動元素） | O(n)（需遍歷） |
| - 尾端 | O(1)（若空間足夠） | O(n)（單向需遍歷） |
| 大小調整 | O(n)（需重新配置） | O(1) |

若為 Doubly Linked List（雙向鏈結串列），尾端刪除可達 O(1)，但需額外空間儲存前向指標。

鏈結串列習題
---

b938. kevin 愛殺殺：https://zerojudge.tw/ShowProblem?problemid=b938

#include <bits/stdc++.h>

using namespace std;

int main() {
    
    ios::sync_with_stdio(false);
    
    cin.tie(nullptr);
    
    int n, m;
    
    cin >> n >> m;
    
    list<int> lst;
    
    vector<list<int>::iterator> vec(n + 1); // 記錄每個編號在 lst 中的迭代器位置
    
    vector<bool> alive(n + 1, true); // 檢查是否有人活著
    
    for (int i = 1; i <= n; i++) {
        vec[i] = lst.insert(lst.end(), i);
    }
    
    for (int j = 0; j < m; j++) {
        
        int k;
        cin >> k;
        
        if (!alive[k]) { // 若 k 沒有活著
            cout << "0u0 ...... ?" << "\n";
        } else {
            
            auto it = vec[k];
            
            if (next(it) == lst.end()) { // 若是最後一個人就 illegal
                cout << "0u0 ...... ?" << "\n";
            } else {
                auto next_it = next(it);
                int removed_value = *next_it;
                cout << removed_value << "\n";
                lst.erase(next_it);
                alive[removed_value] = false;
            }
        }
    }
    
    return 0;
}