题目描述

实现一个双链表，双链表初始为空，支持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个插入的数右侧插入一个数。

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

数据范围
1≤M≤100000

双链表

结点内容

e[N]：第N个节点的内容
l[N]:左指针，指向得到是序号
r[N]:右指针，指向得到是序号
idx：序号
没有头结点 第一个节点序号为0，最后一个节点序号为1

初始化

第一个结点的右指针指向1，最后一个结点的左指针指向0，idx从2开始
r[0] = 1;
l[1] = 0;
idx = 2;

在第k个插入的结点后插入新的结点

e[idx] = x;
l[idx] = k;
r[idx] = r[k];
这两个顺序不能颠倒，要不然就断了
l[r[k]] = idx;
r[k] = idx++;
记得将idx加一

删除第k个插入的结点

r[l[k]] = r[k];
l[r[k]] = l[k];

java 代码

import java.io.*;
import java.util.*;

public class Main{
    static int N = 100010;
    static int idx;
    static int[] l = new int[N];
    static int[] r = new int[N];
    static int[] e = new int[N];

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(reader.readLine());// 读取操作次数

        r[0] = 1;
        l[1] = 0;
        idx = 2;//初始化为2

        while (m-- > 0) {
            String line = reader.readLine().trim();//按行读取，去除首尾空格
            String[] parts = line.split(" ");//按空格分割
            String op = parts[0];//操作符

            if (op.equals("L")) {
                int x = Integer.parseInt(parts[1]);//转为整数
                add(0, x);
            } else if (op.equals("R")) {
                int x = Integer.parseInt(parts[1]);
                add(l[1], x);
            } else if (op.equals("D")) {
                int k = Integer.parseInt(parts[1]);
                remove(k + 1); // 注意索引调整
            } else if (op.equals("IL")) {
                int k = Integer.parseInt(parts[1]);
                int x = Integer.parseInt(parts[2]);
                add(l[k + 1], x);
            } else if (op.equals("IR")) {
                int k = Integer.parseInt(parts[1]);
                int x = Integer.parseInt(parts[2]);
                add(k + 1, x);
            }
        }

        for (int i = r[0]; i != 1; i = r[i]) {
            System.out.print(e[i] + " ");
        }
    }
}