Introduction

传统的链表是定义一个结构体，里面套娃一个结构体类型的指针，指向链表下一个元素（结构体）。这样在访问的时候需要通过指针的索引来找到目标的位置。

数组模拟链表：用两个数组来分别表示结构体的数值和next指针，相等的下标表示他们是同一个节点

Train of Thought

基本变量的初始化

我们需要用到四个变量，表示头指针，数值，指针，和数组的下标

head：头指针，初始化时为-1，即为NULL

e[]：数值数组，用于存储节点的数值

ne[]：指针数组，用于存储下一个节点的地址，也就是下一个节点的数组下标

idx：用于存储用到的数组下标

核心思想：把数组下标当成地址

基本函数

init——初始化函数

不需要传入参数，直接赋值

void init () {
    head = -1;
    // head赋值为-1，表示链表中还没有元素，指向为空。因为数组下标从0开始
    idx = 0;
    // idx是即将用到的数组下标
    // 即将用到——下次插入的新节点，就使用idx作为下标/地址
}

add_to_head——头插法，将新节点插入到头指针的后面，称为第一个节点

传入一个参数，是新节点的数值

void add_to_head(int x) {
    // 传入的参数为x
    e[idx] = x;
    // idx是即将用到的下标/地址，给新节点使用
    ne[idx] = head;
    // 新节点的next指针，需要指向原来head指向的地址
    head = idx;
    // head头指针等于新节点的地址 
    idx ++;
    // 用到的数组下标加一
}

注：ne的赋值和head的赋值不可以交换顺序，一定要让ne先指向后面的节点，然后再让head指向新节点

另外，后面两条语句也可以合并成：head = idx ++;

add——随机插入，插入到下标为k的节点的后面

void add(int k, int x ) {
    // k为前面的节点的地址/下标
    e[idx] = x;
    ne[idx] = ne[k];
    // 先把k节点的next指针存储到新节点的next指针
    ne[k] = idx;
    // 让k节点的next指针指向新节点
    idx ++;
}

remove——删除下标为k的节点后面的节点

void remove (int k ) {
    ne[k] = ne[ne[k]];
}

直接移动下标为k的节点的next指针，指向下一个节点的下一个节点的地址即可

Question

$$ \begin{align} &实现一个单链表，链表初始为空，支持三种操作：\\ &1.向链表头插入一个数；\\ &2.删除第 k 个插入的数后面的数；\\ &3.在第 k 个插入的数后插入一个数。\\ &现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。\\ &\textbf{注意}:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。\\ &\textbf{输入格式}：\\ &第一行包含整数 M，表示操作次数。\\ &接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：\\ &1.H x，表示向链表头插入一个数 x。\\ &2.D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。\\ &3.I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。\\ &\textbf{输出格式}：\\ &共一行，将整个链表从头到尾输出。\\ &\textbf{数据范围}：\\ &1≤M≤100000\\ &所有操作保证合法。\\ \end{align} $$

输入样例：

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

6 4 6 5

思路

remove操作中，要求判断：如果输入为0，则删除头节点。实际上是让头指针指向第二个节点，代码实现：

if (!k) {
    head = ne[head];
} else {
    remove(k - 1);
}

另外，当需要用到随机访问位置时，即add和remove操作，需要注意题中描述，是数组下标还是第i个添加的节点。

由于addandremove函数中操作的是数组下标，从0开始，所以：如果是数组下标，则直接传入参数k；如果是节点序数，则传入参数k - 1，因为第k个插入的节点，其下标是k - 1

Introduction

每个节点存储三个内容，分别是值e[idx]，左指针和右指针，分别保存左右节点的位置（数组下标）

对比单链表

head头指针：单链表需要一个头指针来存储头节点的地址，但是双链表一般不需要

基本函数

初始化

对于双链表，我们需要给他一个左右端点。不妨左端点下标为0，右端点下标为1。但是这两个端点都没有存储的数据，只是作为端点，在输出链表时也不会输出这两个端点

void init () {
    r[0] = 1;
    l[1] = 0;
    idx = 2; // 已经用了0、1下标，下次从2开始使用
}

插入

无论随机插入的位置，即不需要考虑在第i个节点的左侧/右侧插入，我们只需要实现一个插入函数，然后根据插入位置修改传入参数即可。实现在下标为k的节点右侧插入一个节点

void insert(int k, int x ) {
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    // 下面这两个操作的顺序不能交换！！！
    l[r[k]] = idx;
    r[k] = idx;
    // 因为需要先使用原r[k]，再改变r[k]
    idx ++;
}

删除

比较简单，直接删除下标为k的节点：把k节点左侧节点的右指针指向k节点的右侧节点；把k节点右侧节点的左指针指向k节点的左侧节点

void remove (int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

思路

与单链表非常不同！涉及访问位置的操作，传入参数应该是k + 1：第k个插入的节点，下标是k + 1。因为最开始已经有两个左右端点，下标idx从2开始，即第1个插入的节点，下标为2。