Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

type Node struct {
    val, id int
    next *Node
}

func NewNode(val, id int) *Node {
    return &Node{val: val, id: id, next: nil}
}

type List struct {
    head *Node
    id int
    ids map[int]*Node
}

func NewList() *List {
    list :=  &List{
        head: NewNode(0, 0),
        id: 0,
        ids: make(map[int]*Node),
    }
    list.ids[list.head.id] = list.head
    list.id++
    return list
}

func (l *List) HeadInsert(x int) {
    s := NewNode(x, l.id)
    s.next = l.head.next
    l.head.next = s
    l.ids[s.id] = s
    l.id++
}

func (l *List) DeleteKthInserted(k int) {
    p := l.ids[k]
    if p.next != nil {
        delete(l.ids, p.next.id)
        p.next = p.next.next
    }
}

func (l *List) KthInsert(k, x int) {
    p, s := l.ids[k], NewNode(x, l.id)

    s.next = p.next
    p.next = s
    l.ids[s.id] = s

    l.id++
}

func (l List) Display() {
    p := l.head.next
    for p != nil {
        fmt.Printf("%d ", p.val)
        p = p.next
    }
    fmt.Println()
}

func main() {
    in := bufio.NewReader(os.Stdin)
    var m int
    fmt.Fscan(in, &m)

    list := NewList()
    var k, x int
    for i := 0; i < m; i++ {
        var op string
        fmt.Fscan(in, &op)
        switch op {
        case "H":
            fmt.Fscan(in, &x)
            list.HeadInsert(x)
        case "D":
            fmt.Fscan(in, &k)
            list.DeleteKthInserted(k)
        case "I":
            fmt.Fscan(in, &k, &x)
            list.KthInsert(k, x)
        }
    }
    list.Display()
}

C++

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

class List {
public:
    List() : head_(new ListNode(0, 0)), ids_(unordered_map<int, ListNode*>()), id_(0) {
        ids_[head_->id_] = head_;
        id_++;
    }

    ~List() {
        while (head_) {
            ListNode* next = head_->next_;
            delete head_;
            head_ = next;
        }
    }

    void HeadInsert(int x) {
        auto s = new ListNode(x, id_);

        s->next_ = head_->next_;
        head_->next_ = s;
        ids_[s->id_] = s;

        id_++;
    }

    void DeleteKthInserted(int k) {
        ListNode* p = ids_[k];
        if (p->next_) {
            ids_.erase(p->next_->id_);
            ListNode* tmp = p->next_;
            p->next_ = tmp->next_;
            delete tmp;
        }
    }

    void KthInsert(int k, int x) {
        ListNode* p = ids_[k];
        auto s = new ListNode(x, id_);

        s->next_ = p->next_;
        p->next_ = s;
        ids_[s->id_] = s;

        id_++;
    }

    void Display() const {
        ListNode* p = head_->next_;
        while (p) {
            cout << p->val_ << " ";
            p = p->next_;
        }
        cout << endl;
    }

private:
    struct ListNode {
        int val_;
        int id_;
        ListNode* next_;

        ListNode(int val, int id): val_(val), id_(id), next_(nullptr) {}
    };

    ListNode* head_;
    unordered_map<int, ListNode*> ids_;
    int id_;
};

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

    auto list = new List();
    int x, k;
    while (M--) {
        char op;
        cin >> op;
        if (op == 'H') {
            cin >> x;
            list->HeadInsert(x);
        } else if (op == 'D') {
            cin >> k;
            list->DeleteKthInserted(k);
        } else {
            cin >> k >> x;
            list->KthInsert(k, x);
        }
    }
    list->Display();

    delete list;
    return 0;
}