Объяснение

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

В обычном массиве элементы стоят подряд. В связном списке элементы могут лежать в разных местах, но каждый элемент знает, куда идти дальше.

В олимпиадном программировании связный список часто реализуют через массивы. Это быстрее и проще, чем работать с указателями.

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

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

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

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

Значение -1 означает, что следующего элемента нет. То есть список закончился.

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

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

Вход

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

Выход

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];
}

Первый элемент удаляется так: голова списка просто переходит на следующий элемент.

Удаление после элемента

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

Мы перепрыгиваем через следующий элемент. Он остается в массиве, но больше не находится в списке.