数组模拟链表

用数组模拟单链表

模拟最多的：邻接表（作用：存储图和树）

public class Main {
    final int N = 10010;
    //head 表示头节点的下标
    //idx 存储当前已经用到了那个点
    //e[i] 表示节点i的值
    //ne[i] 表示节点i的next指针是多少
	int head, idx;
    int[] e = new int[N];
    int[] ne = new int[N];
    
    //初始化
    public static void init() {
        head = -1;
        idx = 0;
    }
    //将x插入到头节点
    public static void add_to_head(int x) {
        e[idx] = x, ne[idx] = head, head = idx++;
    }
    //将x插入到下标为k的点后面
    public static void add(int k, int x) {
        e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
    }
    //将下标为k的点后面删除
    public static void remove(int k) {
        ne[k] = ne[ne[k]];
        //注意判断当k为头节点时的情况
        if (!k) head = ne[head];
    }
}

用数组模拟双链表

模拟最多的：优化一些问题

public class Main {
    final int N = 10010;
    //idx 存储当前已经用到了那个点
    //e[i] 表示节点i的值
    //l[i] 表示节点i的左边
    //r[i] 表示节点i的右边
	int	idx;
    int[] e = new int[N];
    int[] l = new int[N];
    int[] r = new int[N];
    
    //初始化
    public static void init() {
		//0表示左端点，1表示右端点
        r[0] = 1, l[1] = 0;
        idx = 2;
    }
    //将x插入到下标为k的点后面
    public static void add(int k, int x) {
        e[idx] = x;
        r[idx] = r[k];
        l[idx] = k;
        l[r[k]] = idx;
        r[k] = idx;
    }
    //将下标为k的点删除
    public static void remove(int k) {
		r[l[k]] = r[k]
        l[r[k]] = l[k];
    }
}