双链表

算法题中，一般使用静态链表，可以大幅提升速度。

结点i的值为value[i]，left、right指针为left[i]、right[i]，d表示数组已用位的下一位；

默认0号位为首结点，1号位为尾结点，不存储任何实际值，-1表示空指针；

int value[n], left[n], right[n], d = 2;

left[0] = right[1] = -1, right[0] = 1, left[1] = 0;

插入

在结点x的后面插入值为a的节点：

value[d] = a;
left[d] = x, right[idx] = right[x];
right[x] = d, left[right[x]] = d++;

删除

删除结点x：

right[left[x]] = right[x];
left[right[x]] = left[x];

注解：

(1)双链表有首、尾结点的好处是，在表首、尾部进行操作时，与在表中部进行操作的代码一致。

(2)无首、尾结点的双链表如下：

节点i的值为value[i]，left、right指针为left[i]、right[i]，d表示数组已用位的下一位，head、tail表示首、尾指针，-1表示空指针；

int value[n], left[n], right[n], d = 0, head = -1, tail = -1;

无首、尾结点的双链表在表首、尾部进行操作时，与在表中部进行操作的代码不一致；

在表首插入值为a的结点：

value[d] = a;
left[d] = -1, right[d] = head;
head = d++;

删除表首的一个结点：

head = right[head];
left[head] = -1;

（在tail侧进行插入和删除和head端类似，只需把head和tail、left和right互换即可）

---