题目描述

主要思想

就是利用数组模拟去模拟插入、删除操作
插入包括在头节点和第k个插入的数字的后面插入两种形式
(第k个插入的数字，是从1开始的，每一第k个位置的操作的时候都需要加减1，数组下标从0开始)

需要用到的几个变量
e[]，存储当前节点的value
ne[],存储指针，当前节点的下一节点
idx，主要表示的是数组的下标，在进行第k个数的插入和删除操作时，o(1)的时间复杂度内找到ne[idx]
head,存储头节点的下标，初始化的时候记为-1，在链表头部插入一个元素之后更新为0

package dbfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 单链表 {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */

    static int M=100010;
    static int e[]=new int [M];
    static int ne[]=new int [M];
    static int idx=0;
    static int  head=0;

    public static void init() {
        head=-1;
    }
    public static void  Add_head(int x) {
        e[idx]=x;
        ne[idx]=head;
        head=idx;
        //头节点的下标指向idx,此时的idx等于0
        idx++;
    }
    public static void Remove(int k) {
        ne[k]=ne[ne[k]];
    }
    public static void  Add(int k,int x) {
        e[idx]=x;
        ne[idx]=ne[k];
        ne[k]=idx;
        idx++;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(bufferedReader.readLine());
    int k=0,x=0;
    init();

//初始化链表，head=-1,表示链表为空
    while(n>0){
        String pString[]=bufferedReader.readLine().split(" ");
        if(pString[0].equals("H")){

            k=Integer.parseInt(pString[1]);
            Add_head(k);
        }
        if(pString[0].equals("D")){
            k=Integer.parseInt(pString[1]);
            if(k==0){
                head=ne[head];
            }else{
                Remove(k-1);
            }

        }
        if(pString[0].equals("I")){
            k=Integer.parseInt(pString[1])-1;
            x=Integer.parseInt(pString[2]);
            Add(k, x);
        }
        n--;
    }
    for (int i = head; i != -1; i = ne[i]){
        System.out.println(e[i]);
    }

    }

}