C++

$\color{#cc33ff}{— > 算法基础课题解}$

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

单链表

$通过数组模拟链表的操作$

$\color{red}{图解：}$

$\color{red}{样例模拟结果：}$

$code1:$

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

//head 表示头节点的下标，
//e[i] 表示节点i的值， ne[i] 表示节点i的next指针(节点i的下一个节点的位置)
//idx存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 静态链表

// 链表的初始化
void init(){
    head = -1; // 初始时链表表示是空的，是空集
    idx = 0; // 表示我们当前可以从0号点开始用
}

// 将x插到头节点
void add_to_head(int x){
    e[idx] = x; // 存储x
    ne[idx] = head; //ne[idx]指向head指向的位置
    head = idx; // head 指向 idx
    idx ++; //idx 已经被用过了，走向下一个位置
}

// 将x插入到下标是k的节点的下面(后面)
void add(int k, int x){
    e[idx] = x; // 存数
    ne[idx] = ne[k]; // 建立一个idx,让其指向k的下一个位置
    ne[k] = idx; // k的下一个位置指向idx
    idx ++;
}

//将下标是k的点的后面删掉
void remove(int k){
    ne[k] = ne[ne[k]];

}
int main(){
    int m;
    cin >> m; //m个操作

    init();

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

        cin >> op; // 读入操作

        if(op == 'H'){
            cin >> x; // 读入要插入的数
            add_to_head(x);//调用函数
        }else if (op == 'D'){
            cin >> k; // 删除
            if (!k) head = ne[head];
            remove(k - 1);
        }else{
            cin >> k >> x;
            add(k - 1, x);
        }
    }

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

    return 0;
}

$code2:$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

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

void init() { // 初始化
    head = -1;
    idx = 0;
}

void add_to_head(int x) { // 将x插入到头节点
    e[idx] = x, ne[idx] = head, head = idx, idx ++;
}

void add(int k, int x) { // 将x插入到下标是k的节点的后面
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx ++;
}

void remove(int k) { // 将下标是k的点的后面删掉
    ne[k] = ne[ne[k]];
}

int main() {
    int m; cin >> m;

    init(); 

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

        cin >> op;
        if (op == 'H') {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D') {
            cin >> k;
            if (!k) head = ne[head]; // 当 k 为 0 时，表示删除头结点
            remove(k - 1); // 下标是从0开始的
        }
        else {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

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

    return 0;
}