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

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 Структура элемента односвязного списка

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

Дата добавления: 2014-01-07