Список (абстрактный тип данных)
В информатике список элементов , или последовательность — это набор число которых конечно и в определенном порядке . Экземпляр математической списка — это компьютерное представление концепции кортежа или конечной последовательности .
Список может содержать одно и то же значение более одного раза, и каждое его появление считается отдельным элементом.
Термин «список» также используется для обозначения нескольких конкретных структур данных , которые можно использовать для реализации абстрактных списков, особенно связанных списков и массивов . В некоторых контекстах, например, в программировании на Лиспе , термин список может относиться конкретно к связанному списку, а не к массиву. В программировании на основе классов списки обычно предоставляются как экземпляры подклассов общего класса «список» и просматриваются через отдельные итераторы .
Многие языки программирования обеспечивают поддержку типов данных списков и имеют специальный синтаксис и семантику для списков и операций со списками. Список часто можно составить, записывая элементы последовательно, разделяя их запятыми , точками с запятой и/или пробелами , внутри пары разделителей, таких как круглые скобки «()», квадратные скобки «[]», фигурные скобки «{}» или угловые скобки '<>'. Некоторые языки могут позволять индексировать или нарезать типы списков, как типы массивов , и в этом случае тип данных более точно описывается как массив.
В теории типов и функциональном программировании абстрактные списки обычно определяются индуктивно с помощью двух операций: nil , которая создает пустой список, и cons , которая добавляет элемент в начало списка. [1]
Поток — это потенциально бесконечный аналог списка. [2] : §3.5
Операции
[ редактировать ]Реализация структуры данных списка может обеспечивать некоторые из следующих операций :
- создавать
- тест на пустой
- добавить элемент в начало или конец
- доступ к первому или последнему элементу
- доступ к элементу по индексу
Реализации
[ редактировать ]Списки обычно реализуются либо как связанные списки (одно- или двусвязные), либо как массивы , обычно переменной длины или динамические массивы .
Стандартный способ реализации списков, берущий свое начало в языке программирования 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
- отдых (cons( e , l )) = l
для любого элемента e и любого списка l . Подразумевается, что
- минусы ( е , л ) ≠ л
- минусы ( е , л ) ≠ е
- минусы ( е 1 , л 1 ) = минусы ( е 2 , л 2 ), если е 1 знак равно е 2 и л 1 = л 2
Обратите внимание, что first (nil())) и rest (nil()) не определены.
Эти аксиомы эквивалентны аксиомам абстрактного типа данных стека .
В теории типов приведенное выше определение проще рассматривать как индуктивный тип, определенный в терминах конструкторов: nil и cons . можно представить как преобразование 1 + E × L → L. В алгебраических терминах это first и rest затем получаются путем сопоставления с образцом в конструкторе cons и отдельной обработки нулевого случая.
Монада списка
[ редактировать ]Тип списка образует монаду со следующими функциями (с использованием E * вместо L для представления мономорфных списков с элементами типа E ):
где добавление определяется как:
Альтернативно, монада может быть определена с помощью операций return , fmap и join , с помощью:
что fmap , join , append иbind Обратите внимание , четко определены, поскольку они применяются к все более глубоким аргументам при каждом рекурсивном вызове.
Тип списка — аддитивная монада, где nil — монадический ноль, а add — монадическая сумма.
Списки образуют моноид при операции добавления . Идентификационным элементом моноида является пустой список nil . По сути, это свободный моноид над множеством элементов списка.
См. также
[ редактировать ]- Тип данных массива — тип данных, представляющий упорядоченный набор элементов (значений или переменных).
- Очередь – абстрактный тип данных
- Set — абстрактный тип данных для хранения уникальных значений.
- Стек — абстрактный тип данных.
- Поток — последовательность элементов данных, доступных с течением времени.
Ссылки
[ редактировать ]- ^ Рейнгольд, Эдвард; Нивергельт, Юрг; Нарсингх, Део (1977). Комбинаторные алгоритмы: теория и практика . Энглвуд Клиффс, Нью-Джерси: Прентис Холл. стр. 38–41. ISBN 0-13-152447-Х .
- ^ Абельсон, Гарольд; Сассман, Джеральд Джей (1996). Структура и интерпретация компьютерных программ . МТИ Пресс.
- ^ Барнетт, Гранвилл; Дель Тонга, Лука (2008). «Структуры данных и алгоритмы» (PDF) . mta.ca. Проверено 12 ноября 2014 г.
- ^ Лерусалимский, Роберто (декабрь 2003 г.). Программирование на Lua (первое издание) (Первое изд.). Луа.орг. ISBN 8590379817 . Проверено 12 ноября 2014 г.
- ^ Стил, Гай (1990). Common Lisp (Второе изд.). Цифровая пресса. стр. 29–31. ISBN 1-55558-041-6 .