Список (абстрактный тип данных) - List (abstract data type)

Эта статья о последовательных структурах данных. Для структур данных с произвольным доступом см. Тип данных массива.

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

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

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

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

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

Операции

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

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

Реализации

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

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

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

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

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

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

Приложения

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

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

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

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

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

ноль: () → L

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

первый: L → E

отдых: L → L

с аксиомами

первый (минусы (е, л)) = е

отдых (минусы (е, л)) = л

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

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

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

минусы (е₁, л₁) = минусы (е₂, л₂) если е₁ = е₂ и л₁ = л₂

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

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

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

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

Тип списка образует монада со следующими функциями (используя 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}}}$

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

${\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, присоединиться, добавить и связывать хорошо определены, поскольку они применяются к более глубоким аргументам при каждом рекурсивном вызове.

Тип списка - это аддитивная монада с ноль как монадический нуль и добавить как монадическая сумма.

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

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

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

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

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