Сравнение линейных структур

Сводная таблица структур

Соберём все линейные структуры в одну таблицу, чтобы выбирать осознанно. Сложность указана для худшего случая; «память» — накладные расходы сверх самих данных.

Пояснения к таблице:

• Массив выигрывает по доступу к элементу по номеру и по памяти (данные лежат непрерывно), но вставка и удаление в начало или середину требуют сдвига всех следующих элементов.
• Односвязный список даёт O(1) вставку/удаление в начало; вставка в конец — O(1), если хранить tail, а удаление хвоста всё равно требует предыдущего узла (O(N)). В середину — O(N), потому что до узла нужно дойти от головы.
• Двусвязный список даёт O(1) вставку/удаление в любом месте, если узел уже известен (есть prev). Поиск самого узла по значению всё равно O(N).
• Кольцевой список — тот же односвязный, но без NULL-терминатора: удобен, когда нужно «ходить по кругу» (сдвиг, задача Иосифа, циклический обход). Вставка в конец с tail — O(1); для удаления хвоста всё равно нужен предыдущий узел, поэтому без него это O(N).
• Стек, очередь, дек — это не отдельные структуры хранения, а ограниченные интерфейсы поверх списка или массива: стек — операции только с одного конца, очередь — в один конец и из другого, дек — с обоих концов.

Как выбирать структуру под задачу

Общее правило выбора:

1. Нужен доступ по номеру (a[i], бинарный поиск, сортировка «на месте») — массив.
2. Размер заранее неизвестен и данные часто меняются (вставки/удаления) — список.
3. Много вставок/удалений в начало — односвязный список с head.
4. Нужны операции с обоих концов — дек (двусвязный список) или кольцевой буфер.
5. Нужен циклический обход или «круг» — кольцевой список.
6. Нужно ходить в обе стороны от узла — двусвязный список.
7. Важен только порядок «последний пришёл — первый ушёл» — стек; «первый пришёл — первый ушёл» — очередь.

Выбор под варианты ЛР 3

В лабораторной №3 структура уже задана вариантом; вопрос в том, какие операции вам придётся реализовать и на что обратить внимание.

Основные варианты (1–20) — односвязный список Student. Здесь нужны: стабильная перестановка (разделение на группы без изменения порядка внутри группы), удаление по условию, слияние двух списков, сдвиг, разворот, работа с половинами.

• Стабильная перестановка (варианты 1–3, 5, 8, 14) — строите два (или три) списка-группы, цепляя узлы к их хвостам, затем сшиваете. Односвязный список с tail здесь идеален: вставка в конец группы за O(1).
• Удаление (варианты 4, 6, 7, 20) — нужен указатель на предыдущий узел, чтобы перецепить его next через удаляемый; удаляйте узел только после перецепки.
• Сдвиг на K (вариант 11) — на односвязном списке найдите узел K с конца (или N-K с начала), разорвите список и сшейте в новом порядке; не потеряйте head и новый хвост.
• Разворот и половины (варианты 9, 10, 12, 13, 15) — разворот за один проход с тремя указателями prev/cur/next; для половин найдите середину быстрым/медленным указателем.
• Слияние (варианты 17–19) — аккуратно сшивайте tail первого со вторым; при дедупликации сравнивайте id.

Повышенные варианты (П1–П5) — двусвязный список Student. Здесь добавляется работа с prev. Разворот (П1) — это обмен prev и next у каждого узла. Разделение по порогу (П4) и слияние (П5) требуют обновлять оба направления при каждой перецепке, иначе обратные связи порвутся.

Высокие варианты (В1–В5) — кольцевой список Value. Всё вертится вокруг инварианта tail->next == head. Сдвиг (В1) — перенос головы; обмен половин (В2) — разрезание кольца и слияние частей в обратном порядке; разделение по типу (В3) — разрезание на два кольца; слияние (В4) — соединение хвостов; разворот (В5) — изменение направления с замыканием. Подробно см. статью «Циклический список».

Чек-лист отладки указателей

Работа со списками ломается почти всегда из-за указателей. Вот порядок действий при отладке.

1. Нарисуйте схему на бумаге. Узлы — квадратики, ссылки — стрелки. Перед каждой перецепкой рисуйте «до» и «после»: это ловит потерю узла до того, как вы её закодируете.
2. Проверяйте инварианты. Для очереди/дека — head == NULL <=> tail == NULL; для дека — ещё head->prev == NULL, tail->next == NULL и взаимные prev/next; для кольца — tail->next == head. После каждой операции структура обязана снова удовлетворять инварианту.
3. Отдельно проверьте N = 0, 1, 2. Пустой список (ничего не делаем), один узел (head == tail, next == NULL или next == head), два узла (соседние ссылки). Больше всего ошибок — именно на единице и двойке.
4. Проверьте границы K и T. K = 0, K = N, K = 1, а также T, при котором порог совпадает с реальным значением (запись ровно с T — где она должна остаться?).
5. Проверьте дубликаты id и пустые блоки. Слияние с совпадающими id, разделение, где одна из групп пуста, — типичные места «съедания» узлов.
6. Компилируйте строго и гоняйте под санитайзерами:

gcc -std=c23 -Wall -Wextra -Werror -fsanitize=address,undefined main.c -o main

AddressSanitizer ловит чтение после free и утечки, UndefinedBehaviorSanitizer — разыменование NULL и чтение не того члена union. Под Linux также работает valgrind:

valgrind --leak-check=full ./main

1. После free не трогайте узел. Сначала сохраните все нужные указатели (next, prev), потом освобождайте.

План тестирования

Прогоните программу на этих случаях, сверяя output.txt с ожидаемым:

Проверяйте не только сам вывод, но и отсутствие утечек: запустите под ASan/valgrind и убедитесь, что все узлы освобождены.

Что запомнить

1. Массив — быстрый доступ по номеру, дорогая вставка/удаление; список — наоборот.
2. Односвязный список дешевле по памяти, но ходит только вперёд; двусвязный — в обе стороны ценой указателя prev.
3. Кольцевой список — односвязный без NULL-терминатора, удобен для «круговых» задач.
4. Стек, очередь и дек — ограниченные интерфейсы поверх списка или массива.
5. Храните tail, если нужна O(1) вставка в конец.
6. Перед перецепкой рисуйте схему; проверяйте инварианты и случаи N = 0/1/2.
7. free — только после перецепки и сохранения нужных указателей.
8. Гоняйте код под -fsanitize=address,undefined и valgrind.