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

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

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

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

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

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

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

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

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

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

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

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

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

Внутреннее представление линейных списков

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

Последовательное хранение линейных списков рассмотрено во множестве источников и не составляет предмета данной статьи [1]. Также широко рассмотрено связанное хранение линейных списков, но в подавляющем большинстве случаев такая реализация основана на ссылочной реализации [2]. В то же время существует изящная, но мало известная широкому кругу молодых программистов реализация связного хранения линейных списков на базе массивов. Достаточно подробное, хотя и весьма специфическое описание такой реализации дано в [3]. Этому способу и посвящена данная статья.

ПРИМЕЧАНИЕ Такая реализация встречается не так уж редко. Просто она часто скрывается за разными названиями - индексные массивы, массивы соответствия и т.п. Несмотря на разницу в названиях, используется один и тот же алгоритм. – прим.ред.

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

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

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

в конце списка (то есть за последним элементом списка);

между элементами списка.

Навигатор можно передвигать только от начала к концу списка на один элемент за раз. Кроме того, добавлять элементы списка можно только в позиции, на которую ссылается навигатор. А изменять/удалять/читать можно только элементы, которые находятся в позиции, предшествующей той, на которую ссылается навигатор, т.е. впереди по ходу его движения.

Основная идея данной реализации состоит в отделении информации о содержимом элементов списка от информации о порядке их следования. Графически эта идея представлена на рисунке 1.

Рисунок 1.

Далее ссылки будем изображать стрелками, как показано на рисунке 2.

Рисунок 2.

Естественно, что для работы со списком одних только ссылок между элементами недостаточно – надо знать, например, где расположен первый элемент списка, и отличать последний элемент от всех остальных (ведь за ним уже никаких элементов нет). Для этих целей можно было бы ввести две переменные, которые содержали бы индексы начала и конца списка. Мы, однако, этого делать не будем, а воспользуемся приёмом «сворачивания в кольцо» – «свернем» список, введя специальный воображаемый элемент NULL, который всегда будем располагать в элементе с индексом NullElem (имеющим значение 0) массива, используемого для хранения ссылок на элементы списка (назовем его Refs). На рисунке 3 показано графическое представление этой модели.

Заметьте, что теперь ссылки между элементами списка образуют кольцо, начинающееся с NullElem. Таким образом, ссылка с индексом NullElem показывает на первый элемент списка, а если очередная ссылка равна NullElem, то соответствующий элемент является в списке последним.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--