# 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}$
### 宣告
原本
```cpp=
int *ptr = new int(10);
cout << *ptr << endl;
delete ptr;
```
變成
```cpp=
unique_ptr<int> ptr(new int(10));
cout << *ptr << endl;
```
## Singly linked list
簡單好寫，也挺暴力的
要做持久化也方便，缺點就是不知道能幹嘛
```cpp=
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$
```cpp=
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/)
```cpp=
#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$ 的部分往後移
兩種應該都滿好寫的
這裡只寫了第一種方法
```cpp=
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}$ 試試
把節點訂好
```cpp=
struct node
{
LL value;
list<node>::iterator down;
node(LL _value, list<node>::iterator _down) : value(_value), down(_down) {}
node(LL _value) : value(_value) {}
};
```
懶得判邊界所以先塞兩個點進去
```cpp=
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()));
}
};
```
先寫隨機層數
```cpp=
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);
}
```
然後寫插入
```cpp=
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;
}
```
再寫刪除
```cpp=
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}$
```cpp=
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>
Sign in with Wallet
Connect another wallet