[数据结构与算法]2021-08-10

链表

一.数组模拟单链表

我们用head代表头节点的下标（我觉得可以理解成头节点下一个的指向），用ne[x]代表x 指向的下一个位置，用e[x]代表x节点处的值，用idx代表当前已经用到了哪个点。

链表的初始化：

void init()
{
    head = -1;
    idx = 0;
}

链表的头节点插入：在头节点后面插入值为x的节点

void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++;
}

链表的非头节点的插入：在下标为k的后面插入值为x的节点

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

链表的删除：删除下标为k的下一个节点

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

二.数组模拟双链表

我们用r[x] 表示链表后面指向的节点，用l[x] 表示链表前面指向的节点，用idx表示当前已经用到了哪个点，用e[x] 存储x节点的值为多少。

双链表的初始化：

void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

双链表的右端插入：在k节点后面插入一个新的值为x的节点

void right_add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;        
    r[k] = idx;
    idx ++;
}

双链表的左端插入：在k节点左边插入一个值为x的节点

void left_add(int k, int x)
{   
    right_add(l[k], x);
}

在头节点后面插入一个值为x的节点：

void add_to_head(int x)
{
    right_add(0,x);
} 

在尾节点前面插入一个值为x的节点：

void add_to_tail(int x)
{
    right_add(l[1] , x);
}

移除下标为k的节点：

void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}