题目描述

用数组模拟单链表结构，支持三种功能，在下标为0的位置插入一个节点，删除下标为k的节点，在下表为k -1的后面插入一个节点

背模板时需要理清的思路

对链表结构的一些解释：
我更愿意把链表画成这种形式.

数组链表的操作法则基本有三个
①第一步是初始化数组状的链表头和链表头的指针。这个初始化完成后应该是一个箭头指向空

②第二步是把三种操作用函数来表示，并分别调用函数。插入操作的思路是先解新绳，再解旧绳。

代码写法上的特点

①链表头的初始化用一个函数init()来写会比较整洁一点。idx的意思是当前节点的下标。head的意思是头节点的指向。
②add、add_to_head中的第一步e[idx] = x就是将x作为当前节点，这个节点现在还是在外部的，而不能想象为在原链表中这个idx在哪个位置。
add、add_to_head中的最后一步idx ++的原因是每次插入节点先用一个idx下标的节点做虚拟节点，将idx ++相当于是一个更新初始化的操作，不然这个虚拟节点不更新的化就会对已有的节点赋值，会出现问题。静态看链表的idx是比当前链表的节点数多1的。
③指向的指向用数组来表示是ne[ne[i]]，因为ne的[]中写的是指向。
④链表用数组表示就是可以把idx视为下标，e[N]就是上标，ne[N]就是下标，e[N]就是存输入的值的，ne[N]是一个0，1，2，3，4…-1的下标数组。
⑤remove操作仅改变下标指向就好了，遍历的时候跳过需要删除的值就能实现

参考文献

参考y总的代码

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;
int M;
int head, idx, e[N], ne[N];

void init()
{
    head = -1;
    idx = 0;
}

void add_to_head(int x) 
{
    e[idx] = x, ne[idx] = head, head = idx ++;
}

void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++;

}

void remove(int k) 
{
    ne[k] = ne[ne[k]];

}


int main()
{
    cin >> M;
    char input;

    init();


    while (M -- ) 
    {
        cin >> input;
        if (input == 'H') 
        {
            int x;
            cin >> x;

            add_to_head(x);

        }
        else if (input == 'D')
        {
            int k;

            cin >> k;
            if (!k) head = ne[head];
            remove(k - 1);

        }
        else 
        {
            int k, x;
            cin >> k >> x;
            add(k - 1, x);

        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';

    return 0;

}