# Linked list (鏈結串列)

## B4 start

因為好像沒人在乎他，我又剛好在 [$\text{OI wiki}$](https://oi-wiki.org/) 上看到類似的東西，所以來做一份講義

## Intro

先備知識: 指標、$\text{struct}$


差不多長這樣，每個人都有一個指標指向另一塊
跟人體蜈蚣一樣
優點是因為只要改變各元素之間指標的連接關係
所以只看插入和刪除的話複雜度是 $\mathcal{O}(1)$
還有把兩個串接起來也是 $\mathcal{O}(1)$
缺點也很明顯: 沒辦法 $\text{Random access}$
查詢需要 $\mathcal{O}(n)$ 的複雜度

可以拿來實作 $\text{Stack}$ 或 $\text{Queue}$
稍微爆改一下也能弄出一棵二元樹之類的 (詳見還沒做出來的講義)([喔做出來了](https://hackmd.io/@Viecon-342524/S1ZA5GM6s))

## Smart pointer

剛好要用到指標所以順便介紹一下這個
為了要解決 $\text{memory leak}$ 的問題，$\text{C++}$ 就在 $\text{STL}$ 裡面引進了「$\text{smart pointer}$」的概念
分成以下三種:

* `unique_ptr` :確保一份資源（被配置出來的記憶體空間）只會被一個 `unique_ptr` 指；當 `unique_ptr` 物件消失時，就會自動釋放資源。
* `shared_ptr` :有 $\text{reference count}$ 機制，當沒人指向一塊空間時他就會自動被釋放
* `weak_ptr` :跟 `shared_ptr` 很像，差別在不會計入 $\text{reference count}$

### 宣告

原本

int *ptr = new int(10);
cout << *ptr << endl;
delete ptr;

變成

unique_ptr<int> ptr(new int(10));
cout << *ptr << endl;

## Singly linked list

簡單好寫，也挺暴力的
要做持久化也方便，缺點就是不知道能幹嘛

struct Linked_list
{
    struct node
    {
        LL value;
        shared_ptr<node> next;
        node(LL _value) : value(_value) {}
    };
    shared_ptr<node> head;
    LL sz = 0;
    void insert(LL p, LL v)
    {
        p = min(p, sz);
        if (p == 0)
        {
            auto tmp = head;
            head = shared_ptr<node>(new node(v));
            head->next = tmp;
            return;
        }
        auto cur = head;
        for (int i = 0; i < p - 1; i++)
            cur = cur->next;
        auto tmp = cur->next;
        cur->next = shared_ptr<node>(new node(v));
        cur->next->next = tmp;
        
    }
    bool erase(LL p)
    {
        if (sz == 0)
            return 0;
        if (p >= sz)
            return 0;
        if (p == 0)
        {
            head = head->next;
            return 1;
        }
        shared_ptr<node> cur = head;
        for (int i = 0; i < p - 1; i++)
            cur = cur->next;
        cur->next = cur->next->next;
        return 1;
    }
    LL at(LL p)
    {
        if (p >= sz)
        {
            return -1;
        }
        shared_ptr<node> cur = head;
        for (int i = 0; i < p; i++)
            cur = cur->next;
        return cur->value;
    }
};

沒測過，也不知道對不對

## Doubly linked list


就這樣，似乎也沒什麼
總之不是今天的重點

### 補充 : XOR linked list

可以在降低空間複雜度的情況下達到和 $\text{Doubly linked list}$ 一樣的目的
在每個節點儲存 **前一個節點的位址** $\oplus$ **後一個節點的位址**
這樣就可以省下一個指標大小的空間

## Circular linked list

也是有單向跟雙向
首尾相連 也不知道能幹嘛
但好像滿多地方都有介紹就順便講一下

## std::list

好用的東西
不用再為指標煩惱
(變成為迭代器煩惱)

[**cppreference**](https://en.cppreference.com/w/cpp/container/list)

成員函式之類的
除了 $\text{splice}$ 以外基本上都差不多

### 應用

[**d027: 習題 Q-3-3. 加減乘除**](https://judge.tcirc.tw/ShowProblem?problemid=d027)

$5\times 3+2-4\times 5$

先乘除後加減
想要把「$5\times 3$」換成 $15$，把「$4\times 5$」換成 $20$
所以把每個字都塞到 $\text{list}$ 裡面，找到「\*、/」就把它前後的數字收集起來。算完答案之後把前後都刪掉，把自己這格改成答案。

$15+2-20$

再做一次

$-3$

struct qu
{
    LL k;     // number
    char t;   // operator
};
void sol()
{
    string s;
    cin >> s;
    LL n = s.size();
    list<qu> lis;
    for (int i = 0; i < n; i++)
    {
        if (isdigit(s[i]))
        {
            lis.pb({s[i] - '0', 'k'});
        }
        else
        {
            lis.pb({-1, s[i]});
        }
    }

    for (auto i = lis.begin(); i != lis.end(); i++)
    {
        if (i->t == '*' || i->t == '/')
        {
            auto a = i, b = i;
            a--, b++;
            if (i->t == '*')
                i->k = a->k * b->k;
            else
                i->k = a->k / b->k;
            i->t = 'O';
            lis.erase(a);
            lis.erase(b);
        }
    }
    for (auto i = lis.begin(); i != lis.end(); i++)
    {
        if (i->t == '+' || i->t == '-')
        {
            auto a = i, b = i;
            a--, b++;
            if (i->t == '+')
                i->k = a->k + b->k;
            else
                i->k = a->k - b->k;
            i->t = 'O';
            lis.erase(a);
            lis.erase(b);
        }
    }
    cout << lis.begin()->k << endl;
}

類題:
[**d040: 普通分數的四則運算**](https://judge.tcirc.tw/ShowProblem?problemid=d040)

---

[**NEOJ - 一天遊戲只能一小時**](https://neoj.sprout.tw/problem/25/)

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<list<int>> v(n);
    while (m--)
    {
        string s;
        cin >> s;
        if (s[0] == 'A')
        {
            int a, b;
            cin >> a >> b;
            v[a - 1].push_back(b);
        }
        if (s[0] == 'L')
        {
            int a;
            cin >> a;
            a--;
            if (v[a].empty())
            {
                cout << "queue " << a + 1 << " is empty!" << endl;
            }
            else
            {
                v[a].pop_front();
            }
        }
        if (s[0] == 'J')
        {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            auto it = v[b].end();
            v[b].splice(it, v[a]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << "queue " << i + 1 << ":";
        if (v[i].empty())
        {
            cout << " empty" << endl;
        }
        else
        {
            for (auto j : v[i])
            {
                cout << " " << j;
            }
            cout << endl;
        }
    }
    return 0;
}

## 蛤

其實接下來才是重點

## 塊狀鏈表


(找不到台灣的譯名)
如上圖，其實就是 $\text{linked list}$，只是每一格都存了一個大小為 $\sqrt n$ 的陣列
可以用 $\text{STL}$ 來偷懶
寫起來輕鬆，又有 $\mathcal{O}(\sqrt n)$ 插入/刪除/詢問的複雜度
實作時會將每塊大小設為一個定值，畢竟不可能每插入一個數字就重算一次 $\sqrt n$

### 插入

插入有兩種方法

1. 正常的插入，直到有一塊大小 $\geq 2\sqrt n$ 時就把那塊分裂成兩塊
2. 每插入一個就把超過 $\sqrt n$ 的部分往後移

兩種應該都滿好寫的
這裡只寫了第一種方法

struct Unrolled_linked_list
{
    LL C;
    LL sz = 0;
    list<vector<LL>> l; // list<list<LL>> 也可以
    void insert(LL p, LL v)
    {
        auto it = l.begin();
        while (1)
        {
            if (p - it->size() < 0)
            {
                it->insert(it->begin() + p, v);
                if (it->size() >= 2 * C)
                {
                    auto tmp = it;
                    tmp++;
                    l.insert(tmp, vector<LL>(it->begin() + C, it->end()));
                    it->rz(C);
                }
                break;
            }
            p -= it->size();
            it++;
        }
    }
};

(一樣沒測過，不保證正確)

### 刪除

刪除的操作跟插入差不多，這裡就不再贅述
||(其實是想偷懶)||

## 有序鏈表

就是 $\text{linked list}$ ，但裡面的元素有排序好
(不就是退化的 $\text{BST}$ 嗎)
插入的時候稍微維護一下下就好，不難
顯然插入 刪除 詢問都是 $\mathcal{O}(n)$
當然也可以配合塊狀鏈表把複雜度壓到 $\mathcal{O}(\sqrt n)$
但這不是今天的重點

## 跳表 (skip list)

這份講義的起源
我補習前亂翻 $\text{OI wiki}$ 看到的，因為覺得滿酷的所以做了這整份講義
我個人覺得他的概念有點像 $\text{treap}$ ，都是利用 $\text{Random}$ 來保證有好的複雜度
可以把它當作 $\text{set}$ 或 $\text{map}$ 來用

### 結構

一個跳表由多層有序鏈表組成
最底層是原始的有序鏈表
對於第 $i$ 層的元素，有 $p$ 的機率會出現在第 $i+1$ 層 ( $p$ 是自己訂的一個常數，通常用 $0.25$)
查詢時從最頂層開始往右走，如果不能往右或右邊的比目標大就往下
一直到找到為止


### 時間複雜度

第 $i$ 層期望會有 $np^{i-1}$ 個元素
每一層的大小是底下那一層的 $p$ 倍
故整個跳表的期望層數為 $\log_{\frac{1}{p}} n$ 層

期望在第 $i$ 層走一步相當於在最底層走 $\frac{1}{p^{i-1}}$ 步
可以想像成把目標位置拆成 $\frac{1}{p}$ 進制

所以總共就是 $\log_{\frac{1}{p}} n$ 步

可得單次詢問的期望複雜度為 $\mathcal{O}(\log n)$

### 空間複雜度

>第 $i$ 層期望會有 $np^{i-1}$ 個元素
故整個跳表的期望層數為 $\log_{\frac{1}{p}} n$ 層

就用力地把它們加起來

$\frac{n(1-p^{\log_{\frac{1}{p}} n})}{1-p}$ (等比級數公式)

$=\frac{n-1}{1-p}$

因為 $p$ 是常數，所以它的期望空間複雜度為 $\mathcal{O}(n)$

### 實作

隨便寫一個 $\text{set}$ 試試

把節點訂好

struct node
{
    LL value;
    list<node>::iterator down;
    node(LL _value, list<node>::iterator _down) : value(_value), down(_down) {}
    node(LL _value) : value(_value) {}
};

懶得判邊界所以先塞兩個點進去

skip_list()
{
    lis.rz(max_level);
    lis[0].pb(node(-INF));
    lis[0].pb(node(INF));
    for (int i = 1; i < max_level; i++)
    {
        lis[i].pb(node(-INF, lis[i - 1].begin()));
        lis[i].pb(node(INF, ++lis[i - 1].begin()));
    }
};

先寫隨機層數

const LL p = 4; // 1/p
const LL max_level = 20;
vector<list<node>> lis;
LL random_level()
{
    LL lv = 1;
    while (rng() % p == 0)
        lv++;
    return min(max_level, lv);
}

然後寫插入

void insert(LL v)
{
    vector<list<node>::iterator> stk;
    LL cur_level = max_level - 1;
    auto cur = lis[max_level - 1].begin();
    while (1)
    {
        cur++;
        if (cur->value == v)
            return;
        
        if (cur->value > v)
        {
            if (cur_level != 0)
            {
                stk.pb(cur--);
                cur = cur->down;
                cur_level--;
            }
            else
                break;
        }
    }
    LL lv = random_level();
    auto last = lis[0].insert(cur, node(v));
    for (int i = 1; i < lv; i++)
    {
        last = lis[i].insert(stk.back(), node(v, last));
        stk.pop_back();
    }
    return;
}

再寫刪除

bool erase(LL v)
{
    LL cur_level = max_level - 1;
    auto cur = lis[max_level - 1].begin();
    while (1)
    {
        cur++;
        if (cur->value == v)
        {
            break;
        }
        if (cur->value > v)
        {
            if (cur_level != 0)
            {
                cur--;
                cur = cur->down;
                cur_level--;
            }
            else
                return 0;
        }
    }
    while (cur_level >= 0)
    {
        auto tmp = cur->down;
        lis[cur_level].erase(cur);
        cur = tmp;
        cur_level--;
    }
    return 1;
}

跟插入差不多

最後寫個 $\text{count}$

bool count(LL v)
{
    LL cur_level = max_level - 1;
    auto cur = lis[max_level - 1].begin();
    while (1)
    {
        cur++;
        if (cur->value == v)
            return 1;

        if (cur->value > v)
        {
            if (cur_level != 0)
            {
                cur--;
                cur = cur->down;
                cur_level--;
            }
            else
                return 0;
        }
    }
}

小改一下就可以當 $\text{map}$ 或 $\text{multiset}$

要有 $\text{lower_bound}$ 和 $\text{upper_bound}$ 也不難，改一下 $\text{count}$ 就好

[**CSES - Towers (solved by skip list)**](https://cses.fi/paste/62b66466a91b99114e77f4/)
[**CSES - Subarray Sums II (solved by skip list)**](https://cses.fi/paste/e81259b85f4e5b474e7866/)

除此之外，只要多維護**往右指標的長度**就能做到 $\text{Random access in}$ $\mathcal{O}(\log n)$
而這個其實也不難維護，只要往右走的時候加一下就好

[**Josephus Problem II (solved by skip list)**](https://cses.fi/paste/4c0805a8afdcfa5d4f58e5/)

### 結論

優點:

1. 簡單好寫，雖然看起來有點長但其實大部分都只要複製貼上就好
2. 複雜度好
3. 很酷啊不覺得嗎

缺點:

1. 學這個幹嘛，我都用 [$\text{__gnu_pbds::tree}$](https://hackmd.io/@Viecon-342524/SJ1C2BUE9)
2. 常數竟然比 $\text{std::multiset}$ 大，吐了

## 沒了


## 參考資料

* <https://en.cppreference.com/w/cpp/container/list>
* <https://oi-wiki.org/ds/skiplist/>
* <http://ccf.ee.ntu.edu.tw/~yen/courses/ds20F/chapter-sl.pdf>
* <https://www.twblogs.net/a/5b835f1e2b71776c51e2b615>
* <https://www.javatpoint.com/skip-list-in-data-structure>
* <https://redirect.cs.umbc.edu/courses/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html>
* <https://stackoverflow.com/questions/12733622/the-time-complexity-of-skip-list>
* <https://en.wikipedia.org/wiki/Unrolled_linked_list>
* <https://brilliant.org/wiki/unrolled-linked-list/>
* <https://blog.csdn.net/weixin_39220472/article/details/81294068>
* <https://oi-wiki.org/ds/block-list/>
* <https://cplusplus.com/reference/vector/vector/>
* <https://blog.51cto.com/u_15329201/3392979>
* <https://blog.csdn.net/sinat_36645384/article/details/107051519>
* <https://en.wikipedia.org/wiki/Doubly_linked_list>
* <https://www.geeksforgeeks.org/data-structures/linked-list/singly-linked-list/>
* <https://www.javatpoint.com/singly-linked-list>
* <https://kheresy.wordpress.com/2012/03/03/c11_smartpointer_p1/>
* <https://kheresy.wordpress.com/2012/03/05/c11_smartpointer_p2/>
* <https://rust-algo.club/collections/singly_linked_list/>
* <https://www.tutorialspoint.com/data_structures_algorithms/circular_linked_list_algorithm.htm>