题目描述

双链表(三个函数)

C++ 代码

#include <iostream>
using namespace std;

const int N = 100010;

int e[N], r[N], l[N], idx;

void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// k 右侧插入节点
void add(int k, int x)
{
    //k = 0
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
int main()
{
    init();
    int m;
    cin >> m;
    while (m --)
    {
        string op;
        int k , x;
        cin >> op;
        if (op == "L")
        {
            k = 0;
            cin >> x;
            add(k, x);
        }
        else if (op == "R")
        {
            k = 1;
            cin >> x;
            add(l[k], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k+1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            add(l[k+1], x);
        }
        else if (op == "IR")
        {
            cin >> k >> x;
            add(k+1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";

}