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

---

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

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

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

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

---