双链表

基本结构

left <-> node <-> right

数组实现

int e[N], L[N], R[N], idx;

插入节点

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];
}

指针实现

struct Node{
    int val;
    Node *left;
    Node *right;
};

插入：

void insert(Node *p, Node *x){
    x->right = p->right;
    x->left = p;
    p->right->left = x;
    p->right = x;
}

删除：

void remove(Node *p){
    p->left->right = p->right;
    p->right->left = p->left;
}