链表

• 为什么不用class存储节点，new生成节点？在数据量很大的时候，开辟空间会花去大量时间，会造成题目的TLE
• 在大数据量的题目中，用数组模拟链表
• 删除元素不需要改变idx的值，数据量很大，不方便回头维护，所以直接牺牲一个位置的空间来简化代码以及增强可维护性

单链表模板题

Java代码

import java.io.*;
public class Main{
    private static final int N = 100010;
    private static int head;//头节点的下标
    private static int[] e;//存储每个节点的值
    private static int[] ne;//存储每个节点的下一个节点下标
    private static int idx;//当前使用到的节点下标
    //初始化
    static void init(){
        head = -1;
        idx = 0;
    }
    //在头部添加节点
    static void add_head(int x){
        e[idx] = x;
        ne[idx] = head;
        head = idx;
        idx++;
    }
    //将x插入下标为k的点后面
    static void add(int k, int x){
        e[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx++;
    }
    //删除下标为k的节点后面的节点
    static void remove(int k){
        ne[k] = ne[ne[k]];
    }
    public static void main(String[] args) throws IOException{
        e = new int[N];
        ne = new int[N];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        init();
        while(n-->0){
            String[] s = br.readLine().split(" ");
            if(s[0].equals("H")){
                add_head(Integer.parseInt(s[1]));
            }else if(s[0].equals("I")){
                int k = Integer.parseInt(s[1]);
                int x = Integer.parseInt(s[2]);
                add(k-1,x);
            }else{
                int k = Integer.parseInt(s[1]);
                //删除头节点特判
                if(k == 0) head = ne[head];
                else remove(k-1);
            }
        }

        for(int i = head; i != -1; i = ne[i]){
            System.out.print(e[i]+" ");
        }

        br.close();
    }
}

双链表模板题

• l，r数组：下标表示第几个节点(节点下标)，内容表示左/右节点的下标

Java代码

import java.io.*;
public class Main{
    private static final int N = 100010;
    private static int[] e,l,r;
    private static int idx;
    //初始化
    static void init(){
        e = new int[N];
        l = new int[N];
        r = new int[N];
        r[0] = 1;
        l[1] = 0;
        idx = 2;
    }
    //在第k个节点后面插入一个值为x的节点
    static void add(int k, int x){
        e[idx] = x;
        r[idx] = r[k];
        l[idx] = k;
        l[r[k]] = idx;
        r[k] = idx;
        idx++;
    }
    //删除第k个节点
    static void remove(int k){
        r[l[k]] = r[k];
        l[r[k]] = l[k];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        init();
        while(n-- > 0){
            String[] s = br.readLine().split(" ");
            if(s[0].equals("L")){
                add(0,Integer.parseInt(s[1]));
            }else if(s[0].equals("R")){
                add(l[1],Integer.parseInt(s[1]));
            }else if(s[0].equals("D")){
                int k = Integer.parseInt(s[1]);
                remove(k+1);
            }else if(s[0].equals("IL")){
                int k = Integer.parseInt(s[1]);
                int x = Integer.parseInt(s[2]);
                add(l[k+1],x);
            }else{
                int k = Integer.parseInt(s[1]);
                int x = Integer.parseInt(s[2]);
                add(k+1,x);
            }
        }
        for(int i = r[0]; i != 1; i = r[i]){
            System.out.print(e[i]+" ");
        }
    }
}