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

Конечный, упорядоченный набор элементов

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

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

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

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

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

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

Поток — это потенциально бесконечный аналог списка. ^{[2] : §3.5}

Операции

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

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

Реализации

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

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

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

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

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

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

Приложения

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

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

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

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

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

ноль: () → L

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

сначала: Л → Э

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

с аксиомами

первый (конс ( е , л )) = е

остаток (конс ( е , л )) = л

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

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

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

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

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

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

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

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

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

где append определяется как:

${\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 — монадический ноль, а append — монадическая сумма.

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

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

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

Ссылки

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