链表可以 \(O(1)\) 插入/删除
单向链表
顾名思义 只有后继指针
邻接表
我习惯叫做链式前向星, 一般用来存储图, 挺好理解的, 这里直接给出存图的应用
struct edge {
int to, nxt;
} eg[M];
int head[N], egtot;
void add (int u, int v) {
eg[++egtot].to = v;
eg[egtot].nxt = head[u];
head[u] = egtot;
}
哈希表
通过链表实现一个整型到任意值的映射, 利用了取模意义下的剩余系, 代码:
struct hash_table {
int head[P], nxt[N], key[N], val[N], cnt;
int & operator [] (const int &x) {
int tmp = x % P;
for (int i = head[tmp]; i; i = nxt[i])
if (key[i] == x) return val[i];
nxt[++cnt] = head[tmp], head[tmp] = cnt;
key[cnt] = x, val[cnt] = 0;
return val[cnt];
}
};
一般来讲模数选一个稍大的质数使得冲突概率降低，同时使数据分布更均匀
由于哈希表本身在数据较少的情况下运行很快，单次查找可以近似看做是 \(O(1)\) 的，那么可以用来代替 STL 的 map 实现更快的映射存储
发现只有全局操作, 所以可以维护 \(x \times mul + add\) 以及全局和 \(sum\)
然后全局赋值就是清空, 使用哈希表维护一个下标到值的映射, 单点修改就可以使用映射完成
双向链表
顾名思义, 记录前驱和后继
考虑一个问题, 有一个数组, 如何按顺序从左到右删除这个数, 并实时维护它的排序数组?
使用 \(set\) 或者 平衡树?
实际上没有修改, 只有删除, 可以使用双向链表, 首先排序一下, 然后我们删除就可以做成 \(O(1)\) 的了
总复杂度就是 \(O(n)\) 的了
初始化就是上述的问题了, 剩下的内容是一个倍增, 因为决策点始终唯一所以可以倍增
循环链表
把双向链表头尾套接到一起, 一般用于处理有环的问题
十字链表
需要维护上下左右四个指针, 常见应用是 \(DLX\)
标签：egtot,head,nxt,int,cnt,链表 From： https://www.cnblogs.com/aqz180321/p/18415590