Линейный список

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

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

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

Содержание

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

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

Применение

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

Реализации

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home