时间复杂度

插入和删除都是O(1)
查找第k个节点要遍历，因此是O(n)

C++ 代码

# include <iostream>
using namespace std;

const int N = 1e6 + 10;
int head = -1, e[N], ne[N], idx = 0;

void init() {
    head = -1;//此时链表为空，head指向空指针-1表示
    idx = 1;
}

void addNodeToHead(int value) {
    e[idx] = value;
    ne[idx] = head;
    head = idx;
    idx++;
}
//删除第 k 个插入的数后面的数
void remove(int k) {
    if (k == 0) { //删除头节点
        int temp = ne[head];
        ne[head] = -2;
        head = temp;
        return;
    }
    int temp = ne[ne[k]];//ne[k-1] = ne[ne[k-1]]
    ne[ne[k]] = -2;//-1是print终止标志
    ne[k] = temp;//ne[0] = ne[1]
}
//在第 k 个插入的数后面插入一个数 x
void addNodeToK(int value, int k) {
    e[idx] = value;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

void printList() {
    int index = head;
    while (index != -1) {
        printf("%d ", e[index]);
        index = ne[index];
    }
    printf("\n");
}

int main() {
    int M = 0;
    cin >> M;
    char op;
    int k = 0, x = 0;
    init();//初始化链表
    for (int i = 0; i < M; i++) {
        cin >> op;
        switch (op) {
        case 'H':
            cin >> x;
            addNodeToHead(x);
            break;
        case 'D':
            cin >> k;
            remove(k);
            break;
        case 'I':
            cin >> k;
            cin >> x;
            addNodeToK(x, k);
            break;
        default:
            break;
        }
        //cout << "the " << i << " op: ";
        //printList();
    }
    int index = 0;
    printList();
    return 0;
}