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

Эта статья о последовательных структурах данных. Фундаментальную концепцию упорядочения информации см. в 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 . По сути, это свободный моноид над множеством элементов списка.

См. также

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