Список (абстрактный тип данных)

Эта статья о последовательных структурах данных. Фундаментальную концепцию упорядочения информации см. в List . Структуры данных с произвольным доступом см. в разделе Массив (тип данных) .

В информатике список элементов , или последовательность — это набор число которых конечно и в определенном порядке . Экземпляр математической списка — это компьютерное представление концепции кортежа или конечной последовательности .

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

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

Термин «список» также используется для обозначения нескольких конкретных структур данных , которые можно использовать для реализации абстрактных списков, особенно связанных списков и массивов . В некоторых контекстах, например, в программировании на Лиспе , термин список может относиться конкретно к связанному списку, а не к массиву. В программировании на основе классов списки обычно предоставляются как экземпляры подклассов общего класса «список» и просматриваются через отдельные итераторы .

Многие языки программирования обеспечивают поддержку типов данных списков и имеют специальный синтаксис и семантику для списков и операций со списками. Список часто можно составить, записывая элементы последовательно, разделяя их запятыми , точками с запятой и/или пробелами , внутри пары разделителей, таких как круглые скобки «()», квадратные скобки «[]», фигурные скобки «{}» или угловые скобки '<>'. Некоторые языки могут позволять индексировать или нарезать типы списков, как типы массивов , и в этом случае тип данных более точно описывается как массив.

В теории типов и функциональном программировании абстрактные списки обычно определяются индуктивно с помощью двух операций: nil , которая создает пустой список, и cons , которая добавляет элемент в начало списка.

Поток — это потенциально бесконечный аналог списка.

Операции

Реализация структуры данных списка может обеспечивать некоторые из следующих операций :

• создавать
• тест на пустой
• добавить элемент в начало или конец
• доступ к первому или последнему элементу
• доступ к элементу по индексу

Реализации

Списки обычно реализуются либо как связанные списки (одно- или двусвязные), либо как массивы , обычно переменной длины или динамические массивы .

Стандартный способ реализации списков, берущий свое начало в языке программирования Lisp , заключается в том, чтобы каждый элемент списка содержал как свое значение, так и указатель, указывающий расположение следующего элемента в списке. В результате получается связанный список или дерево , в зависимости от того, есть ли в списке вложенные подсписки. Некоторые старые реализации Lisp (например, реализация Lisp символики 3600 ) также поддерживали «сжатые списки» (с использованием кодирования CDR ), которые имели специальное внутреннее представление (невидимое для пользователя). Списками можно манипулировать с помощью итерации или рекурсии . Первое часто предпочтительнее в императивных языках программирования , тогда как второе является нормой в функциональных языках .

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

Поддержка языков программирования

Некоторые языки не предлагают структуру данных списка , но предлагают использование ассоциативных массивов или каких-либо таблиц для эмуляции списков. Например, Lua предоставляет таблицы. Хотя Lua хранит внутри себя списки с числовыми индексами в виде массивов, они по-прежнему выглядят как словари.

В Lisp списки являются основным типом данных и могут представлять как программный код, так и данные. В большинстве диалектов список первых трех простых чисел можно записать как (list 2 3 5). В нескольких диалектах Lisp, включая Scheme , список представляет собой набор пар, состоящий из значения и указателя на следующую пару (или нулевое значение), образующий односвязный список.

Приложения

В отличие от массива , список может расширяться и сжиматься.

В вычислениях списки реализовать проще, чем множества. Конечное множество в математическом смысле можно реализовать как список с дополнительными ограничениями; то есть повторяющиеся элементы запрещены и порядок не имеет значения. Сортировка списка ускоряет определение наличия данного элемента в наборе, но для обеспечения порядка требуется больше времени для добавления новой записи в список. Однако в эффективных реализациях наборы реализуются с использованием самобалансирующихся двоичных деревьев поиска или хеш-таблиц , а не списка.

Списки также составляют основу для других абстрактных типов данных, включая очередь , стек и их варианты.

Абстрактное определение

Тип абстрактного списка L с элементами некоторого типа E ( мономорфный список) определяется следующими функциями:

ноль: () → L

минусы: E × L → L

сначала: Л → Е

остальное: Л → Л

с аксиомами

первый (cons ( e , l )) = e

отдых (cons( e , l )) = l

для любого элемента e и любого списка l . Подразумевается, что

минусы ( е , л ) ≠ л

минусы ( е , л ) ≠ е

минусы ( е ₁ , л ₁ ) = минусы ( е ₂ , л ₂ ), если е _{1 знак} равно е ₂ и л ₁ = л ₂

Обратите внимание, что first (nil())) и rest (nil()) не определены.

Эти аксиомы эквивалентны аксиомам абстрактного типа данных стека .

В теории типов приведенное выше определение проще рассматривать как индуктивный тип, определенный в терминах конструкторов: nil и cons . можно представить как преобразование 1 + E × L → L. В алгебраических терминах это first и rest затем получаются путем сопоставления с образцом в конструкторе cons и отдельной обработки нулевого случая.

Монада списка

Тип списка образует монаду со следующими функциями (с использованием E ^* вместо L для представления мономорфных списков с элементами типа E ):

${\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}$

${\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

где добавление определяется как:

${\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}$

Альтернативно, монада может быть определена с помощью операций return , fmap и join , с помощью:

${\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

${\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

что fmap , join , append иbind Обратите внимание , четко определены, поскольку они применяются к все более глубоким аргументам при каждом рекурсивном вызове.

Тип списка — аддитивная монада, где nil — монадический ноль, а add — монадическая сумма.

Списки образуют моноид при операции добавления . Идентификационным элементом моноида является пустой список nil . По сути, это свободный моноид над множеством элементов списка.

См. также

• Тип данных массива — тип данных, представляющий упорядоченный набор элементов (значений или переменных). Страницы, отображающие краткие описания целей перенаправления.
• Очередь – абстрактный тип данных
• Set — абстрактный тип данных для хранения уникальных значений.
• Стек — абстрактный тип данных.
• Поток — последовательность элементов данных, доступных с течением времени.