题目描述

双链表

JAVA 代码

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

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

    static void init(){
        l[1] = 0;
        r[0] = 1;
        idx = 2;
    }
    static void remove(int k){
        l[r[k]] = l[k];
        r[l[k]] = r[k];

    }

    //双链表模板. 
    static void add(int k, int x){
        e[idx] = x;
        l[idx] = k;
        r[idx] = r[k];
        l[r[k]] = idx;
        r[k] = idx++;

    }

    public static void main(String args[])throws IOException{

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        init();
        m = Integer.parseInt(in.readLine());
        while(m --> 0){
            String[] s1 = in.readLine().split(" ");

            String e = s1[0];

            //主要好插入位置. 插入最左为 0
            if(e.equals("L" )){
                int x = Integer.parseInt(s1[1]);
                add(0, x);

            }else if(e.equals("R" )){
                int x = Integer.parseInt(s1[1]);

                //最右为 头结点的左边. 
                add(l[1], x);
            }else if(e.equals("D" )){
                int k = Integer.parseInt(s1[1]);

                //要删除的节点是下一个节点. 
                remove(k+1);
            }else if(e.equals("IR" )){
                int k = Integer.parseInt(s1[1]);
                int x = Integer.parseInt(s1[2]);
                //往右新增也是一样. 
                add(k+1, x);
            }else{// IL
                int k = Integer.parseInt(s1[1]);
                int x = Integer.parseInt(s1[2]);
                //往左新增则需要算出左边位置. 
                add(l[k+1], x);
            }
        }

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

}