2、数组模拟双链表

AcWing 827. 双链表

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.danlianbiao();
    }

    int N = 100010;
    int idx;
    int e[] = new int[N];
    int l[] = new int[N];
    int r[] = new int[N];

    //在a号点的的右结点插入一个数
    void insert(int a, int x) {
        e[idx] = x;
        l[idx] = a;
        r[idx] = r[a];
        l[r[a]] = idx;
        r[a] = idx++;
    }

    //删除结点a
    void remove(int a) {
        r[l[a]] = r[a];
        l[r[a]] = l[a];
    }

    void danlianbiao() {
        //100000的右节点是100001
        //100001的左节点是100000
        //其他所有点都建立在100000-100001的基础上
        //完成以上步骤后，设定初始idx为0
        r[100000]=100001;
        l[100001]=100000;
        idx=0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String d = scanner.next();
            if (d.equals("L")) {
                int k = scanner.nextInt();
                insert(100000, k);
            }
            if (d.equals("R")) {
                int k = scanner.nextInt();
                insert(l[100001], k);
            }
            if (d.equals("D")) {
                int k = scanner.nextInt();
                remove(k-1);
            }
            if (d.equals("IL")) {
                int k = scanner.nextInt();
                int x = scanner.nextInt();
                insert(l[k-1],x);
            }
            if (d.equals("IR")) {
                int k = scanner.nextInt();
                int x = scanner.nextInt();
                insert(k-1,x);
            }
        }

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

另一种按照0-1为分界的写法，idx开始设为2

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.danlianbiao();
    }

    int N = 100010;
    int idx;
    int e[] = new int[N];
    int l[] = new int[N];
    int r[] = new int[N];

    //在a号点的的右结点插入一个数
    void insert(int a, int x) {
        e[idx] = x;
        l[idx] = a;
        r[idx] = r[a];
        l[r[a]] = idx;
        r[a] = idx++;
    }

    //删除结点a
    void remove(int a) {
        r[l[a]] = r[a];
        l[r[a]] = l[a];
    }

    void danlianbiao() {
        //0的右节点是1
        //1的左节点是0
        //其他所有点都建立在0-1的基础上
        //完成以上步骤后，设定初始idx为2
        r[0]=1;
        l[1]=0;
        idx=2;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String d = scanner.next();
            if (d.equals("L")) {
                int k = scanner.nextInt();
                insert(0, k);
            }
            if (d.equals("R")) {
                int k = scanner.nextInt();
                insert(l[1], k);
            }
            if (d.equals("D")) {
                int k = scanner.nextInt();
                remove(k+1);
            }
            if (d.equals("IL")) {
                int k = scanner.nextInt();
                int x = scanner.nextInt();
                insert(l[k+1],x);
            }
            if (d.equals("IR")) {
                int k = scanner.nextInt();
                int x = scanner.nextInt();
                insert(k+1,x);
            }
        }

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