2、数组模拟单链表

AcWing 826. 单链表

import java.util.*;

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

    int N = 100010;
    int idx, head;
    //e[idx-1]即为第idx次插入的结点值
    int e[] = new int[N];
    int ne[] = new int[N];

    void init() {
        head = -1;
        idx = 0;
    }

    //插入点到头结点
    void add_to_head(int x) {
        e[idx] = x;
        ne[idx] = head;
        head = idx++;
    }

    //将x插入到k为下标的点后面
    void add(int k, int x) {
        e[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx++;
    }

    void remove(int k) {
        ne[k] = ne[ne[k]];
    }

    void danlianbiao() {
        init();
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        for (int i = 0; i < M; i++) {
            String c = scanner.next();
            int k = scanner.nextInt();
            if (c.equals("H")) {
                add_to_head(k);
            }
            if (c.equals("D")) {
                //注意删除表头的时候
                if (k == 0) head = ne[head];
                else remove(k - 1);
            }
            if (c.equals("I")) {
                int x = scanner.nextInt();
                add(k - 1, x);
            }
        }
        for (int i = head; i != -1; ) {
            System.out.print(e[i] + " ");
            i = ne[i];
        }
    }
}