Начнем с процедуры создания списка. Ниже приведен ее код. Здесь создается список целых чисел, и признаком завершения построения является введенное нулевое значение в поле данных.

Механизм управления указателями в процедуре Insert приведен на рис. 1. На рисунке 1. а) показана ситуация перед выполнением процедуры вставки. Необходимо вставить новый элемент x перед элементом b, поэтому в строке (1) задается temp как указатель на ячейку, содержащую элемент b. В строке (2) листинга создается новая ячейка, и в поле next ячейки, содержащей элемент а, ставится указатель на новую ячейку. В строке (3) поле data вновь созданной ячейки принимает значение х, а в строке (4) поле next этой ячейки принимает значение переменной temp, которая хранит указатель на ячейку, содержащую элемент b. На рисунке 1. б) представлен результат выполнения процедуры Insert , где пунктирными линиями показаны новые указатели и номерами (совпадающими с номерами строк в листинге) помечены этапы их создания.

Показана схема манипулирования указателями в процедуре удаления элемента из списка. Старые указатели показаны сплошными линиями, а новые – пунктирной. Ниже приведен код процедуры удаления элемента.

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

Сравнение различных реализаций списков

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

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

2. Выполнение некоторых операторов в одной реализации требует больших вычислительных затрат, чем в другой. Например, процедуры INSERT и DELETE выполняются за постоянное число шагов в случае связанных списков любого размера, но требуют времени, пропорционального числу элементов, следующих за вставленным (или удаляемым) элементом, при использовании массивов. И наоборот, время выполнения функции для выделения предыдущего или последнего элемента списка постоянно при реализации списков посредством массивов, но в это же время пропорционально длине списка в случае реализации, построенной с помощью указателей.

3. Если необходимо вставлять или удалять элементы, положение которых указано с помощью специальной переменной типа position , и значение этой переменной будет использовано позднее, то нецелесообразно использовать реализацию с помощью указателей, поскольку эта переменная не «отслеживает» вставку и удаление элементов.

4. Реализация списков с помощью массивов расточительна по отношению к компьютерной памяти, поскольку резервируется объем памяти, достаточный для максимально возможного размера списка независимо от его реального размера в конкретный момент времени. Реализация с помощью указателей использует столько памяти, сколько необходимо для хранения текущего списка, но требует дополнительную память для указателя каждой ячейки. Таким образом, в разных ситуациях по критерию используемой памяти могут быть выгодны разные реализации.

Дважды связные списки

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

Рис. 3 – Дважды связный список

Важным преимуществом является то, что можно использовать указатель ячейки, содержащей i-й элемент, для определения i-й позиции вместо использования указателя предшествующей ячейки. Однако при этом появляются дополнительные указатели и, следовательно, удлиняются некоторые процедуры. Ниже приведен код объявления дважды связного списка.

Ниже показаны процедуры построения двусвязного списка, а также удаления элемента из него.

Здесь предполагается, что удаляемая ячейка не является ни первой, ни последней в списке. Сплошными линиями показаны указатели до удаления, а пунктирными – после удаления элемента. Сначала с помощью указателя поля previous определяется положение предыдущей ячейки. Затем в поле next этой ячейки устанавливается указатель на ячейку, предшествующую позиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей и при необходимости может быть использована повторно.

Рис. 3 – Удаление элемента из дважды связного списка

ОЧЕРЕДИ И СТЕКИ