题目描述

原题

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

(1) 在最左侧插入一个数；

(2) 在最右侧插入一个数；

(3) 将第k个插入的数删除；

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

(5) 在第k个插入的数右侧插入一个数

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

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

输入格式
第一行包含整数M，表示操作次数。

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

(1) “L x”，表示在链表的最左端插入数x。

(2) “R x”，表示在链表的最右端插入数x。

(3) “D k”，表示将第k个插入的数删除。

(4) “IL k x”，表示在第k个插入的数左侧插入一个数。

(5) “IR k x”，表示在第k个插入的数右侧插入一个数。

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

数据范围
1≤M≤100000
所有操作保证合法。

输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例：
8 7 7 3 2 9

算法

双链表

插入和删除图：

注意

有个很重要的注意点：我们在说k号结点的上一个结点或者下一个结点的时候，不要写成k - 1或者k + 1 号结点。
因为很有可能这两个结点之间又插入了别的结点，双链表的上一个结点或者下一个结点都是用过指针来索引的，所以
写上一个结点的时候应该写成l[k],同理下一个结点的写法应该是r[k].

其他就没什么注意点了，详情都在注释里面 。

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
//e数组存放的是结点的值  l数组存放的指向上一个结点的指针
//r数组存放的是指向下一个结点的指针  idx记录当前正在使用的结点
int e[N] , l[N] , r[N] , idx ;

//初始化
void init(){
    /*这里就不定义头结点和尾结点，直接把0结点当作头结点，1号点当作尾结点。
      所以，初始状态下o号点的下一个结点就是1， 1号结点的上一个结点就是0
    */
    r[0] = 1 , l[1] = 0;
    //当前结点从2号结点开始。因为0 ， 1都已经使用过了。
    idx = 2;
}

//插入操作有两种，一种是在一个结点的左边，另外一种是在结点的右边插入
//这里是在第k哥结点的右边插入
void add(int k , int x){
    //第一步，先把要插入结点的值赋好
    e[idx] = x;
 //把第k个结点的下一个指针赋给插入结点指向下一个结点的指针
    r[idx] = r[k];
    //插入结点指向上一个结点的指针指向k
    l[idx] = k;
    //原本k号结点的下一个结点他指向上一个结点指针指向变为指向当前这个结点idx
    l[r[k]] = idx;
    //k号结点的指向下一个结点指针指向变为当前结点idx
    r[k] = idx ;

    /*上面两句不能写反了，不然会错误。因为r[k]原本是指向下一个结点的，如果写反了
      ，r[k]的值就变成了当前结点，然后下面赋值的时候就会发生错误。
    */
    idx ++;
}

//删除第k个点
//这里有点绕，为简洁表述，指向下一个结点的指针叫做右边指针，左边同理
void remove(int k){
    //k号结点上一个结点的右边指针赋值为k号结点的右边指针，跳过k结点
    r[l[k]] = r[k];
    //k号结点下一个结点的左边指针赋值为k号结点的左边指针，跳过k结点
    l[r[k]] = l[k];
}

int main(){
    int m;
    cin >> m;
    init();
    while(m--){
        int k , x ;
        string op ;
        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;
            //第k个结点的下标是k + 1，因为idx下标是从2开始的
            remove(k + 1);
        }else if(op == "IL") {
            //在k号结点的左边插入一个结点
            cin>>k>>x;
            add(l[k + 1] , x);
        }else{
            //在k号结点右边插入一个结点
            cin>>k >> x;
            add(k + 1 , x);
        }
    }

    //遍历输出双链表,头结点是0，但是不输出，所以从头结点的下一个结点r[0]进行输出
    for(int i = r[0] ; i != 1 ; i = r[i]) cout<<e[i]<<' ';
    cout<<endl;
    return 0;
}