Список (информатика)

Поделись знанием:
Перейти к: навигация, поиск

В информатике, спи́сок (англ. list) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности. Экземпляры значений, находящихся в списке, называются элементами списка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.

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





Определение

При помощи нотации метода синтаксически-ориентированного конструирования Ч. Хоара определение списка можно записать следующим образом:

<math>List(A) = NIL + (A \times List(A))</math>
<math>prefix = \text{constructor}</math> <math>List(A)</math>
<math>head, tail = \text{selectors}</math> <math>List(A)</math>
<math>null, nonnull = \text{predicates}</math> <math>List(A)</math>
<math>NIL, nonNIL = \text{parts}</math> <math>List(A)</math>

Первая строка данного определения обозначает, что список элементов типа <math>A</math> (говорят: «список над <math>A</math>») представляет собой размеченное объединение пустого списка и декартова произведения атома типа <math>A</math> со списком над <math>A</math>. Для создания списков используются два конструктора (вторая строка определения), первый из которых создаёт пустой список, а второй — непустой соответственно. Вполне понятно, что второй конструктор получает на вход в качестве параметров некоторый атом и список, а возвращает список, первым элементом которого является исходный атом, а остальными — элементы исходного списка. То есть получается префиксация атома к списку, с чем и связано такое наименование конструктора. Здесь необходимо отметить, что пустой список <math>[]</math> не является атомом, а потому не может префиксироваться. С другой стороны, пустой список является как бы нулевым элементом для конструирования списков, поэтому любой список содержит в самом своём конце именно пустой список — с него начинается конструирование.

Третья строка определяет селекторы для списка, то есть операции для доступа к элементам внутри списка. Селектор <math>head</math> получает на вход список и возвращает первый элемент этого списка, то есть типом результата является тип <math>A</math>. Этот селектор не может получить на вход пустой список — в этом случае результат операции неопределён. Селектор <math>tail</math> возвращает список, полученный из входного в результате отсечения его головы (первого элемента). Этот селектор также не может принимать на вход пустой список, так как в этом случае результат операции неопределён. При помощи этих двух операций можно достать из списка любой элемент. Например, чтобы получить третий элемент списка (если он имеется), необходимо последовательно два раза применить селектор <math>tail</math>, после чего применить селектор <math>head</math>. Другими словами, для получения элемента списка, который находится на позиции <math>n</math> (начиная с <math>0</math> для первого элемента, как это принято в программировании), необходимо <math>n</math> раз применить селектор <math>tail</math>, после чего применить селектор <math>head</math>.

Четвёртая строка определения описывает предикаты для списка, то есть функции, возвращающие булевское значение в зависимости от некоторых условий. Первый предикат возвращает значение <math>true</math> в случае, если заданный список пуст. Второй предикат действует наоборот. Наконец, пятая строка описывает части списка, которые, как уже сказано, представляют собой пустой и непустой списки.

Свойства

У определённой таким образом структуры данных имеются некоторые свойства:

  • Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.
  • Тип элементов — тот самый тип <math>A</math>, над которым строится список; все элементы в списке должны быть этого типа.
  • Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).
  • Возможности доступа — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу.
  • Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

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

Списки в языках программирования

Функциональные языки

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

Язык Haskell

Язык Lisp

Императивные языки

См. также

Напишите отзыв о статье "Список (информатика)"

Отрывок, характеризующий Список (информатика)

– Графинюшка, – послышался голос графа из за двери. – Ты не спишь? – Наташа вскочила босиком, захватила в руки туфли и убежала в свою комнату.
Она долго не могла заснуть. Она всё думала о том, что никто никак не может понять всего, что она понимает, и что в ней есть.
«Соня?» подумала она, глядя на спящую, свернувшуюся кошечку с ее огромной косой. «Нет, куда ей! Она добродетельная. Она влюбилась в Николеньку и больше ничего знать не хочет. Мама, и та не понимает. Это удивительно, как я умна и как… она мила», – продолжала она, говоря про себя в третьем лице и воображая, что это говорит про нее какой то очень умный, самый умный и самый хороший мужчина… «Всё, всё в ней есть, – продолжал этот мужчина, – умна необыкновенно, мила и потом хороша, необыкновенно хороша, ловка, – плавает, верхом ездит отлично, а голос! Можно сказать, удивительный голос!» Она пропела свою любимую музыкальную фразу из Херубиниевской оперы, бросилась на постель, засмеялась от радостной мысли, что она сейчас заснет, крикнула Дуняшу потушить свечку, и еще Дуняша не успела выйти из комнаты, как она уже перешла в другой, еще более счастливый мир сновидений, где всё было так же легко и прекрасно, как и в действительности, но только было еще лучше, потому что было по другому.

На другой день графиня, пригласив к себе Бориса, переговорила с ним, и с того дня он перестал бывать у Ростовых.


31 го декабря, накануне нового 1810 года, le reveillon [ночной ужин], был бал у Екатерининского вельможи. На бале должен был быть дипломатический корпус и государь.
На Английской набережной светился бесчисленными огнями иллюминации известный дом вельможи. У освещенного подъезда с красным сукном стояла полиция, и не одни жандармы, но полицеймейстер на подъезде и десятки офицеров полиции. Экипажи отъезжали, и всё подъезжали новые с красными лакеями и с лакеями в перьях на шляпах. Из карет выходили мужчины в мундирах, звездах и лентах; дамы в атласе и горностаях осторожно сходили по шумно откладываемым подножкам, и торопливо и беззвучно проходили по сукну подъезда.
Почти всякий раз, как подъезжал новый экипаж, в толпе пробегал шопот и снимались шапки.
– Государь?… Нет, министр… принц… посланник… Разве не видишь перья?… – говорилось из толпы. Один из толпы, одетый лучше других, казалось, знал всех, и называл по имени знатнейших вельмож того времени.
Уже одна треть гостей приехала на этот бал, а у Ростовых, долженствующих быть на этом бале, еще шли торопливые приготовления одевания.
Много было толков и приготовлений для этого бала в семействе Ростовых, много страхов, что приглашение не будет получено, платье не будет готово, и не устроится всё так, как было нужно.
Вместе с Ростовыми ехала на бал Марья Игнатьевна Перонская, приятельница и родственница графини, худая и желтая фрейлина старого двора, руководящая провинциальных Ростовых в высшем петербургском свете.
В 10 часов вечера Ростовы должны были заехать за фрейлиной к Таврическому саду; а между тем было уже без пяти минут десять, а еще барышни не были одеты.
Наташа ехала на первый большой бал в своей жизни. Она в этот день встала в 8 часов утра и целый день находилась в лихорадочной тревоге и деятельности. Все силы ее, с самого утра, были устремлены на то, чтобы они все: она, мама, Соня были одеты как нельзя лучше. Соня и графиня поручились вполне ей. На графине должно было быть масака бархатное платье, на них двух белые дымковые платья на розовых, шелковых чехлах с розанами в корсаже. Волоса должны были быть причесаны a la grecque [по гречески].
Все существенное уже было сделано: ноги, руки, шея, уши были уже особенно тщательно, по бальному, вымыты, надушены и напудрены; обуты уже были шелковые, ажурные чулки и белые атласные башмаки с бантиками; прически были почти окончены. Соня кончала одеваться, графиня тоже; но Наташа, хлопотавшая за всех, отстала. Она еще сидела перед зеркалом в накинутом на худенькие плечи пеньюаре. Соня, уже одетая, стояла посреди комнаты и, нажимая до боли маленьким пальцем, прикалывала последнюю визжавшую под булавкой ленту.
– Не так, не так, Соня, – сказала Наташа, поворачивая голову от прически и хватаясь руками за волоса, которые не поспела отпустить державшая их горничная. – Не так бант, поди сюда. – Соня присела. Наташа переколола ленту иначе.
– Позвольте, барышня, нельзя так, – говорила горничная, державшая волоса Наташи.
– Ах, Боже мой, ну после! Вот так, Соня.
– Скоро ли вы? – послышался голос графини, – уж десять сейчас.
– Сейчас, сейчас. – А вы готовы, мама?
– Только току приколоть.
– Не делайте без меня, – крикнула Наташа: – вы не сумеете!
– Да уж десять.
На бале решено было быть в половине одиннадцатого, a надо было еще Наташе одеться и заехать к Таврическому саду.
Окончив прическу, Наташа в коротенькой юбке, из под которой виднелись бальные башмачки, и в материнской кофточке, подбежала к Соне, осмотрела ее и потом побежала к матери. Поворачивая ей голову, она приколола току, и, едва успев поцеловать ее седые волосы, опять побежала к девушкам, подшивавшим ей юбку.
Дело стояло за Наташиной юбкой, которая была слишком длинна; ее подшивали две девушки, обкусывая торопливо нитки. Третья, с булавками в губах и зубах, бегала от графини к Соне; четвертая держала на высоко поднятой руке всё дымковое платье.
– Мавруша, скорее, голубушка!