Линейный
однонаправленный список — это структура данных, состоящая из элементов
одного типа, связанных между собой.
В информатике линейный список обычно определяется
как абстрактный тип данных (АТД), формализующий понятие
упорядоченной коллекции данных.
На практике линейные
списки обычно реализуются при помощи массивов и связных списков.
Иногда термин «список» неформально используется также как синоним понятия
«связный список».
К примеру, АТД
нетипизированного изменяемого списка может быть определён как набор
из конструктора и четырёх основных операций:
1.
операция, проверяющая список на пустоту;
2.
операция добавления объекта в список;
3.
операция определения первого (головного) элемента списка;
4.
операция доступа к списку, состоящему из всех элементов исходного списка,
кроме первого.
Характеристики
·
Длина списка. Количество элементов в списке.
·
Списки могут быть типизированными или нетипизированными.
Если список типизирован, то тип его элементов задан, и все его элементы должны
иметь типы, совместимые с заданным типом элементов списка. Обычно списки,
реализованные при помощи массивов, являются типизированными.
·
Список может быть сортированным или несортированным
·
В зависимости от реализации может быть возможен произвольный доступ к
элементам списка.
Операции, которые мы имеем право выполнять с
линейными списками, включают, например, следующие:
1. Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей.
2. Включить новый узел непосредственно перед k-ым узлом.
3. Исключить k-й узел.
4. Объединить два (или более) линейных списка в один список.
5. Разбить линейный список на два (или более) списка.
6. Сделать копию линейного списка.
7. Определить количество узлов в списке.
8. Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах.
9. Найти в списке узел с заданным значением в некотором поле.
1. Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей.
2. Включить новый узел непосредственно перед k-ым узлом.
3. Исключить k-й узел.
4. Объединить два (или более) линейных списка в один список.
5. Разбить линейный список на два (или более) списка.
6. Сделать копию линейного списка.
7. Определить количество узлов в списке.
8. Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах.
9. Найти в списке узел с заданным значением в некотором поле.