•【3】链表：单链表、双向链表、循环链表 •【4】链表（list）
每个节点只维护 next 指针
每个节点维护左右指针（下一个 next 和 上一个 previous）
https://www.luogu.com.cn/problem/P1160
1
2 1
2 3 1
2 3 4 1
2 4 1
直接暴力
在数组中插入一个数字，之后的每个数字都要向后移动，非常慢，会超时
对于每个人记录自己左边的是谁，自己右边的是谁
为了实现简单，往往实现成环形，可以避免特殊处理队首和队尾
0 1 0
0 2 1 0
0 2 3 1 0
0 2 3 4 1 0
0 2 4 1 0
双向链表的插入
假设有 a b c d 四个位置
R[a] = b
R[b] = c
R[c] = d
L[b] = a
L[c] = b
L[d] = c
希望在 b 和 c 之间插入 x
那么插入之后
R[b] = x
R[x] = c
L[c] = x
L[x] = b
希望在 c 左边插入 x
方法一：
b = L[c]
R[b] = x
R[x] = c
L[c] = x
L[x] = b
方法二：
R[x] = c
L[x] = L[c]
R[L[c]] = x
L[c] = x
双向链表的删除
假设有 a b c d 四个位置
删掉c
方法一：
b = L[c]
d = R[c]
R[b] = d
L[d] = b
方法二：
R[L[c]] = R[c]
L[R[c]] = L[c]