Закрепление материала: Линейные списки

Модуль "Линейные списки" • урок 8 из 9 • ~8 минут

Суть урока. В этом модуле мы разобрали устройство линейных списков - структур, допускающих произвольную вставку и удаление. Мы посмотрели на них с разных сторон: от абстрактной логики головы и хвоста до суровых реализаций на указателях и индексных векторах в C. Пришло время собрать все концепции воедино и проверить свои знания перед переходом к графам и деревьям.

Индексный вектор и динамические узлы: массив дает сплошную память ценой ручного учета дырок, а куча дает вставку за O(1) ценой вызовов malloc и free — Что выбрать: сплошная память с учетом дырок или узлы по одному из кучи

Краткое резюме модуля

За прошедшие уроки мы изучили несколько ключевых подходов к хранению и обработке списков:

Логический список - рекурсивная структура из функционального программирования. Состоит из первого элемента (головы) и остатка списка (хвоста).
Индексный вектор - суррогатная реализация списка на массиве. Использует индексы вместо указателей, спасает от сдвигов элементов, но требует ручного управления дырками (список свободных ячеек).
Динамический список - классическая реализация в куче. Узлы выделяются по одному и связываются указателями. Вставка - это просто переброска связей за O(1).
Ортосписок - список общего вида, переплетенный по строкам и столбцам. Идеален для хранения разреженных матриц без траты памяти на нули.

Ключевые идеи

Итератор: безопасная обертка над указателем в C. Защищает программиста от случайной адресной арифметики и дает универсальный интерфейс обхода.
Разделение на голову и хвост: базовый принцип рекурсивной обработки в языках вроде Lisp и Prolog. Хвост - это всегда список, даже если он пустой.
Универсальность памяти: использование объединений (union) в C позволяет создавать списки общего вида, где один узел может хранить либо простое число, либо указатель на вложенный список, экономя память.

Коротко: главное

Списки решают проблему дорогой вставки в середину коллекции.
Поиск элемента в списке всегда занимает время O(N), так как прямого доступа по индексу нет.
Сама операция вставки или удаления (при известной позиции) выполняется за O(1).
Индексные векторы заменяют физические указатели на целые числа.
Разреженные матрицы выгодно хранить в виде триплетов, собирая их в ортосписки.

Проверьте себя

Вопрос 1

В чем заключается главная цель использования итераторов при работе со списками на языке C?

Ускорить поиск элемента до O(1) Автоматически очищать память при удалении узла Изолировать сырые указатели в структуре, предотвратив опасную адресную арифметику

Вопрос 2

Если логически отделить голову от хвоста в списке [15, 42], чем будет являться хвост?

Числом 42 Списком [42] Списком []

Вопрос 3

Что происходит с остальными данными в массиве при удалении элемента из индексного вектора?

Они остаются на своих местах, а массив получает логическую "дырку" Они сдвигаются на одну позицию влево Они копируются в новый, уменьшенный массив

Как вам урок? Спасибо за отзыв!