题目链接：https://www.acwing.com/problem/content/description/828/

1.思路

利用数组模拟链表，e为链表存储的值，ne为指向下一个元素的指针，head为头节点，idx存储当前已经用到了哪个点。

2.代码模板

import java.util.*;
public class Main{
    public static int N = 100000;
    public static int[] e = new int[N]; //存储值
    public static int[] ne = new int[N];    //存储下一个指针坐标
    public static int head = -1;    //头节点
    public static int idx = 0;  //idx 存储当前已经用到了哪个点

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n --> 0) {
            String s = in.next();
            if (s.equals("H")) 
                insertHead(in.nextInt());   //表示向链表头插入一个数 x
            else if (s.equals("I")) 
                insert(in.nextInt() - 1, in.nextInt()); //表示在第 k 个插入的数后面插入一个数 x
            else if (s.equals("D")) {
                int k = in.nextInt();
                if (k == 0)         //表示删除头结点
                    head = ne[head];
                else
                    delete(k - 1);  //表示删除第 k 个插入的数后面的数
            }
        }
        for (int i = head; i != -1; i = ne[i])  //遍历链表
            System.out.print(e[i] + " ");
    }
    //表示在第 k 个插入的数后面插入一个数 x
    public static void insert(int k, int x) {
        e[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx++;
    }
    //表示向链表头插入一个数 x。
    public static void insertHead(int x) {
        e[idx] = x;
        ne[idx] = head;
        head = idx++;
    }
    //表示删除第 k 个插入的数后面的数
    public static void delete(int k) {
        ne[k] = ne[ne[k]];
    }
}

3.复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(n)