3.2. Списки и их разновидности

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

Рассмотрим список

EL1, EL2, EL3, EL4. (3.1)

Простейшей его реализацией будет структура последовательно связанных компонент, изображенная на рис. 3.1. Каждая компонента в этой структуре состоит из двух ячеек памяти. Первая ячейка содержит сам эле-мент, вторая - указатель следующего элемента, причём последняя компонента не имеет указателя (точ-нее: его значение равно 0), а указатель на первую компонен-ту (FIRST) является внешним.

Такую структуру можно реализовать в виде двух массивов, которые на рис. 3.2 названы NAME и NEXT. Если COMP - компонента в рассматриваемом массиве, то NAME[COMP] - сам элемент, хранящийся там, а NEXT[COMP] - индекс следующего элемента в списке (если такой элемент существует). Если COMP - индекс последнего элемента в этом списке, то NEXT[COMP]=0.

На рис. 3.2 NEXT[0] означает постоянный указатель на первую компоненту в списке. Заметим, что порядок элементов в массиве NAME не совпадает с их порядком в списке. Однако рис. 3.2 даёт верное представ-

Index	NAME	NEXT
0	__	1
1	EL1	3
2	EL4	0
POS3	EL2	4
4	EL3	2
FREE5	__	__
Рис. 3.2. Представление списка (3.1) из четырех элементов

л

элементы в той же последовательности, в какой они расположены в списке (3.1).

Опишем процедуру INS (Insert - вставить), которая вставляет новую компоненту X в список. В ней предполагается, что FREE - номер незанятой ячейки в массивах NAME и NEXT, а POS (POSition – позиция) - индекс той компоненты в списке, после которой следует вставить элемент X.

ение списка, изображенного на рис. 3.1, так как массив NEXT располагает

Процедура INS c формальными параметрами X, FREE, POS имеет вид

procedure INS (X, FREE, POS);

begin

NAME[FREE]Х;

NEXT[FREE]NEXT[POS];

NEXT[POS]FREE;

end.

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

Пример 3.1. Пусть необходимо вставить в список (3.1) новый элемент NEL (New ELement) после элемента EL2 и получить список

EL1, EL2, NEL, EL3, EL4. (3.2)

Если пятая ячейка (FREE=5) в каждом массиве на рис. 3.2 пуста, можно вставить X=NEL после EL2 (POS=3), вызвав процедуру INS c фактическими параметрами NEL, 5, 3. В результате выполнения трёх операторов в процедуре INS получим NAME[5]=NEL, NEXT[5]=4 и NEXT[3]=5; тем самым создадутся массивы, показанные на рис. 3.3.

Index	NAME	NEXT
0	__	1
1	EL1	3
2	EL4	0
POS3	EL2	5
4	EL3	2
5	NEL	4
FREE6	__	__
Рис. 3.3. Представление списка со вставленным элементом NEL

Для того, чтобы удалить компоненту, следующую за компонентой в ячейке I, можно положить

NEXT[I]=NEXT[NEXT[I]].

При желании индекс удалённой компоненты можно поместить в список незанятых ячеек памяти.

Часто в один и тот же массив вкладываются несколько списков. Обычно один из этих списков состоит из незанятых ячеек; будем называть его свободным списком.

Для добавления элемента к списку А можно так изменить процедуру INS, чтобы незанятая ячейка получалась путём удаления первой ячейки в свободном списке. При удалении элемента из списка А соответствующая ячейка возвращается в свободный список для будущего использования

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

Ещё две основные операции над списками - конкатенация (сцепление) двух списков, в результате которой образуется единственный список, и обратная к ней операция расцепления списка после заданного элемента, результатом которого будут два списка.

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

Тривиальной модификацией связанного списка будет следующее, несколько более гибкое представление последовательности: если P_n указывает на S₁ (см. рис. 3.1), то такой список называется циклическим. Это представление даёт возможность достигнуть любого элемента из любого другого элемента последовательности. Включение и исключение элементов здесь осуществляется так же, как и в нециклических списках, в то время как сцепление и расцепление реализуются несколько более сложно.

Еще большая гибкость достигается, если использоватьдважды связанный список, когда каждый элемент S_I последовательности вместо одного имеет два связанных с ним указателя на элементы S_i-1 и S_i+1 (рис. 3.4). В таком списке для любого элемента имеется мгновенный прямой доступ к предыдущему и последующему элементам, в связи с чем облегчаются такие операции, как включение нового элемента перед S_i и исключение элемента S_i без предварительного знания его предшественника. Если есть необходи-мость, дважды связанный список очевид-ным образом можно сделать циклическим.

Index	NAME	PREV	NEXT
. . .	. . .	. . .	. . .
i	a	l	j
. . .	. . .	. . .	. . .
j	b	i	k
. . .	. . .	. . .	. . .
k	c	j	m
. . .	. . .	. . .	. . .

Рис. 3.5. Двухсвязный список:

представление в виде массивов

Из такого списка можно удалить или вставить в него элемент, не зная, где находится предыдущий элемент.

На рис. 3.5 показано заполне ние массивов NAME, PREV и NEXT для фрагмента дважды связанного списка, представленного на рис. 3.4.

Списки можно сделать проходимыми в обоих направлениях, если добавить ещё один массив, называемый PREV (PREVious – предыдущий). Значение PREV[I] равно ячейке, в которой помещается тот элемент списка, который стоит непосредственно перед элементом из ячейки I.

Рассмотрим широко распространённые специального вида списки, с которыми работают ограниченными приёмами: 1) элементы добавляются или удаляются только на одном конце; 2) элементы добавляются на одном конце, а удаляются – с другого конца списка. В первом случае доступ к элементам основан на принципе "последний вошёл - первый вышел" (LIFO - Last Input, First Output), и в этом случае список называется стеком, или магазином. Во втором случае доступ к элементам основан на принципе “первый вошёл - первый вышел” (FIFO - First Input, First Output); такого рода список называется очередью.

Первый специального вида список – стек, который обычно реализуется в виде одного массива. Например, список EL1, EL2, EL3 можно хранить в массиве NAME, как показано на рис. 3.6. Переменная TOP (вершина) является указателем последнего элемента, добавленного к стеку.

Чтобы добавить новый элемент в стек, значение TOP увеличивают на 1, а затем помещают новый элемент в NAME[TOP]. Однако следует иметь в виду, что массив NAME имеет конечную длину l, поэтому перед попыткой вставить новый элемент следует проверить, что TOP<l-1.

Чтобы удалить элемент из вершины стека, надо просто уменьшить значение TOP на 1.

Чтобы узнать, пуст ли стек, достаточно проверить, не имеет ли TOP значение меньше нуля.

Понятно, что время выполнения операций PUSH (ВТОЛКНУТЬ) и POP (ВЫТОЛКНУТЬ) и проверка пустоты стека не зависят от числа элементов в стеке.

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

Другой специальный вид списка - очередь. Как и стек, очередь можно реализовать одним массивом, как показано на рис. 3.7, где приведена очередь, содержащая список из эле-ментов P, Q, R, S, T. Два указателя обозначают ячейки текущих концов очереди, переднего (HEAD - голова) и заднего (TAIL - хвост). Чтобы добавить (ВПИСАТЬ) новый элемент к очереди, полагают TAIL = TAIL+1 и помещают новый элемент в NAME[TAIL]. Чтобы удалить (ВЫПИСАТЬ) элемент из очереди, заменяют HEAD на HEAD +1.

Так как массив NAME имеет конечную длину (пусть l), указатели HEAD и TAIL рано или поздно доберутся до его конца. Если есть уверенность в том, что длина списка, представленногo этой очередью, никогда не превысит l, то можно трактовать NAME[0] как элемент, следующий за элементом NAME[l-1]. Другими словами, можно считать этот список кольцевым.

Очередь обычно используется для предварительного анализа команд в конвейере команд (например, в персональных компьютерах) или при организации векторной обработки данных в суперЭВМ.

При работе со списками удаляемые элементы не обязательно физически стирать, однако при этом возникает проблема сбора мусора (ненужных ячеек памяти).

Элементы, расположенные в виде списка, сами могут быть сложными структурами. При работе, например, со списками массивов, на самом деле массивы не добавляются и не удаляются, ибо каждое добавление или удаление потребовало бы времени, пропорционального размеру массива. Вместо этого добавляются или удаляются указатели массивов. Таким образом, сложную структуру можно добавить или удалить за фиксированное время, не зависящее от её размера.