1-单链表

算法思想

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

算法图解

算法模板

import java.util.*;

public class Main {
    static int N = 100010;
    // head 代表头结点的下一个节点的索引
    // e[i] 代表第 i 个节点的值
    // ne[i] 代表第 i 个节点的下一个节点的索引
    // idx 代表数组 e 中第一个未被使用的元素的索引
    static int head, idx;
    static int[] e = new int[N],
        ne = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        
        int order = 0;
        init();
        while(n -- > 0)
        {
            String op = in.next();
            int x;
            int k;
            switch(op)
            {
                case "H":
                    x = in.nextInt();
                    addToHead(x);
                    break;
                case "D":
                    k = in.nextInt();
                    if(k == 0) head = ne[head];
                    else remove(k - 1);
                    break;
                case "I":
                    k = in.nextInt();
                    x = in.nextInt();
                    // 第 k 个插入的数，
				    // 即为数组 e 中第 k - 1 个已经被使用的元素
                    add(k - 1, x);
                    break;
            }
        }
        
        while(head != -1)
        {
            System.out.print(e[head] + " ");
            head = ne[head];
        }
    }
    
    static void init()
    {
        head = -1;
        idx = 0;
    }
    
    static void addToHead(int x)
    {
        e[idx] = x;
        ne[idx] = head;
        head = idx ++;
    }
    
    static void remove(int k)
    {
        ne[k] = ne[ne[k]];
    }
    
    static void add(int k, int x)
    {
        e[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx ++;
    }
}