$\Huge\color{orchid}{点击此处获取更多干货}$

事先说一句，数据结构部分，如果数据结构本身对元素的类型无限制，之后的代码中一直都会使用泛型编程

单向链表原理

这是考研数据结构最开始就讲到的线性表中的一种，支持随机存取的顺序表不用多说了，就是平时经常使用的原生数组，std::vector以及较少提及的std::array，另外一种则是之后介绍的链表，又分为单向和双向两种。链表中是由若干离散的节点构成，每个节点包含自身信息以及后继、前驱节点的地址信息，下图就是一条单向链表可能的构成：

可见链表的每个节点在内存中的地址空间可能不是连续的，因此才需要指向后继或者前驱的地址信息，这个可以表示为指针也可以表示为索引，在单向链表中先用指针，随后双向链表中改为索引

如上图所示，此单向链表的元素按顺序依次为$\{1,3,6,5,9,7,4\}$。如果想要在头节点$head$后插入元素8，那么需要在内存中寻找一块大小合适的内存空间，先构造一个$val = 8$的节点，然后将其后继指针$next$指向头结点后继$head->next$，最后将$head->next$指向该节点，就完成了插入，如下图所示：

接下来，删除9，然后在1和3之间插入一个新的9，这时情况就变得复杂起来了，由于单向链表的存取点只有头结点$head$，必须要从$head$开始向后寻找到9的前一个节点$p$（9这个节点为$q$），然后$p->next = q->next; q->next = nullptr; delete~q;$就算完成删除

插入回这个9的时候，由于之前的$q$指针执行过了delete，新插入的9有可能和原来的9不在一个地址，插入操作还是跟之前类似

可见随着长度的增加，离头结点越远的节点，存取起来耗时越久，如果想要按照需求描述的那样，任意按插入位序增删节点，只用一条链式结构的表显然是不够的，于是我们另外用一张哈希表，按照插入位序存放链表中仍然存在的节点（已析构的节点保留其插入位序），就可以在较短时间内按插入位序任意取得节点了

C++代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

//Elem属于模板参数
template<class Elem>
struct SLNode {
    Elem val = Elem();
    SLNode<Elem>* next = nullptr;
    SLNode() {}
    SLNode(Elem e) : val(e) {}
    SLNode(Elem e, SLNode<Elem>* nxt) : val(e), next(nxt) {}
};

template<class Elem> 
class SingleLinkedList {
private:
    //哈希表的键值对分别代表插入位序和节点本身
    unordered_map<size_t, SLNode<Elem>*> existNodes;
    SLNode<Elem>* head, * del;
    size_t tot = 1ull;//表示当前插入的节点位序（一定非负）
public:
    SingleLinkedList() {
        existNodes[0] = new SLNode<Elem>();
        //假设头结点已经有了
        head = existNodes[0];
        del = nullptr;
    }

    ~SingleLinkedList() {
        while (head != nullptr) {
            del = head;
            head = head->next;
            delete del;
            del = nullptr;
        }
    }

    //向头结点插入，实际上就是在假设的头结点后面插入一个元素
    void insertAfterHead(Elem e) {
        SLNode<Elem>* cur = new SLNode<Elem>(e, head->next);
        existNodes[tot++] = cur;
        head->next = cur;
    }

    //在插入位序k的元素后插入
    void insertAfterKthNode(Elem e, size_t k) {
        SLNode<Elem>* cur = new SLNode<Elem>(e), * pre = existNodes[k];
        existNodes[tot++] = cur;
        cur->next = pre->next;
        pre->next = cur;
    }

    //移除插入位序k的元素的后继
    void eraseNodeAfterKth(size_t k) {
        //k=0不会造成任何影响
        SLNode<Elem>* cur = existNodes[k];
        del = cur->next;
        cur->next = del->next;
        del->next = nullptr;
        delete del;
        //可能多次使用del指针，delete后要置空
        del = nullptr;
    }

    //遍历并按顺序输出链表全部元素
    void traverse() {
        SLNode<Elem>* cur = head->next;
        while (cur != nullptr) {
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
};

int main() {
    //用实际存在的类型int替换模板参数Elem
    SingleLinkedList<int> list;
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    size_t k;
    char op;
    cin >> n;
    while (n--) {
        cin >> op;
        switch (op) {
        case 'H':
        {
            cin >> x;
            list.insertAfterHead(x);
            break;
        }
        case 'I':
        {
            cin >> k >> x;
            list.insertAfterKthNode(x, k);
            break;
        }
        case 'D':
        {
            cin >> k;//已包含删除头节点的情况
            list.eraseNodeAfterKth(k);
            break;
        }
        }
    }
    list.traverse();
    return 0;
}