Односвязный список

6.2.1 Общая характеристика односвязного списка

Наиболее простой способ объединить или связать некоторое множество элементов - это «вытянуть их в линию», то есть организовать односвязныйсписок (singly linked list, one-linked list).

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

Рисунок 6.1 - Два варианта представления логической структуры односвязного списка

Односвязный список всегда является линейным, поэтому его называют часто линейным односвязным списком (linear singly linked list). Свойство линейности односвязного списка определяется линейностью логической упорядоченности его элементов: для каждого элемента (кроме первого и последнего) имеется единственный предыдущий и единственный последующий элементы. Организованный таким образом список называют еще однонаправленным (one-wаy list).

Для доступа к желаемому элементу списка в общемслу­чае необходимо просматривать список с его начала,даже если указатель текущего элемента расположен близко от искомогоэлемента, но посленего. В кольцевом односвязном списке (ring, circular, cyclic one-linked list), логическая структура которого представлена на рисунке 6.2,очередной просмотрможно начи­нать с текущего элемента, поскольку элементы списка «связаны» в кольцо. Для этого в поле логического указа­теля последнего элемента помещается вместо «пустого» указателя указатель начала списка.

Рисунок 6.2 - Два варианта представления структуры кольцевого односвязного списка

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

- код структуры,

- имя списка,

- указатель (адрес) начала списка (First) - этот указа­тель называетсяуказателем списка (list pointer),

- указатель на текущий элемент (Current),

- текущее количество элементов всписке,

- описатель (дескриптор)элемента.

Указатель, указывающий на некоторый узел списка, называется курсором этого узла: First - это курсор первого элемента списка, Current - курсор текущего элемента.

В одном из содержательных полей каждого элемента иногда размещают так называемыйуказатель возврата (backward pointer), ссылающийся на дескриптор.

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

6.2.2 Структура элемента односвязного списка

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

Type

PNode = ^TNode;

TNode = Record

Key: Integer;

Dat: <идентификатор типа данных>;

Next: PNode;

End;

Указатель типа PNode представляет собой указатель на базовый тип TNode. Базовый тип TNode определяет структуру узла односвязного списка:

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

- поле Dat - это фактически набор полей, описывающих полезные данные;

- для хранения структурных ссылок предназначено поле Next.

Характерной особенностью типа TNode является наличие поля Next, которое должно содержать указатель на данное типа TNode. Записи некоторого типа, содержащие в своих полях указатели на записи такого же типа, называются самоадресующимися записями. А типы самоадресующихся записей называют иногда рекурсивными типами.

Для иллюстрирования операций в односвязном списке нам потребуется описание следующих переменных, которые будут использоваться в качестве внешних курсоров:

Var First, Current, G: PNode;

6.2.3 Формирование односвязного списка

Если указатель списка First равен Nil, то списка еще нет (он пуст). Значит это начальное значение списка. Для его инициализации следует записать: First:= Nil;

Следующий программный код формирует список из N узлов:

ProcedureCreateOneWayList(N: Integer);

Var i: Integer;

Begin

i:= N;

While i > 0 Do Begin

New(Current);

Current^.Next:= First;

First:= Current;

With Current^ Do Begin

Key:= i;

<заполнение полей Current^.Dat>

End;

i:= i-1;

End;

End;

Под управлением процедуры CreateOneWayList список формируется в направлении «от конца к началу», т. е. последний элемент списка будет создан первым. В поля Key заносятся номера узлов. Логическая структура списка, сформированного при N=4, приводится на рисунке 6.3.

Рисунок 6.3 - Структура односвязного списка, сформированного
процедурой CreateOneWayList при N=4

6.2.4 Просмотр односвязного списка

Операция просмотра списка, называемая также прохождением, заключается в переходах курсора Current от узла к узлу по структурным указателям, расположенным в поле Next всех узлов. Просмотр начинается от начала списка (от элемента First^) и производится до достижения узла, у которого в поле Next записано значение Nil.

Программный фрагмент просмотра имеет следующий вид:

Current:= First;

While Current <> Nil Do Begin

With Current^ Do Begin

<действия с полями элемента Current^>

Current:= Current^.Next;

End;

End;

6.2.5 Вставка элемента в односвязный список

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

Рассмотрим включение в список послетекущего элемента (элемента, заданного указателем Current), когда этот текущий элемент не является ни первым и ни последним элементом списка.

На рисунке 6.4 изображена схема, иллюстрирующая первую разновидность операции включения узла с меткой 20. Для организации операции включения требуется дополни­тельный указатель G (типа PNode). Фрагмент программной реа­лизации этой операции включения может выглядеть так:

New(G); G^.Key:= 20;

G^.Next:= Current^.Next;

Current^.Next:= G;

После выполнения операторов первой строки этого фрагмента

а) в памяти образуется ячейка, размер которой определяется типом TNode,

б) указатель G получает направление («начинает указывать») на созданную ячейку,

в) в поле Key этой ячейки заносится значение 20.

Результат этих действий показан на рисунке 6.4 б. Новая ячейка идентифицируется как G^.

При выполнении присваивания во второй строке в поле Next элемента G^ записывается тот же адрес, который хранится в указателе Next текущего элемента. Иначе говоря, указатель G^.Next начинает указывать на то же место в памяти, что и указатель Current^.Next, т. е. на узел с меткой 3. Это показано на рисунке 6.4 в.

Рассмотрение операции вставки можно было бы закончить, приведением логической схемы, показанной на рисунке 6.4 г. Однако эту схему можно преобразовать к более привычному виду односвязного списка, который показан на рисунке 6.5.

Рисунок 6.4 - Этапы операции включения узла в односвязный список

Рисунок 6.5 - Результат вставки узла с меткой 20

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

New(G);

G^.Next:= First;

First:= G;

а для добавления элемента (вставки в конец списка), когда текущим является последний элемент списка, можно использовать следующий код:

New(G);

G^.Next:= Current^.Next; // т.е. G^.Next = Nil

Current^.Next:= G;

6.2.6 Удаление элемента из односвязного списка

Для удаления простейшим вариантом является удаление элемента, находящегося после текущего узла. В этом случае необходимо установить, чтобы указатель Next текущего узла, указывавший до удаления на удаляемый элемент, стал указывать на элемент, расположенный после удаляемого. Если стартовая структура такая же, как изображенная на рисунке 6.4 а, то для удаления элемента с меткой 3 можно использовать следующий программный код:

G:= Current^.Next;;

Current^.Next:= G^.Next;

Dispose(G);

Процесс и результат выполнения операторов этого фрагмента, показан на рисунке 6.6

Рисунок 6.6 - Процесс удаления узла в односвязном списке:

а – «переброска» структурного указателя текущего узла, к узлу с меткой 4,
расположенному после удаляемого узла; б – уничтожение элемента с меткой 3

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

Current:= First^.Next;;

Dispose(First);

First:= Current;

а с помощью фрагмента, приведенного ниже, удаляется последний элемент односвязного списка, если именно этот последний элемент адресуется курсором Current:

G:= First;

While G^.Next <> CurrentDo

G:= G^.Next;

G^.Next:= Nil;

Dispose(Current); Current:= G;

Здесь в While-цикле курсор G перемещается к предпоследнему элементу. Затем в поле структурного указателя элемента G^ записывается значение Nil, в результате чего этот элемент становится последним в списке. Удаляемый элемент Current^ уничтожается, и текущим становится новый последний элемент.