Линейный список
Материал из Википедии — свободной энциклопедии
 |
Эту статью предлагается объединить с Связанный список. Пояснение причин и обсуждение — на странице Википедия:К объединению. Обсуждение длится одну неделю. Дата постановки — 1 апреля 2007 года. Если обсуждение не требуется (очевидный случай) используйте другие шаблоны. |
В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных. Например, АТД нетипизированного списка может быть определён как набор из конструктора и четырёх основных операций:
- конструктора для создания пустого списка;
- операция, проверяющая список на пустоту;
- операция добавления объекта в список;
- операция определения первого (головного) элемента списка;
- операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.
На практике линейные списки обычно реализуются при помощи массивов и связанных списков. Иногда термин «список» неформально используется также как синоним понятия «связанный список».
Содержание |
[править] Характеристики
- Длина списка. Количество элементов в списке.
- Тип элементов списка. В зависимости от реализации может меняться или не меняться во время работы программы.
- Список может быть сортированным или несортированным
- В зависимости от реализации может быть возможен произвольный доступ к элементам списка.
- Списки могут быть типизированные или нетипизированными. Под типизированным списком подразумевается такой, в котором все элементы имеют тип, совместимый с типом списка.
[править] Применение
Как следует из названия, списки используются для хранения списков записей. Эти записи могут быть отсортированы в списке, что позволяет осуществлять быстрый (например, бинарный) поиск, или же несортированы, что обеспечивает быструю вставку элементов.
