2-双链表

算法思想

1. 用数组分别存储节点值、上一个节点的索引和下一个节点的索引

算法模板

import java.util.*;

public class Main {
    static int N = 100010;
    static int[] e = new int[N];
    // 数组 l 存储向前（从右往左）的链接
    static int[] l = new int[N];
    // 数组 r 存储向后（从左往右）的链接
    static int[] r = new int[N];
    // idx 代表数组 e 中首个未被使用的元素
    static int idx;
    // head 代表首节点，end 代表尾节点
    static int head, end;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        init();    
        while(m -- > 0)
        {
            String op = in.next();
            int k, x;
            
            switch(op)
            {
                case "L":
                    x = in.nextInt();
                    insert(head, x);
                    break;
                case "R":
                    x = in.nextInt();
                    insert(l[end], x);
                    break;
                case "D":
                    k = in.nextInt();
                    remove(k + 1);
                    break;
                case "IL":
                    k = in.nextInt();
                    x = in.nextInt();
                    insert(l[k + 1], x);
                    break;
                case "IR":
                    k = in.nextInt();
                    x = in.nextInt();
                    // 第 k 个插入的数，
				    // 即为数组 e 中第 k + 1 个已经被使用的元素
                    insert(k + 1, x);
                    break;
            }
        }
        
        head = r[head];
        while(head != end)
        {
            System.out.print(e[head] + " ");
            head = r[head];
        }
    }
    
    static void init()
    {
        head = 0;
        end = 1;
        r[head] = end;
        l[end] = head;
        
        idx = 2;
    }

    // 在第 k 个插入的数的右边插入一个数 x
    static void insert(int k, int x)
    {
        e[idx] = x;
        // 先设置向左的指针
        l[r[k]] = idx;
        l[idx] = k;
        // 再设置向右的指针
        r[idx] = r[k];
        r[k] = idx ++;
    }
    
    static void remove(int k)
    {
        r[l[k]] = r[k];
        l[r[k]] = l[k];
    }
}