单链表

本质上：静态链表（数组模拟链表）

写法1

• 感谢@yxc
• 仿y总的单链表C++模板，换成c语言写
• 注意：scanf("%c") 会把空格和回车读入，所以每次注意格式都要\n
• remove函数会重名，改方法名为m_remove

C语言 代码

#include<stdio.h>
#include<stdlib.h>
#define N 100010

int e[N], ne[N], head, idx;

void init(){
    head = -1; // -1表示null
    idx = 0;   // 从[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 m_remove(int k) { ne[k] = ne[ne[k]]; }

int main()
{
    int n;
    scanf("%d\n", &n);     // 一定要写"%d\n"，否则会影响到scanf("%c")
    init();                // 初始化静态链表

    while(n --)
    {
        int x, k;
        char op;

        scanf("%c", &op);
        switch(op)
        {
            case 'H': 
                scanf("%d\n", &x); 
                add_to_head(x); 
                break;

            case 'I': 
                scanf("%d%d\n", &k, &x); 
                add(k - 1, x); 
                break;

            case 'D': 
                scanf("%d\n", &k); 
                if(!k) head = ne[head];
                else m_remove(k - 1); 
                break;

            default: break;
        }
    }

    for(int i = head; i != -1; i = ne[i]) 
        printf("%d ", e[i]);

    return 0;
}

写法2

• 感谢@yxc
• 仿y总的双链表C++模板的思想
• 偷懒行为，浪费[0]位置作为head（注：这个head无实际的值）. idx 从1开始

C++ 代码

#include<iostream>

using namespace std;
const int N = 1e5 + 10;

int ne[N], e[N], idx;

// 初始化.默认以[0]为head指针（无实际值）. 从[1] 开始存第1个结点 
void init() {
    ne[0] = -1, idx = 1;
}

// 在第[k]个位的右边,插入新元素
void add(int k, int x) {
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++;
}

// 删除第[k]位的右边的元素
void remove(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    int m;
    scanf("%d", &m);
    init();             // 一般情况下,init()的方法体可以直接写在main函数里

    while(m --){ 
        string op;
        cin >> op;

        int k, x;       // 在第k个位置,k对应的下标从1,2,3,....,n ; 由于[0]已被head使用,所以不需要k-1
        if(op == "H"){
            cin >> x;
            add(0, x);  // [0]的右边即实际第1个结点
        }

        else if(op == "I"){
            cin >> k >> x;
            add(k, x);  
        }

        else {
            cin >> k;
            remove(k);  
        }
    }

    for(int i = ne[0]; i != -1; i = ne[i]) // ne[0] 是第1个实际有值的结点
        printf("%d ", e[i]);

    return 0;
}