Объяснение

Двусвязный список — это список, где каждый элемент знает не только следующий элемент, но и предыдущий.

В односвязном списке у элемента есть только ссылка вперед. В двусвязном списке у элемента есть две связи:

• pre[i] — предыдущий элемент
• nxt[i] — следующий элемент

Благодаря этому можно быстро вставлять элемент слева или справа от известного элемента. Также можно быстро удалять известный элемент.

Что храним в массивах?

• val[i] — значение элемента с индексом i
• pre[i] — индекс предыдущего элемента
• nxt[i] — индекс следующего элемента
• idx — индекс свободной ячейки для нового элемента

Фиктивные вершины

Чтобы код был проще, мы создаем две специальные вершины:

• 0 — левая граница списка
• 1 — правая граница списка

Настоящие элементы начинаются с индекса 2.

Пример хранения

Пусть список такой:

В массивах это может выглядеть так:

Пример задачи для реализации

Дан пустой двусвязный список. Нужно обработать несколько команд.

Вход

7
L 10
R 20
IR 1 15
IL 2 17
D 3
L 5
R 30

Выход

5 10 17 20 30

Реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int val[N];
int pre[N];
int nxt[N];
int idx;

void init() {
    nxt[0] = 1;
    pre[1] = 0;
    idx = 2;
}

void addAfter(int pos, int x) {
    val[idx] = x;

    pre[idx] = pos;
    nxt[idx] = nxt[pos];

    pre[nxt[pos]] = idx;
    nxt[pos] = idx;

    idx++;
}

void addBefore(int pos, int x) {
    addAfter(pre[pos], x);
}

void delAt(int pos) {
    nxt[pre[pos]] = nxt[pos];
    pre[nxt[pos]] = pre[pos];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int m;
    cin >> m;

    while (m--) {
        string op;
        cin >> op;

        if (op == "L") {
            int x;
            cin >> x;

            addAfter(0, x);
        } else if (op == "R") {
            int x;
            cin >> x;

            addBefore(1, x);
        } else if (op == "D") {
            int k;
            cin >> k;

            delAt(k + 1);
        } else if (op == "IL") {
            int k, x;
            cin >> k >> x;

            addBefore(k + 1, x);
        } else if (op == "IR") {
            int k, x;
            cin >> k >> x;

            addAfter(k + 1, x);
        }
    }

    for (int i = nxt[0]; i != 1; i = nxt[i]) {
        cout << val[i] << ' ';
    }

    return 0;
}

Объяснение переменных

• val — значения элементов
• pre — предыдущий элемент
• nxt — следующий элемент
• idx — свободная ячейка для нового элемента
• pos — позиция элемента

Инициализация

void init() {
    nxt[0] = 1;
    pre[1] = 0;
    idx = 2;
}

В начале список пустой. После левой границы 0 сразу идет правая граница 1. Новые элементы начинаются с индекса 2.

Вставка справа от элемента

void addAfter(int pos, int x) {
    val[idx] = x;

    pre[idx] = pos;
    nxt[idx] = nxt[pos];

    pre[nxt[pos]] = idx;
    nxt[pos] = idx;

    idx++;
}

Новый элемент вставляется после элемента pos. Он становится между pos и старым следующим элементом.

Вставка слева от элемента

void addBefore(int pos, int x) {
    addAfter(pre[pos], x);
}

Чтобы вставить слева от pos, можно вставить новый элемент справа от предыдущего элемента.

Удаление элемента

void delAt(int pos) {
    nxt[pre[pos]] = nxt[pos];
    pre[nxt[pos]] = pre[pos];
}

Чтобы удалить элемент, нужно соединить его предыдущий элемент со следующим элементом.