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), ссылающийся на дескриптор.

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

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;