Doubly Linked List

Түсіндіру

Doubly Linked List — бұл двусвязный список. Мұнда әр элемент тек келесі элементті ғана емес, алдыңғы элементті де біледі.

басы ⇄ 10 ⇄ 20 ⇄ 30 ⇄ соңы

Singly Linked List-та әр элемент тек алға қарай жүреді. Ал Doubly Linked List-та екі бағыт бар:

pre[i] — алдыңғы элементтің индексі
nxt[i] — келесі элементтің индексі

Сондықтан біз элементтің сол жағына да, оң жағына да тез қоса аламыз. Белгілі элементті өшіру де оңай болады.

Кейде оны “двумерный список” деп айтуы мүмкін. Бірақ алгоритмде дұрыс атауы — Doubly Linked List немесе двусвязный список.

Массивте не сақтаймыз?

val[i] — i индексіндегі элементтің мәні
pre[i] — i элементінің алдындағы элемент
nxt[i] — i элементінен кейінгі элемент
idx — жаңа элемент салатын бос индекс

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

Код оңай болу үшін біз екі арнайы элемент қолданамыз:

0 — сол жақ шекара
1 — оң жақ шекара

0 ⇄ список элементтері ⇄ 1

Нағыз элементтер 2 индексінен басталады.

Егер список бос болса, онда 0-ден кейін бірден 1 тұрады. Яғни nxt[0] = 1 және pre[1] = 0.

Сақталу мысалы

Бізде мынадай список бар:

10 ⇄ 20 ⇄ 30

Массив арқылы ол былай сақталуы мүмкін:

i	val[i]	pre[i]	nxt[i]
0	-	-	2
2	10	0	3
3	20	2	4
4	30	3	1
1	-	4	-

Реализацияға арналған есеп мысалы

Басында список бос. Бірнеше команда беріледі. Сол командаларды орындау керек.

Команда	Не істейді
L x	x санын списоктың басына қосады
R x	x санын списоктың соңына қосады
D k	k-шы қосылған элементті өшіреді
IL k x	k-шы қосылған элементтің сол жағына x қояды
IR k x	k-шы қосылған элементтің оң жағына x қояды

Input

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

Output

5 10 17 20 30

Бірінші нағыз элементтің индексі 2 болады. Сондықтан k-шы қосылған элемент массивте k + 1 индексінде тұрады.

Реализация

#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 пен ескі келесі элементтің ортасына кіреді.

бұрын: pos ⇄ oldNext
кейін: pos ⇄ new ⇄ oldNext

Сол жағына қосу

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

pos элементінің сол жағына қосу үшін, жаңа элементті pos-тың алдындағы элементтен кейін қоямыз.

бұрын: oldPrev ⇄ pos
кейін: oldPrev ⇄ new ⇄ pos

Элементті өшіру

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

Элементті өшіру үшін оның алдындағы элементті оның келесі элементімен қосамыз. Өшірілген элемент массивте қалады, бірақ списоктың ішінде болмайды.

бұрын: left ⇄ pos ⇄ right
кейін: left ⇄ right