Данные с динамической структурой. Линейные списки. Схематическое представление основных операций. Сложность основных операций.

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой.
В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных.
На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список».
К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и четырёх основных операций:
1.      операция, проверяющая список на пустоту;
2.      операция добавления объекта в список;
3.      операция определения первого (головного) элемента списка;
4.      операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

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

1.     Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей.

2.     Включить новый узел непосредственно перед k-ым узлом.

3.     Исключить k-й узел.

4.     Объединить два (или более) линейных списка в один список.

5.     Разбить линейный список на два (или более) списка.

6.     Сделать копию линейного списка.

7.     Определить количество узлов в списке.

8.     Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах.

9.     Найти в списке узел с заданным значением в некотором поле.