Реализация связанных списков на базе массивов

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным.

С реализациями линейных списков в императивных языках программирования могут выполняться следующие операции:

получение доступа к некоторому элементу списка для проверки и/или изменения содержимого его полей;

вставка нового элемента сразу перед или после произвольного элемента;

удаление произвольного элемента;

объединение в одном списке двух (или более) линейных списков;

разбиение линейного списка на два (или более) списка;

создание копии линейного списка;

определение количества элементов в списке;

сортировка элементов списка;

поиск элементов с заданным значением.

В одной программе крайне редко возникает необходимость использовать все девять типов операций. При этом достаточно трудно создать единую реализацию линейных списков, при которой эффективно выполнялись бы все эти операции. Поэтому линейные списки могут быть реализованы по-разному в зависимости от класса операций, которые наиболее часто должны с ними выполняться в данной программе, или наиболее критичных к времени выполнения.