Чуриков Константин, Донбасский государственный технический университет
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным.
С реализациями линейных списков в императивных языках программирования могут выполняться следующие операции:
получение доступа к некоторому элементу списка для проверки и/или изменения содержимого его полей;
вставка нового элемента сразу перед или после произвольного элемента;
удаление произвольного элемента;
объединение в одном списке двух (или более) линейных списков;
разбиение линейного списка на два (или более) списка;
создание копии линейного списка;
определение количества элементов в списке;
сортировка элементов списка;
поиск элементов с заданным значением.
В одной программе крайне редко возникает необходимость использовать все девять типов операций. При этом достаточно трудно создать единую реализацию линейных списков, при которой эффективно выполнялись бы все эти операции. Поэтому линейные списки могут быть реализованы по-разному в зависимости от класса операций, которые наиболее часто должны с ними выполняться в данной программе, или наиболее критичных к времени выполнения.
Основные способы хранения линейных списков в памяти компьютера можно разделить на способы последовательного и связанного хранения. При последовательном хранении элементы списка располагаются в памяти в последовательных ячейках, при этом один элемент следует сразу же за другим. Связанное хранение представляет собой более гибкую схему, при которой каждый элемент списка содержит связь со следующим элементом, а их взаимное расположение в памяти может быть произвольным. Каждый способ имеет свои преимущества и недостатки. При выборе способа хранения в конкретной программе следует учитывать, какие операции и с какой интенсивностью будут выполняться над линейными списками, стоимость их выполнения и объем необходимой памяти для хранения списка.
Последовательное хранение линейных списков рассмотрено во множестве источников и не составляет предмета данной статьи [1]. Также широко рассмотрено связанное хранение линейных списков, но в подавляющем большинстве случаев такая реализация основана на ссылочной реализации [2]. В то же время существует изящная, но мало известная широкому кругу молодых программистов реализация связного хранения линейных списков на базе массивов. Достаточно подробное, хотя и весьма специфическое описание такой реализации дано в [3]. Этому способу и посвящена данная статья.
ПРИМЕЧАНИЕ
Такая реализация встречается не так уж редко. Просто она часто скрывается за разными названиями - индексные массивы, массивы соответствия и т.п. Несмотря на разницу в названиях, используется один и тот же алгоритм. – прим.ред.
