acwing算法基础之数据结构--双链表

1 知识点

一般的结构体写法为，

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

但我们不用这个，而用数组模拟双链表，此时，用编号为0的结点表示头结点，用编号为1的结点表示尾节点。

2 模板

const int N = 1e6 + 10;
int idx; //用来表示所有的结点下标。
int e[N], l[N], r[N]; //e[i]表示结点i的值，l[i]表示结点i的左边结点，r[i]表示结点i的右边结点。//（1）初始化
void init() {//结点0表示头结点，结点1表示尾节点。r[0] = 1;l[1] = 0;idx = 2;
}//（2）在结点k的右边插入数值x
void insert(int k, int x) {e[idx] = x;r[idx] = r[k];l[idx] = k;r[k] = idx;l[r[idx]] = idx;idx++;
}//（3）删除结点k
void remove(int k) {r[l[k]] = r[k];l[r[k]] = l[k];
}