Түсіндіру

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

Қарапайым массивте элементтер бірінен кейін бірі тұрады. Ал связный списокта элементтер әр жерде тұра алады. Бірақ әр элемент келесі элемент қайда тұрғанын біледі.

Олимпиадалық программалауда связный списокты жиі массив арқылы жазады. Себебі бұл әдіс қарапайым және жылдам.

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

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

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

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

-1 дегеніміз — келесі элемент жоқ. Яғни список аяқталды.

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

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

Input

8
H 10
H 20
I 1 30
D 2
H 5
I 3 7
D 0
H 1

Output

1 20 30 7

Реализация

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

const int N = 100010;

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

void init() {
    head = -1;
    idx = 0;
}

void addHead(int x) {
    val[idx] = x;
    nxt[idx] = head;
    head = idx;
    idx++;
}

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

void delHead() {
    head = nxt[head];
}

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

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

    init();

    int m;
    cin >> m;

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

        if (op == 'H') {
            int x;
            cin >> x;

            addHead(x);
        } else if (op == 'I') {
            int k, x;
            cin >> k >> x;

            addAfter(k - 1, x);
        } else if (op == 'D') {
            int k;
            cin >> k;

            if (k == 0) {
                delHead();
            } else {
                delAfter(k - 1);
            }
        }
    }

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

    return 0;
}

Айнымалылар

• head — списоктың бірінші элементі
• val — элементтердің мәндері
• nxt — келесі элементтің индексі
• idx — жаңа элементке арналған бос индекс
• pos — әрекет жасайтын элементтің позициясы

Басына қосу

void addHead(int x) {
    val[idx] = x;
    nxt[idx] = head;
    head = idx;
    idx++;
}

Жаңа элементке x мәні беріледі. Кейін ол ескі бірінші элементке сілтейді. Соңында жаңа элемент бірінші элемент болады.

Элементтен кейін қосу

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

Жаңа элемент pos элементінен кейін қойылады. Алдымен жаңа элемент pos бұрын көрсетіп тұрған жерге сілтейді. Кейін pos жаңа элементке сілтейді.

Бірінші элементті өшіру

void delHead() {
    head = nxt[head];
}

Бірінші элементті өшіру үшін head келесі элементке ауысады.

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

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

Біз келесі элементті өткізіп кетеміз. Ол массивте қалады, бірақ списоктың ішінде енді болмайды.