题目描述
实现一个单链表，链表初始为空，支持三种操作：
(1) 向链表头插入一个数；
(2) 删除第k个插入的数后面的数；
(3) 在第k个插入的数后插入一个数
现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。
输入格式
第一行包含整数M，表示操作次数。
接下来M行，每行包含一个操作命令，操作命令可能为以下几种：
(1) “H x”，表示向链表头插入一个数x。
(2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。
(3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
样例
输入样例：
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
算法1
时间复杂度分析：链表在插入的时候可以达到O(1)的复杂度
理解
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
解释一下 就先把值赋到数据域，然后让head的地址值存入指针域，让idx向下移一位；
//向表中k位置插图x
void add(int k,int x){
n[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
// 将k删除，需要保证头结点存在
void remove(int k)
{
ne[k]=ne[ne[k]];
}
这个与插入思想类似：
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
int idx,head,n[N],ne[N];
int a;
void add_head(int x){
n[idx]=x;
ne[idx]=head;
head=idx++;
}
void add(int k,int x){
n[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
void remove(int k){
ne[k]=ne[ne[k]];
}
int main(){
head=-1;idx=0;
cin>>a;
while(a--){
string op;
int k,x;
cin>>op;
if(op=="D")
{
cin>>k;
if(!k)head=ne[head];
remove(k-1);
}
else if(op=="H")
{
cin>>x;
add_head(x);
}
else if(op=="I"){
int k,x;
cin>>k>>x;
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i])
cout<<n[i]<<" ";
return 0;
}
感谢
感谢以下巨巨是对本题理解勘错与问题深化：
【@dfbdberberb】
【@cdd_1】
【@Anish】
我看到好多人问idx的问题 ：不知道他们是不是和我刚才一样困惑的点一样：我刚想明白：
(要明白数组下标联系的是e与ne的关系，所以前后的节点的数组下标不需要连续！！！所以idx只是记录当前的操作的位置)
大师 我悟了
感谢
大师我爱你
大师我爱你
# 大师 我悟了
我帮大家大概总结了评论区的问题，欢迎来访问：
https://blog.csdn.net/m0_74215326/article/details/128770930
cin>>k; if(!k)head=ne[head]; remove(k-1);删除这里应该加上else吧，不然k = 0时-1依然会传进去
嗯嗯，但是为啥不会报错呢。。
因为比如数组int a[N]。我尝试了输出a[-1]居然是存在的，只是值是不确定的。。。所以不会报错
好的，还有个问题，y总的单链表模板里没有加哑头节点，否则就不需要特判了。但是y总双链表加了两个哑头。。。
你可以理解为划分一段空间，a[-1]是a前面的一个地址
强啊老哥，刚准备评论求解这个问题
好细心欸，赞
为什么是用数组来模拟链表，这样不是得开辟连续的内存空间吗，为什么不用指针呢？背离链表存在的意义了呀
这里的链表是一种抽象的数据结构，每个节点有信息和下一个节点的地址，和怎么实现半毛钱关系也没有。链表当然也可以用数组实现，也可以用STL的vector，都不用动态allocate。
对于指针，我们来看一下静态域动态的区别：
数组静态分配内存，链表动态分配内存;
数组在内存中连续，链表不连续;
数组元素在栈区，链表元素在堆区;
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n);
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1);
是的，我俩说的不一样，代码这里说的链表是逻辑上的，是依赖数组实现的。我说的链表是直接操作内存、地址不连续的存储结构，之前学C的时候，我写链表都是用struct{ int val; Node* next;} 这样写。。。你这里说的是一种逻辑结构，不关心它是如何实现的，我明白了，多谢啦。
Y总说 数组来模拟静态链表不容易超时， new一个node花费的时间很容易超时~
所以做题时用 数组来模拟 静态链表~
### 单链表
单链表在算法竞赛或者在笔试里最常用的作用就是写邻接表，邻接表的作用是存储树和图
这里单链表我们用数组模拟，也可以采用结构体模拟；后者更好理解但是在算法竞赛中出于对效率的考虑，我们用数组模拟单链表（以及后续的所有数据结构）
当然也可以使用C++或是Java自带的单链表，但是这些效率都不如数组高
这里实现的单链表又叫静态链表，写工程的时候常用动态链表
有几个问题:
1.针对k=0时,会导致对-1号结点进行删除,然而链表中不存在-1号结点,但是不会报错,我debug了看了一下ne[-1]=0,不知道大家是不是都是0?在python中负数索引表示数组中倒数第几个,c++是否有这样的机制?
2.同上述问题,在删除最后一个结点时也会出现ne[-1]这个状态.
3.一般动态链表都会增加虚拟头尾结点来避免特判,静态链表是否也可以做到呢?
for(int i=head;i!=-1;i=ne[i]){
cout<<e[i]<<” “; 这个是正着输出链表还是倒着输出？
从头到尾
head表示的是指向头节点的指针吗？
head指向第一个元素，保存的是第一个元素的下标
头节点是不是第一个元素？
是的
https://blog.csdn.net/weixin_49486457/article/details/122825779?spm=1001.2014.3001.5502
很棒很棒，这个很好理解哇！！！点赞了
一看就懂了
蟹蟹
为什么删除头结点不是删除整个链表（头结点将其他结点串连起来的），而是让它指向head=ne[head];（是因为静态链表吗），求解，头大！！！
删除头结点是head指向的结点，也就是链表中的第一个结点，head指向可能是一个空结点（e数组不存值），或者是非空结点。指向空结点的叫头结点，指向非空结点的叫首元结点。但是y总并没有区分这个概念，所以删除头结点就是删除链表的第一个有值的结点，head指向ne[head]是因为head本来就指向它的下一个结点，所以ne[head]就是头结点的下一个结点~
嗯，就是区分头结点的定义比较模糊这道题，但是解释的非常漂亮
嘿嘿
这个解释非常漂亮，我也懂了，就是说我们按y总的意思这里的头结点是所谓的“首元节点”对吧。虽然但是，这个代码不严谨的地方在于，k==0时，删除头节点之后，并没有else，也就是说还回去执行下一句remove(k-1),显然此时k-1=-1，那么删除的时候不应该会报错吗，毕竟数组下标不能是-1
emmm，我看了一下代码，确实不严谨，准确来说因为remove函数只支持删除第k个插入的数，但是head指向的是idx，idx并不是一直为0，所以操作的过程中，0并不一定是头结点，所以需要这个判断。-1确实是越界了，但是越界不代表不能访问，很多时候不会报错，取到的是随机值，所以代码相当于删除头结点的前驱结点。正确的写法应该加上else
移除的话，不就是ne[3]= ne[2]吗，那这样原来数组不是没移除掉
、
删除第k次插入的数后面的数，第k次插入的数后面可能没有数，因此当输入以下样例时你的代码会TLE
3
H 9
H 8
D 1
为什么要是head=ne[head],他不是说删除头结点嘛 那不该是赋成-1
这里是删除头结点，如果后面还有元素，就需要再有一个头结点，指向后面的元素！如何后面没有元素当然可以这样删除，相当于重新建立一个，当然还要清空其他相关地址·数组
清空单链表的操作：为什么不能写成if(!k) head = -1;
改变它的前索引，有着改变地址的意思，就像Java中GC垃圾回收机制一样！
D操作时，k=0时，应该要做else处理，不然都调用remove，传入进去是-1, ne数组索引是非负，这样会导致越界。用vector应该就可以抛出边界跨越异常了
测试了一次应该没有这个问题存在，巨巨您可以否提供一下相关的测试数据？然后我做相应的修改
ne数组并没有赋值-1，为什么最后循环的时候条件是
i != -1呢，不太明白开始add_head的时候head是-1
好哒～搞明白啦～
leetcode链表写了能有20多道题了，到acwing上后，看这单链表一脸懵逼。果然是学的不太行
leetcode上我一直都用动态链表做的o(╥﹏╥)o，在acwing学到了静态链表。
大佬，请问为什么删除操作不能写成ne[k] = ne[idx];
k指向的节点不一定是idx，ne[ne[k]]表示k指向的节点所指向的节点
idx是指数组e使用到哪个位置了，idx是还未被使用，就跟队列的rear一样
这题义也不清呀，表示删除第 k 个插入的数后面的数的意思是后面的那一个数。。。给的示例还无法确认这一点
其实可以再好好读一读，这个应该没有问题
建议事先说下每个变量是用来做什么，纯靠猜很蒙
这个是yls上课就讲的变量命名，这个基本上就不用标注说明了（hhhh
好家伙，学过数据结构看你这个一脸懵，用数组模拟链表真的和原来学的有很大出入，理解不了（笑哭
比如ne[idx]，你可以理解为idx->next,同理 ne[ne[idx]]：ne->next>next，这样理解方便很多
说的不错hh