你还在用结构体操作链表吗？

在算法考试中遇到链表的题目时，我们通常都不会使用结构体的方法来操作链表，对于C++而言，我们会频繁申请内存空间非常费时，因此我们可以考虑使用数组来实现链表。

单链表

• $e[N]$：存储节点值$value$
• $ne[N]$：存储某个节点的$next$指针（下个值在$e$数组中的下标）
• $head$表示头结点的下标
• $idx$表示已经用到了哪个点

初始化

#include <iostream>

using namespace std;

const int N = 100010;

int e[N], ne[N], idx, head;

/**
 * @brief 初始化
 */
void init () {
    head = -1;
    idx = 0;
}

插入到头节点

• 初始化当前节点$idx$
• 当前节点的$next$指针指向头结点
• 头结点重新指向当前结点，并使$idx++$

/**
 * @brief 将x插到头结点
 * @param x 
 */
void add_to_head (int x) {
    // 初始化当前节点
    e[idx] = x;
    // 当前节点的next指针指向头节点
    ne[idx] = head;
    // 头节点重新指向当前节点，并使idx++（当前节点用过）
    head = idx++;
}

插入结点

• 初始化当前结点$idx$
• 当前节点的$next$指针指向下标为$k$的结点的$next$指针
• 下标为$k$的结点$next$指针指向当前结点，并使$idx++$

/**
 * @brief 将节点 x 插入到下标为 k 的节点的后面
 * @param k 
 * @param x 
 */
void add (int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

删除节点

/**
 * @brief 将下标是k的点后面的点删除
 * @param k 
 */
void remove (int k) {
    ne[k] = ne[ne[k]];
}

遍历

for (int i = head; i != -1; i = ne[i])
        cout << e[i] << ' ';
    cout << endl;

双链表

• $e[N]$：存储节点值$value$
• $r[N]$：存储某个节点右边的$next$指针（右边的值在$e$数组中的下标）
• $l[N]$：存储某个节点左边的$next$指针（左边的值在$e$数组中的下标）
• $idx$表示已经用到了哪个点

初始化

• 初始化的时候一开始相当于就有两个结点，左端点$head$右端点$tail$，$idx$从$2$开始

#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

/**
 * @brief 初始化
 */
void init() {
    // 左端点head为0
    l[1] = 0;
    // 右端点tail为1
    r[0] = 1;
    idx = 2;
}

插入节点

• 初始化当前节点$idx$
• 当前节点的左指针指向节点$a$
• 当前节点的右指针指向节点$a$原来的右节点
• 结点$a$原来的右节点的左指针指向当前节点
• 结点$a$的右指针指向当前节点$idx$，并使$idx++$

/**
 * @brief 在节点a的右边插入一个数x
 * @param a 
 * @param x 
 */
void insert (int a, int x) {
    e[idx] = x;
    l[idx] = a;
    r[idx] = r[a];
    l[r[a]] = idx;
    r[a] = idx++;
}

删除节点

/**
 * @brief 删除节点a
 * @param a 
 */
void remove (int a) {
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

遍历

• 初始化是以$0$和$1$为两个空点加入双链表，所以$0$的右边就是第一个点$r[0]$，$1$的左边就是最后一个点$l[1]$

for (int i = r[0]; i != 1; i = r[i]) 
    cout << e[i] << ' ';
cout << endl;