Список

Список — это структурированная совокупность данных, в которой каждый элемент идентифицируется своим положением (индексом) или значением. В широком смысле список представляет собой упорядоченный или неупорядоченный перечень объектов, сведений, действий или признаков, объединённых общим критерием. В информатике и математике список — фундаментальная абстракция, используемая для хранения и обработки последовательностей данных, обеспечивающая доступ к элементам по порядковому номеру или по ключу. Списки противопоставляются массивам, множествам и ассоциативным контейнерам, однако в разных языках программирования и системах управления базами данных границы между этими понятиями размыты.

История и происхождение понятия

Понятие списка как упорядоченного перечня восходит к античным каталогам, инвентарям и переписным листам — например, к спискам римских консулов или к индексам трудов Аристотеля. В математике ещё в XIX веке использовались «списки» как синоним перечня (sequence), но систематическое изучение формальных свойств началось с работ по алгебре и комбинаторике. В computer science термин «список» вошёл в обиход в 1950-х годах благодаря развитию языков программирования: в Lisp (1958) список стал основной структурой данных, на которой строится весь язык. Джон Маккарти и его коллеги в MIT использовали двухзвенные узлы с указателями на следующий элемент, что заложило основы для функционального и процедурного использования списков. С тех пор понятие списка распространилось на все отрасли программирования, теории баз данных (списки значений, списки полей) и на повседневный документооборот (списки рассылки, списки задач).

Классификация списков

По способу хранения и доступа

• Линейные (односвязные) списки — каждый элемент содержит ссылку (указатель) на следующий. Доступ к произвольному элементу осуществляется последовательным обходом, что делает добавление и удаление элементов на концах быстрым (O(1) для головы). Основной недостаток — сложность поиска и произвольного доступа (O(n)).
• Двусвязные списки — каждый элемент хранит ссылку на предыдущий и следующий. Это позволяет проходить список в обоих направлениях и удалять элемент без знания его предшественника (при наличии ссылки на сам элемент). Используются, например, в реализации LRU-кэшей.
• Циклические списки — последний элемент указывает на первый, а не на NULL. Применяются в задачах с циклическими очередями (например, Round-Robin алгоритмы).
• Разреженные списки — хранят только ненулевые или существенные элементы с их индексами для экономии памяти.

По правилам доступа и упорядоченности

• Неупорядоченные списки — порядок элементов не отражает их значения, возможна произвольная компоновка (например, список покупок).
• Упорядоченные списки — элементы отсортированы по некоторому критерию (значение, дата, алфавит). В информатике для таких списков часто применяются деревья или хэш-таблицы для ускорения поиска.
• Очередь (FIFO) — добавление только в конец, извлечение из начала. Реализуется как односвязный список с двумя указателями.
• Стек (LIFO) — добавление и извлечение с одного конца (вершины). В языках программирования часто реализуется через список или массив.

По структуре узла

• Простые списки — каждый узел содержит одно значение и одну ссылку.
• Списки с данными произвольной длины — узлы могут содержать строки, структуры или другие списки.
• «Ленивые» списки (списки с отложенным вычислением) — элементы не вычисляются, пока не потребуются (реализуются в Haskell и некоторых библиотеках Python).

Устройство и основные операции

Односвязный список (в виде кода на C-подобном языке)

Типичная структура узла: ``c struct Node { int data; struct Node* next; }; `` Основные операции:

• Вставка в начало — создать новый узел, присвоить его next на текущую голову, обновить голову. Сложность O(1).
• Вставка в конец — пройти до последнего элемента и добавить новый узел (без указателя на хвост — O(n); с указателем на хвост — O(1)).
• Удаление по значению — найти элемент, перенаправить next предыдущего на последующий. Сложность O(n) из-за поиска.
• Поиск элемента — последовательный обход до совпадения или конца списка. Сложность O(n).
• Обход (итерация) — от головы до NULL, выполняя действие над каждым элементом.

В языках программирования высокого уровня (Python, Java, C#) списки встроены как динамические массивы (списки с произвольным доступом, фактически — массивы), а не как связные списки. Однако классы LinkedList (Java), list из STL (C++), collections.deque (Python) предоставляют двусвязные или односвязные реализации.

Применение списков

В программировании

• Реализация очередей и стеков — стандартные структуры для планирования задач, обработки вызовов, буферизации.
• Управление памятью — списки свободных блоков (free list) в куче, кэши (LRU, LFU).
• Графы и деревья — списки смежности (adjacency list) для хранения рёбер графа.
• Лексический анализ и компиляция — токены в виде списка лексем, последовательность AST-узлов.
• Обработка событий — список зарегистрированных обработчиков (callback-функций) в GUI-фреймворках.

В повседневной и деловой сфере

• Список задач (to-do list) — управление временем.
• Список литературы — библиографические перечни, ссылки, архивные реестры.
• Списки рассылки и подписок — групповые почтовые переписки.
• Инвентаризационные списки — складской учёт, описи имущества.

В документообороте и законодательстве

• Список документов — перечень регистрируемых бумаг в делопроизводстве.
• Избирательный список — официальный перечень кандидатов или избирательных участков.
• Таможенный список — перечень товаров, подлежащих декларированию.

Преимущества и ограничения

Достоинства

• Динамическое управление памятью — не нужно заранее выделять фиксированный блок; добавление элементов возможно до исчерпания всей доступной памяти.
• Быстрая вставка и удаление в начале/середине (для связных списков) — O(1) при известном положении.
• Простота реализации и лежащий в основе многих алгоритмов (сортировка слиянием, обход графа).

Недостатки

• Отсутствие произвольного доступа (для одно- и двусвязных списков) — поиск любого элемента требует O(n) времени, что делает работу с большими списками неэффективной.
• Дополнительные накладные расходы на память — каждый узел хранит ссылку (указатель) помимо данных, что в два-три раза увеличивает объём памяти по сравнению с массивами.
• Плохая кэш-локальность — элементы могут быть разбросаны в памяти процессора, из-за чего обход замедляется по сравнению с массивом.
• Сложность многопоточной обработки — параллельные модификации требуют блокировки или специальных структур (lock-free списки).

Реализации в популярных языках

• Python: list — динамический массив (не связный список), collections.deque — двусторонняя очередь на основе двусвязного списка.
• C++: std::list (двусвязный), std::forward_list (односвязный) из стандартной библиотеки шаблонов (STL).
• Java: LinkedList<E> (двусвязный), ArrayList (динамический массив с интерфейсом списка).
• C#: List<T> (динамический массив), LinkedList<T> (двусвязный).
• JavaScript: массивы Array и очередь Queue (реализуемая через Array или связные узлы).
• Rust: LinkedList<T> из стандартной библиотеки, Vec<T> (массив), VecDeque<T>.

Математическая формализация

В теории формальных языков и комбинаторике список (sequence) — это функция вида \( f: \mathbb{N}_{<n} \to A \), где \( n \) — количество элементов, а \( A \) — множество возможных значений. Для бесконечных списков (строго говоря, нереализуемых в памяти) используется обозначение \( A^{\omega} \) — множество всех последовательностей мощности алеф-нуль. Операции над списками включают конкатенацию, обращение (reverse), фильтрацию и свёртку (fold). В технической литературе списки часто рассматриваются как частный случай алгебраических типов или индуктивно определённых структур (типы данных «cons-ячейка» и «nil» в функциональных языках).

Список как специальный вид документа

В русском документообороте список — это официальный перечень объектов (лиц, предметов, событий), составленный в соответствии с установленными правилами. Списки бывают:

• именные (пофамильные) — например, избирательные списки, списки сотрудников;
• номенклатурные (перечень товаров, материалов, услуг);
• хронологические (с указанием дат);
• географические (населённых пунктов, объектов на местности).

Для каждого списка определяются реквизиты: название, дата составления, порядок нумерации, подписи или гриф утверждения. Юридическое значение списка заключается в том, что он может выступать в качестве первичного документа учёта или служить основанием для финансово-хозяйственных операций.