单链表

单链表：只有数值跟后指针的数据结构

题目地址：

https://www.acwing.com/problem/content/828/

变量表示：

head ： 头指针，始终只想链表的头节点

e[N] ： 数值数组，存放每个节点数值，下标表示存储地址，存放的值为节点的值

ne[N] ： 指针数组，存放每个节点的指针，下标表示当前节点的存储地址，存放的值是下个节点的地址

idx ： 地址，分配的地址，就是各个数组的下标，相当于内存中的0x3fde..之类的。

这边的数组相当于为这个链表分配的存储空间，而idx相当于为每个节点分配具体的地址

操作分析：

插入头结点跟插入中间节点的操作基本一致，需要注意的点就是，要先连接新节点的next指针，再断掉全原本前一个节点的指针，不然会丢失后面的节点

插入到头结点：

删除：

注意

这边函数参数中的k并不是指链表中的第几个节点，而是指我们为其开辟的静态数组中的下标，为其分配的地址，是指第几个插入，而不是具体指第几个节点。

代码如下

#include <iostream> using namespace std; const int N = 100010; int head,e[N],ne[N],idx; //初始化 void init() { head = -1;//head要定义为-1之后尾节点才会都指向-1 idx = 0; } //向链表头插入一个数x void add_to_head(int x) { e[idx] = x; ne[idx] = head; head = idx++; } //删除第k个输入的数后面的数 void de(int k) { ne[k] = ne[ne[k]]; } //在第k个输入的数后面插入一个数x void add(int k,int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } int main() { int n; cin>>n; //不要忘记初始化 init(); while(n--) { int k,x; char op; cin>>op; if(op == 'H') { scanf("%d",&x); add_to_head(x); } else if(op == 'D') { scanf("%d",&k); //删除头结点 if(!k)head = ne[head]; //第k个，因为从0开始数，所以要减一 else de(k-1); } else { scanf("%d%d",&k,&x); //第k个，因为从0开始数，所以要减一 add(k-1,x); } } //链表的遍历 for(int i = head; i != -1; i = ne[i])cout<<e[i]<<' '; cout<<endl; return 0; } } } //链表的遍历 for(int i = head; i != -1; i = ne[i])cout<<e[i]<<' '; cout<<endl; return 0; }