双链表

发表于 更新于 分类于 ，
本文字数： 411

数组实现双链表

e[N]储存每个节点的value l[N]储存每个节点的左指针 r[N]储存每个节点的右指针 idx保存已使用到的地址

初始化操作

1
2
3
4
5
6
7
void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
//在这里将双链表的头节点地址表示为0，尾节点地址表示为1，0与1使用所以这里的idx初始化为2

在地址为k的节点右边（后边）增加一个节点

1
2
3
4
5
6
7
8
void add(int k, int x)
{
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    e[idx++] = x;
}//在这里r[k]的更新一定要在 l[r[k]]更新后

（代码实现往右增加，同样可以实现往左，但往左边增加相当于往左边节点的右边增加节点）

删除地址为k的节点

1
2
3
4
5
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}