В зависимости от числа ссылок список называется одно-, двунаправленным и т.д.

В однонаправленном списке каждый элемент содержит ссылку на последующий элемент. Если последний элемент списка содержит «нулевую» ссылку, то есть содержит значение предопределенной константы Nil и, следовательно, не ссылается ни на какой другой элемент, такой список называется линейным.

Для доступа к первому элементу списка, а за ним - и к последующим элементам необходимо иметь адрес первого элемента списка. Этот адрес обычно записывается в специальное поле - указатель на первый элемент, дадим ему специальное, «говорящее» имя - first. Если значение first равно nil, это значит, что список пуст, он не содержит ни одного элемента. Оператор

first: = nil;

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

Структура линейного однонаправленного списка показана на рисунке 17.

Если последний элемент содержит ссылку на первый элемент списка, то такой список называется кольцевым, циклическим. Изменения в списке при этом минимальны - добавляется ссылка с последнего на первый элемент списка: в адресной части последнего элемента значение Nil заменяется на адрес первого элемента списка (см. рис. 18).

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

Такая организация списка позволяет от каждого элемента двигаться по списку как в прямом, так и в обратном направлениях. Наиболее удобной при этом является та организация ссылок, при которой движение, перебор элементов в обратном направлении является строго противоположным перебору элементов в прямом направлении. В этом случае список называется симметричным. Например, в прямом направлении элементы линейного списка пронумерованы и выбираются так: 1, 2, 3, 4, 5. Строго говоря, перебирать элементы в обратном направлении можно по-разному, соответствующим способом организуя ссылки, например: 4, 1, 5, 3, 2. Симметричным же будет называться список, реализующий перебор элементов в таком порядке: 5, 4, 3, 2, 1.

Следует заметить, что «обратный» список, так же, как и прямой, является просто линейным однонаправленным списком, который заканчивается элементом со ссылкой, имеющей значение nil. Для удобства работы со списком в обратном направлении и в соответствии с идеологией однонаправленного списка нужен доступ к первому в обратном направлении элементу. Такой доступ осуществляется с помощью указателя last на этот первый в обратном направлении элемент. Структура линейного двунаправленного симметричного списка дана на рис. 19.

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

Описать элемент однонаправленного списка (см. рис 1) можно следующим образом:

Type

Tpoint=^Tzap;

Tzap=record

inf1: integer; {первое информационное поле }

inf2: string; {второе информационное поле }

next: Tpoint; {ссылочное поле }

End;

Из этого описания видно, что имеет место рекурсивная ссылка: для описания типа Tpoint используется тип Tzap, а при описании типа Tzap используется тип Tpoint. По соглашениям Паскаля в этом случае сначала описывается тип «указатель», а затем уже тип связанной с ним переменной. Правила Паскаля только при описании ссылок допускают использование идентификатора (Tzap) до его описания. Во всех остальных случаях, прежде чем упомянуть идентификатор, необходимо его определить.

В случае двунаправленного списка в описании должно появиться еще одно ссылочное поле того же типа, например,

Type

Tpoint=^Tzap;

Tzap = record

inf1: integer; { первое информационное поле }

inf2: string; { второе информационное поле }

next: Tpoint; {ссылочное поле на следующий элемент}

prev: Tpoint; {ссылочное поле на предыдущий элемент}

End;

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

При работе со списками любых видов нельзя обойтись без указателя на первый элемент. Не менее полезными, хотя и не всегда обязательными, могут стать адрес последнего элемента списка и количество элементов. Эти данные могут существовать по отдельности, однако их можно объединить в единую структуру типа «запись» (из-за разнотипности полей: два поля указателей на элементы и числовое поле для количества элементов). Эта структура и будет представлять так называемый головной элемент списка. Следуя идеологии динамических структур данных, головной элемент списка также необходимо сделать динамическим, выделяя под него память при создании списка и освобождая после окончания работы. Использование данных головного элемента делает работу со списком более удобной, но требует определенных действий по его обслуживанию.

Рассмотрим основные процедуры работы с линейным однонаправленным списком без головного элемента. Действия оформлены в виде процедур или функций в соответствии с основными требованиями модульного программирования.

Приведем фрагменты разделов type и var, необходимые для дальнейшей работы с линейным однонаправленным списком без головного элемента.

Type

Telem = ^Tzap;

Tzap = record

inf1: integer; { первое информационное поле }

inf2: string; { второе информационное поле }

next: Telem; {ссылочное поле }

End;

Var

first, { указатель на первый элемент списка }

p, q, t: Telem; {рабочие указатели, с помощью которых будет выполняться работа с элементами списка }