模拟单链表和双链表

模拟单链表

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = N;
int h = -1, e[M], ne[M], idx = 1;
void add_h(int x)
{
    e[idx] = x, ne[idx] = h, h = idx++;
}
void d_k(int k)
{
    ne[k] = ne[ne[k]];
}
void add_k(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
int main()
{
    int m;
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        char op;
        cin >> op;
        
        if(op == 'H')
        {
            int x;
            cin >> x;
            add_h(x);
        }
        else if(op == 'I')
        {
            int k, x;
            cin >> k >> x;
            add_k(k,x);
        }
        else
        {
            int k;
            cin >> k;
            if(!k) h = ne[h];
            else d_k(k);
        }
    }
    
    for(int i = h; ~i; i = ne[i])
        cout << e[i] << ' ';
}

模拟双链表

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int e[N];
int l[N], r[N], idx = 2;
void init()
{
    r[0] = 1;
    l[1] = 0;
}
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    //l[r[idx]] = idx;
    idx++;
}
void dele(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
int main()
{
    int m;
    cin >> m;
    
    init(); int k, x;
    for(int i = 1; i <= m; i++)
    {
        string op;
        cin >> op;
        
        if(op == "L")
        {
            cin >> x;
            add(0, x);
        }
        else if(op == "R")
        {
            cin >> x;
            add(l[1], x);
        }
        else if(op == "D")
        {
            cin >> k;
            dele(k+1);
        }
        else if(op == "IL")
        {
            cin >> k >> x;
            add(l[k+1], x);
        }
        else
        {
            cin >> k >> x;
            add(k+1, x);
        }
    }
    
    for(int i = r[0]; i != 1; i = r[i])
        cout << e[i] << ' ';
}