双链表应用¶

应用1：LRU缓存¶

LRU：最近最少使用。

结构：

head <-> 最新访问 <-> ... <-> 最久访问 <-> tail

使用：

哈希表快速查找
双链表维护顺序

完整代码¶

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int e[N], L[N], R[N], idx;
unordered_map<int,int> mp;

void insert(int k,int x){
    e[idx]=x;
    R[idx]=R[k];
    L[idx]=k;
    L[R[k]]=idx;
    R[k]=idx++;
}

void remove(int k){
    L[R[k]]=L[k];
    R[L[k]]=R[k];
}

int main(){
    R[0]=1;
    L[1]=0;
    idx=2;

    return 0;
}

应用2：编辑器¶

双链表可以表示：

左侧内容 <-> 光标 <-> 右侧内容

支持：

光标移动
插入字符
删除字符