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

Абстрактный тип данных, используемый в информатике

В информатике список или последовательность — это абстрактный тип данных , который представляет конечное число упорядоченных значений , где одно и то же значение может встречаться более одного раза. Экземпляр списка — это компьютерное представление математической концепции кортежа или конечной последовательности ; (потенциально) бесконечный аналог списка — это поток . ^{[1] : §3.5} Списки являются базовым примером контейнеров , поскольку они содержат другие значения. Если одно и то же значение встречается несколько раз, каждое появление считается отдельным элементом.

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

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

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

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

Операции

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

• конструктор для создания пустого списка ;
• операция проверки того, пуст ли список;
• операция добавления объекта в список
• операция добавления объекта в список
• операция определения первого компонента (или «головы») списка
• операция обращения к списку, состоящему из всех компонентов списка, кроме его первого (это называется «хвост» списка).
• операция доступа к элементу по заданному индексу.

Реализации

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

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

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

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

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

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

Приложения

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

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

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

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

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

ноль: () → L

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

сначала: Л → Е

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

с аксиомами

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

отдых (минусы ( е , л )) знак равно л

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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 , с помощью:

${\displaystyle {\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}}}$

${\displaystyle {\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 . По сути, это свободный моноид над множеством элементов списка.

Смотрите также

• Множество
• Очередь
• Набор
• Куча
• Транслировать

Рекомендации

1. Абельсон, Гарольд; Сассман, Джеральд Джей (1996). Структура и интерпретация компьютерных программ . МТИ Пресс.
2. Рейнгольд, Эдвард; Нивергельт, Юрг; Нарсингх, Део (1977). Комбинаторные алгоритмы: теория и практика . Энглвуд Клиффс, Нью-Джерси: Прентис Холл. стр. 38–41. ISBN 0-13-152447-Х.
3. Барнетт, Гранвилл; Дель Тонга, Лука (2008). «Структуры данных и алгоритмы» (PDF) . mta.ca. _ Проверено 12 ноября 2014 г.
4. Лерусалимский, Роберто (декабрь 2003 г.). Программирование на Lua (первое издание) (Первое изд.). Луа.орг. ISBN 8590379817. Проверено 12 ноября 2014 г.
5. Стил, Гай (1990). Common Lisp (Второе изд.). Цифровая пресса. стр. 29–31. ISBN 1-55558-041-6.