全文目录
- 😀 数组实现的优势
- 🤔 单链表
- 😕 初始化
- 😕 头插
- 😕 在下标 `k` 后面插入元素
- 😕 删除下标 `k` 后面的元素
- 😕 遍历
- 😵💫 双链表
- 🤨 初始化
- 🤨 插入
- 🤨 删除元素
- 🤨 遍历
😀 数组实现的优势
链表在很多语言的标准库里面都有，基本上是通过 Node 节点来链接下一个节点实现的：
struct Node
{int _data;Node* _next;Node* _prev; // 双链表
}
这样的链表使用起来虽然方便，但是有两个缺点：
- 空间更大，因为有内存对齐的存在
- 如果有大量的节点，那么会在耗费大量的时间来开辟节点，效率低
所以一般，如果数据是整数的话可以使用数组来代替链表，可以大幅度地提升效率。
🤔 单链表
通过数组实现，需要用到两个数组，一个用来存放数据 e[]，一个用来存放下一个节点的下标 ne[]，一个用来标记头结点的位置 head，一个用来标记下一个需要用到的位置 index 。
实现的样子大概是这样：
😕 初始化
void init()
{head = 0;index = 1;
}
同样也可以 head = -1, index = 0 来进行初始化，但是这样的话，后面的操作下标都需要 -1 ，所以个人感觉 上一种方式处理起来更加方便。
😕 头插
void add_head(int x)
{e[index] = x;ne[index] = head;head = index;index ++;
}
这里需要清楚的是，如果是没有数据的话，那么节点一定是头插的。这样才能保证 head 的更新和顺利找到尾结点。
😕 在下标 k 后面插入元素
void add(int k, int x)
{e[index] = x;ne[index] = ne[k];ne[k] = index;index ++;
}
😕 删除下标 k 后面的元素
void remove(int k)
{ne[k] = ne[ne[k]];
}
😕 遍历
for (int i = head; i; i = ne[i])
{cout << e[i] << ' ';
}
遍历可能会有一些误导，需要找到初始化的 head 才算是到了尾，
首先这个head指的是链表中头节点的下标，当链表中没有节点时head = 0，但当链表中有值插到头节点的时候，head储存的就是这个值的idx1，通过e[idx1]可以求出这个节点的值。而ne[idx1]就等于head之前的值，即0。如果再在头节点插入一个元素，则head指向这个元素的idx2，而ne[idx2]就等于上一次插入的head值，即idx1。此时，head = idx2，ne[idx2] = idx1，ne[idx1] = 0。若真正理解了这个过程，你的问题就迎刃而解了。拿上述链表举例，在循环链表时，初始的i = head，除非链表为空，否则这个head的值一定不为0，其值应为链表中第一个节点的idx2值，输出e[i]后，有i = ne[i]，其含义为i = ne[dix2]，由上述论证可知，ne[idx2] = idx1，则i = idx1，满足i != 0，输出e[i]的值。又有i = ne[i]，即为i = ne[idx1]，可知ne[idx1] = 0，则i = 0，不满足i != 0的循环条件，故循环退出。这个链表的循环依次输出了e[idx2]，e[idx1]，即链表中的前后两个节点。
😵💫 双链表
因为双链表有左右两个指针，所以在实现的时候需要三个数组，一个存储元素 e[]，一个存储左节点的下标 l[]，一个存储右节点的下标 r[]，index 表示用到的下标。
🤨 初始化
初始化数组时，给定左边界和右边界。头结点是从左边界的下一个开始，尾结点就是右边界的前一个。这样可以方便头插和尾插，所以就给定 0为左边界， 1 为右边界， index 从2开始。
因为 index 是从2开始的，所以后面的关于下标的操作都需要加上1
// 初始化
void init()
{r[0] = 1; // 头结点l[1] = 0; // 尾结点index = 2; // 元素的下标从2开始，后面的下标也都需要+1
}
这样初始化可能会觉得很变扭，有点违背我们的思维方式，就会想index能不能从1开始，右边界取2。
答案是不能的，这样会导致index在向后走的时候可能取到右边界，那么对index 进行操作就会导致右边界发生变化。所以要保证 index 不能取到右边界。
🤨 插入
因为是双链表，可以直接找到前一个节点，所以在 k 的左边插入可以表示成在 k 的前一个节点的后面插入，头插就是在左边界的后面插入，尾插就是在右边界的前一个节点后面插入。因此只实现一个插入就好了。
// 在当前节点的后面插入
void insert(int k , int x)
{e[index] = x; r[index] = r[k];l[index] = k;l[r[k]] = index;r[k] = index;index++;
}头插：insert(0, x); // 头插就是在头结点的右边插入尾插：insert(l[1], x); // 尾插就是在尾结点的左边插入在k的左边插入：insert(l[k + 1], x); // 在左节点的后面插入在k后插入：insert(k + 1, x); // 正常插入
🤨 删除元素
// 删除当前节点
void remove(int k)
{r[l[k]] = r[k]; l[r[k]] = l[k];
}
🤨 遍历
同样的，双链表的遍历只要找到右边界的位置就好了
for (int i = r[0]; i != 1; i = r[i])
{cout << e[i] << ' ';
}
完结散花🌈🌈🌈
