java 代码

import java.io.*;
import java.util.*;
class Main{
    private static int N = 100000+10;
    private static int[] l = new int[N]; //当前结点的上个结点位置
    private static int[] e = new int[N];//当前结点的值
    private static int[] r = new int[N];//当前结点的下一个结点的位置 
    private static int head;
    private static int idx;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        init();
        while(m-- > 0){
            String operate = in.next();
            switch(operate){
                case "R" :{ //插入到最右边  也就是在最后一个结点的前面 （最后一个结点就是一个标识 不是具体的结点）
                   int x = in.nextInt();
                   add(l[1],x);
                }
                    break;
                case "L" :{
                   int x = in.nextInt();
                   add(0,x); 
                }
                    break;
                case "D" :{
                    int k = in.nextInt();
                    romove(k+1);
                    /*
                    为什么对第 k 个插入的数会变成对下标为（k+1）这个结点的操作？？？？

                    下标0放置的是第一个结点  下标1放置的最后一个结点 （虽然这两个结点都是空的 输出的时候不会输出这两个结点的值）
                    所有的插入操作可是在这两个结点之间进行插入的

                    显然第一个插入结点的存储位置是3 （0，1位置已经被占了） 所以对第k个插入的数操作会变成为位置k+1 （k是从1开始的）

                    */
                }
                    break;
                case "IL" :{
                    int k = in.nextInt();
                    int x = in.nextInt();
                    add(l[k+1],x);
                }
                    break;
                case "IR" :{
                    int k = in.nextInt();
                    int x = in.nextInt();
                    add(k+1,x);
                }
                    break;
                default: break;
            }
        }
        for(int i=r[0];i!=1;i=r[i]) System.out.print(e[i]+" ");
    }


    public static void init(){
        // 0是左端点，1是右端点    也就是位置0就是第一个结点  位置1就是最后一个元素
        r[0] = 1;
        l[1] = 0;
        idx = 2;
        //初始化就是假设这个链表里面已经有两个结点（假设有 是空的）了  
        //所以以后的添加操作就变成了在这两个结点之间的插入
        // 数组中位置0 即使第一个元素  位置1就是最后一个元素 后面的结点的插入就用数组位置2及以后的位置来存储
    }

    public static void add(int k ,int x){
        //在k结点的右边插入
        e[idx] = x;//插入结点的值
        l[idx] = k;//插入结点的上一个结点的位置
        r[idx] = r[k];//插入节点下一个节点的位置

        l[r[k]] = idx; //让k结点原来的下一个节的上一个位置指向插入结点
        r[k] = idx;   //让k结点的下一个结点指向插入结点的位置
        //这两句的顺序不能反
        idx++;
    }

    //删除结点
    public static void romove (int k){
        r[l[k]] = r[k]; //让第k个结点的右节点的左结点指向 k结点的右节点
        l[r[k]] = l[k];//让第k个结点的左节点的右结点指向 k结点的左节点
    }
}