单链表

基本操作:(对k结点)

1. 这里删除节点不是真删除而是让k节点的指向下一个节点的下一个节点
2. 在k的右侧增加节点:增加节点要先把新节点i指向k节点的下一个节点,再把k节点指向i节点,反过来就找不到k节点
3. 用数组模拟开两个数组,e和ne,记一个序号idx(代表已经真实使用的点数,删除点不改idx),该序号用来区分不同的点
   1. e[i]代表第i个节点的值,i为序号,是我们认为规定的
   2. ne[i]代表第i个节点的下一个节点的序号
4. 本例中头节点用head变量表示,head的值是头节点的序号,对应的e[head]就是头节点的值,这里head仅仅是记录头节点在哪的变量,所以head不是一个空结点,向头部插入不是向头的右侧插入而是直接改头,没有使用时head=-1,头插一个点时e[head]就存在了,e[head]存值

代码:

/*
实现一个单链表，链表初始为空，支持三种操作：向链表头插入一个数；删除第 k 个插入的数后面的数；在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。
D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
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
*/
#include <iostream>
using namespace std;
const int N = 1e6+10;
int head,idx,e[N],ne[N];//e[i]是序号为i点值,ne[i]表示i的下一个点的序号,一定区分清楚
//idx !序号,从0开始
void init()
{
    head = -1;//-1相当于序号,序号为-1的点就是头
    idx = 0;//idx从0开始
}
//把点插入头节点
void add_to_head(int x){
    e[idx] = x;//第idx个点的值为x
    ne[idx] = head;//向头部插入不是向头的右侧插入而是直接改头
    head = idx ++;//跟新头节点序号为idx,idx++表示这步用了一个点,++
}
//在k(序号)后面一个插入
void add(int k,int x){
    e[idx] = x;//新点(idx)赋值
    ne[idx] = ne[k];//序号为idx的下一个点为序号为k的下一个点
    ne[k] = idx++;//k的下一个点序号为idx
}
//删除k(序号)数
void remove (int k){
    ne[k] = ne[ne[k]];//k的下一个点的序号变为k的下一个的下一个点的序号,删除了k的下一个点
}
int main()
{
    init();
    int n;scanf("%d",&n);
    char a;
    int o1,o2;
    while(n--){

        //!scanf("%c",&a); 这样过不了题,这里在下一次会读入空格! 用cin保险
        //或者用op[2] scanf("%s",op);
        cin>>a;
        if(a == 'H'){
            scanf("%d",&o1);
            add_to_head(o1);
        }else if (a == 'D'){
            scanf("%d",&o1);
            if(!o1){//特判 o1为0删除头结点
                head = ne[head];//删除头节点是删除头结点本身,所以直接等于ne[head]
            }else {
                remove (o1-1);//删除第o1个点,o1从1开始,我们idx从0开始,所以o1-1 下面同
            }
        }else{
            scanf("%d %d",&o1,&o2);
            add(o1-1,o2);
        }
    }
    for(int i = head;i != -1;i = ne[i]){
        printf("%d ",e[i]);
    }
    return 0;
}