Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой.

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных.

На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список».

К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и четырёх основных операций:

1. операция, проверяющая список на пустоту;
2. операция добавления объекта в список;
3. операция определения первого (головного) элемента списка;
4. операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

Характеристики

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

Реализации

См. также

• Список структур данных
• Связный список
• Массив