单链表和双链表的比较

一、变量声明

单链表

// head为头节点，不存储值(即ne)，但存储头节点的下标，当链表为空时，head = -1
// e[i] 表示节点i的值
// ne[i]表示节点i的next(下一个)指针是多少
// idx 存储当前已经用到了哪个点，即最新点的下标
int head,e[MAXN],ne[MAXN],idx;

双链表

// e[i] 表示节点i的值
// l[i] 表示节点i左边的指针是多少
// r[i] 表示节点i右边的指针是多少
// idx 存储当前已经用到了哪个点，即最新点的下标
int e[MAXN],l[MAXN],r[MAXN],idx;

二、链表初始化

单链表

//当链表为空时，head = -1，这时head即使尾节点也是头节点；当链表不为空时，head只表示头节点，-1表示尾节点。
//因为下标为0的位置没有使用，所以idx = 0;
void init()
{
    head = -1;
    idx = 0;
}

下图为单链表此时的情况：

双链表

//下标为0的点表示链表的表头，下标为1的点表示链表的表尾，相当于单链表中的head。
//因为下标0和1的位置都使用了，所以idx = 0;
void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

下图为双链表此时的情况：

三、链表的增删

单链表

//将x插到头节点后面
void add_to_head(int x)
{
    e[idx] = x;
    head = idx;
    idx ++;
}

//将x插到下标是k的节点后面
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]];
}

//删除头节点即删除head右面的节点。
//为什么head不能使用remove，而要特判？
//因为头节点的下标在head中，而题意可能把k = 0是为删除头节点操作，而head的值可能不等于0啊。故要特判。
//以k = 0时为例
if (!k) head = ne[head];

缺点：不能将x插入k节点的左边。

双链表

//在下标是k的点的右(后面)面插入x
void add(int k,int x)
{
    e[idx] = x;
    r[idx] = r[k];①
    l[idx] = k;②
    l[r[k]] = idx;③
    r[k] = idx;④
    idx ++;
}

//删除第k个点
void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k]; 
}

下图插入操作步骤：

调用函数操作实现不同的效果
这里的k为链表中插入的第k个数。
因为链表进行操作的是下标，又因为0和1用过了，所以这里传参为 k - 1 + 2，即 k + 1

//将x插入链表的左端点处
add(0,x);

//将x插入链表的右端点处
add(l[1],x);

//将x插入到k节点的左端
add(l[k + 1],x);

//将x插入到k节点的右端
add(k + 1,x);

//删除第k个节点
remove(k + 1);

注意：
①下标为0的点只是链表左端点的标记，r[0]的值才是链表的左端点的下标。即下标为0的右边为左端点
下标为1的点只是链表右端点的标记，l[1]的值才是链表的右端点的下标。即下标为1的左边为右端点
②进行链表操作使用的是下标；但题中可能给出第几个插入的数时，记得转换成下标，单链表与双链表不同。

四、链表的遍历

单链表

for (int i = head;i != -1;i = ne[i]) cout << e[i] << ' ';
cout << endl;

为什么这里是i=head,而不是i=0?
因为可能进行add_to_head操作，这时head=idx，可能不等于0了；还有一个原因，不用特判链表为空了。

双链表

for (int i = r[0];i != 1;i = r[i]) cout << e[i] << ' ';
cout << endl;

为什么这里是i=0，而是i=r[0]?
因为下标0和1不存储值。