🌈个人主页：聆风吟
🔥系列专栏：算法模板、数据结构
🔖少年有梦不应止于心动，更要付诸行动。
文章目录
📋前言
一. ⛳️使用数组模拟单链表讲解
1.1 🔔为什么我们要使用数组去模拟单链表？
假如你学过数据结构，那么你对链表的第一反应可能就是：由一系列结点组成，每个结点包含两个域，其中一个域用于存储数据元素，另一个域用于存储下一个结点的地址。节点的表示形式如下：
class Node{
public:
int val;
Node* next;
};
这种构造形式是我们常见的，使用该方法，在创建 一个值为 x 的新结点的时候，语法如下：
Node* node = new Node();
node->val = x
代码分析：Node* node = new Node();，中间有一个 new 关键字来为新对象分配空间。new 的底层涉及内存分配，调用构造函数，指针转换等多种复杂且费时的操作。由于一秒大概只能 new 一万次左右。在平时的工程代码中，不会涉及上万次的new操作，所以这种使用这种结构创建单链表是一种 见代码知意 的好结构。
但是在算法比赛中，经常碰到在10w级别以上的链表操作，如果使用结构体这种方式创建链表，是无法在算法规定时间完成的。因此，在算法比赛这种有严格的时间要求的环境中，不能频繁使用new操作。所以在这里我们采用数组去模拟单链表。
1.2 🔔用数组模拟实现单链表
1.2.1 👻整体框架说明
初始状态：将头指针head指向空结点。
插入结点状态：
- 创建数组
val和ne分别存储某个结点的值和指向下个结点的next指针； - 使用数组下表进行关联，通过数组ne将整个链表链接起来；
- 空结点的下表用 - 1 来表示；
### 1.2.2 👻单链表查找和修改 因为是使用数组模拟出来的链表，所以对于查找和修改直接通过数组下标进行遍历查找即可，这里就不多叙述。
1.2.3 👻单链表插入结点
代码展示（建议结合图示看注释）：
//将x插到头结点
//idx 存储当前已经用到了哪个点,即记录当前下标位置
void add_to_head(int x)
{
val[idx] = x;//记录要插入结点的数据
ne[idx] = head;//将待插结点指向头结点
head = idx;//断开头指针head指向的头结点的箭头，改为指向待插入结点
idx++;//下标向后移一位，为下一次插入元素做准备。
}
代码展示（建议结合图示看注释）：
//将x插到下标是k的结点后面
//idx 存储当前已经用到了哪个点,即记录当前下标位置
void add(int k, int x)
{
val[idx] = x;//记录要插入结点的数据
ne[idx] = ne[k];//将待插结点指向下标为k结点的下个结点
ne[k] = idx;//断开下标为k到k+1结点的箭头，将下标为k的结点改为指向待插入结点
idx++;//下标向后移一位，为下一次插入元素做准备。
}
1.2.4 👻单链表删除结点
代码展示（建议结合图示看注释）：
//将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];//让k指向的改为指向下下个结点，那中间的那个结点就被挤掉了。
}
1.3 🌟模板提取(重点)🌟
模板代码
// head 表示头结点的下标
// val[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点，即记录当前下标位置
int head, val[N], ne[N], idx;
//初始化
void init()
{
head = -1;//将头指针head指向空结点。
idx = 0;//下标置为0
}
//将 x 插入到头结点
void add_to_head(int x)
{
val[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//将 x 插入到下标是k的结点后面
void add(int k, int x)
{
val[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
二. ⛳️题目练习
2.1 题目
2.2 输入样例
2.3 输出样例
2.4 c++代码
#include <iostream>
using namespace std;
const int N = 100010;
// head 表示头结点的下标
// val[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点，即记录当前下标位置
int head, val[N], ne[N], idx;
//初始化
void init()
{
head = -1;
idx = 0;
}
//将 x 插入到头结点
void add_to_head(int x)
{
val[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//将 x 插入到下标是k的结点后面
void add(int k, int x)
{
val[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
init();//切记：初始化
while(m--)
{
int k, x;
char op;
cin >> op;
//判断执行哪种操作
if(op == 'H')
{
//执行头插操作
cin >> x;
add_to_head(x);
}
else if(op == 'D')
{
//执行删除操作
cin >> k;
if(k == 0) head = ne[head];//删除头节点
remove(k - 1);//注意删除第k个输入后面的数，那函数里放的是下标，k要减去1
}
else
{
//执行指定位置插入操作
cin >> k >> x;
add(k - 1, x);
}
}
for(int i = head; i != -1; i = ne[i]) cout << val[i] << " ";
cout << endl;
return 0;
}
📝结语
今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！