您现在的位置是：首页 >技术交流 >acwing c++基础算法笔记（6）数据结构之链表网站首页技术交流

单链表 AcWing 826. 单链表

实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；删除第 k 个插入的数后面的数；在第 k 个插入的数后插入一个数。现在要对该链表进行 M MM 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k kk 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

#include<iostream>

using namespace std;

const int N=100010;
// head 表示头节点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储已经用到了那个点 
int head,e[N],ne[N],idx;

// 初始化
void init ()
{
        head=-1;
        idx=0;
} 

// 将x插到头节点
void add_to_head(int x) 
{
        e[idx]=x;
        ne[idx]=head;
        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]];
} 

int main ()
{
        int m;
        cin >> m;
        init ();
        while (m--)
        {
                int k,x;
                char op;
                cin >> op;
                if (op=='D')
                {
                        cin >> k;
                        if (!k) head=ne[head];
                        remove (k-1);
                }
                else if (op=='H')
                {
                        cin >> x;
                        add_to_head (x);
                }
                else
                {
                        cin >> k >> x;
                        add (k-1,x);
                }
        }
        for (int i=head;i!=-1;i=ne[i]) cout << e[i] << ' ';
        return 0;
}

init 函数

功能：这个函数用于初始化链表。它将 head 的值设置为 -1，表示链表初始为空，不存在头节点。同时把 idx 的值设置为 0，意味着下一次插入节点时会从数组下标为 0 的位置开始存储数据和构建指针关系，为后续的节点插入操作做好准备。

add_to_head 函数

功能：实现将一个给定的整数 x 插入到链表的头部位置的操作。

首先，e[idx] = x; 将传入的参数 x 的值存储到 e 数组中索引为 idx 的位置，也就是把要插入的数据存放到当前可用的节点数据存储位置。

接着，ne[idx] = head; 将 ne 数组中索引为 idx 的元素赋值为当前的 head 值，这使得新插入的节点（对应下标 idx ）的下一个节点指向了原来链表的头节点，建立起了新节点与原链表头部的连接关系。

最后，head = idx++; 先将 idx 的值赋给 head，使得 head 指向新插入的这个节点，完成将新节点添加到链表头部的操作，然后将 idx 自增 1，以便下次插入节点时可以使用新的数组下标位置。

add 函数

功能：实现在链表中指定下标为 k 的节点后面插入一个新节点，新节点存储的数据为 x 。

首先，e[idx] = x; 把要插入的新数据 x 存储到 e 数组中当前可用的下标为 idx 的位置，确定了新节点的数据内容。

然后，ne[idx] = ne[k]; 将新节点（对应下标 idx ）的下一个节点指针（通过 ne 数组模拟）设置为原来下标为 k 的节点的下一个节点的下标，也就是让新节点的下一个节点指向原 k 节点后面原本指向的那个节点，保持链表的连续性。

最后，ne[k] = idx++; 将原来下标为 k 的节点的下一个节点指针更新为当前的 idx ，使得原 k 节点的下一个节点变为新插入的节点，同时将 idx 自增 1，为后续插入操作准备新的可用下标位置。

remove 函数

功能：实现删除链表中指定下标为 k 的节点后面的那个节点的操作。

具体原理：通过 ne[k] = ne[ne[k]]; 这行代码，将下标为 k 的节点的下一个节点指针（原本指向要删除的节点）更新为要删除节点的下一个节点的下标，相当于跳过了要删除的节点，直接将原 k 节点与要删除节点后面的那个节点连接起来，从而实现了删除指定节点后面节点的效果。

双链表 AcWing 827. 双链表

实现一个双链表，双链表初始为空，支持 5 种操作：

在最左侧插入一个数；

在最右侧插入一个数；

将第 k 个插入的数删除；

在第 k 个插入的数左侧插入一个数；

在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 x。

R x，表示在链表的最右端插入数 x。

D k，表示将第 k 个插入的数删除。

IL k x，表示在第 k 个插入的数左侧插入一个数。

IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

#include<iostream>

using namespace std;

const int N=100010;

int e[N],l[N],r[N],idx;

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

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

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

int main()
{
        int m;
        cin >> m;
        init();
        while (m--)
        {
                string op;
                int k,x;
                cin >> op;
                if (op=="L")
                {
                        cin >> x;
                        add(0,x);
                }
                else if (op=="R")
                {
                        cin >> x;
                        add(l[1],x);
                }
                else if (op=="D")
                {
                        cin >> k;
                        remove (k+ 1);
                }
                else if (op=="IL")
                {
                        cin >> k >> x;
                        add(l[k+1],x);
                }
                else
                {
                        cin >> k >> x;
                        add(k+1,x);
                }
        }
        for (int i=r[0];i!=1;i=r[i]) cout << e[i] << ' ';
        cout << endl;
        return 0;
} 

功能：该函数用于初始化这个模拟的双向链表结构。

通过 r[0] = 1; 这行代码，将索引为 0 的节点（这里可以看作是一个虚拟的头节点，虽然它本身可能不存储实际的数据，但用于构建链表的起始结构）的后继指针 r[0] 设置为 1，意味着从这个虚拟头节点出发，其后继节点的索引为 1。

接着 l[1] = 0; 语句，将索引为 1 的节点（与前面虚拟头节点的后继节点对应）的前驱指针 l[1] 设置为 0，也就是明确了这个节点的前驱是索引为 0 的虚拟头节点，这样就初步构建起了一个简单的双向链表的基本框架，尽管此时还没有实际存储数据的节点。

最后，idx = 2; 将 idx 的值设置为 2，这是因为后续插入实际节点时，要从索引为 2 的位置开始存储节点数据以及构建相应的前驱、后继指针关系，为新节点的插入操作预留好了初始的可用位置。

add 函数

功能：此函数实现了在双向链表中指定索引为 k 的节点后面插入一个新节点的操作，新节点存储的数据为 x 。

首先，e[idx] = x; 将传入的参数 x 的值存储到 e 数组中索引为 idx 的位置，这就确定了新插入节点的数据内容，把要插入的数据放到了对应的节点数据存储位置上。

然后，r[idx] = r[k]; 这行代码将新节点（索引为 idx ）的后继指针 r[idx] 设置为原来索引为 k 的节点的后继节点的索引，也就是让新节点的后继节点先指向原 k 节点原本指向的那个后继节点，保持链表在后继方向上的连续性。

接着，l[idx] = k; 语句把新节点的前驱指针 l[idx] 设置为当前传入的索引 k，明确了新节点的前驱节点就是索引为 k 的那个节点，在双向链表的前驱方向上建立起正确的连接关系。

再通过 l[r[k]] = idx; 这一步，找到原索引为 k 的节点的后继节点（通过 r[k] 获取其索引），并将这个后继节点的前驱指针 l[r[k]] 更新为新节点的索引 idx，使得原 k 节点的后继节点能够正确地指向新插入的这个节点，完善了双向链表在插入新节点后的前驱指针关联。

• 最后，r[k] = idx++; 先将原索引为 k 的节点的后继指针更新为当前的 idx，使得原 k 节点的后继节点变为新插入的这个节点，然后将 idx 自增 1，这样 idx 就指向了下一个可用的数组下标位置，为后续继续插入新节点做好准备。

remove 函数

功能：这个函数实现了从双向链表中删除指定索引为 k 的节点的操作。

r[l[k]] = r[k]; 这行代码，先通过 l[k] 找到索引为 k 的节点的前驱节点的索引，然后将这个前驱节点的后继指针（原本指向要删除的索引为 k 的节点）更新为索引为 k 的节点的后继节点的索引（即 r[k] ），这样就相当于在链表中跳过了要删除的节点，使得前驱节点直接与要删除节点的后继节点连接起来，保证了链表在后继方向上的连续性。

接着，l[r[k]] = l[k]; 通过 r[k] 找到索引为 k 的节点的后继节点的索引，再将这个后继节点的前驱指针（原本指向要删除的索引为 k 的节点）更新为索引为 k 的节点的前驱节点的索引（即 l[k] ），使得后继节点也正确地连接到了原本要删除节点的前驱节点上，从而在双向链表的前驱方向上也保持了连续性，整体实现了从双向链表中删除指定节点的效果，让链表结构依然保持正确的双向连接关系。