Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Ведущее ( нпн заглавное) звено. Все приведённые выше примеры на языке Си++ подразумевают наличие в списке веду- щего звена. Создаваться это звено может либо отдельной проце- дурой, либо следующим набором операторов (эти же операторы и будут находиться в процедуре):
L iп k1 *L 1 = new L ink1 ; // Выделение памяти под звено L I —>n ex 4 = NULL ; // Ведущее звено одновременно явля-
ется последним

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

Занесение в очередь и извлечение из очереди, построенной
на основе двусвязного списка.

void queue in(Link2*& q, // «Голова» очереди Link2*& е, // «Хвост» очереди

int k) // Вводимые данные

Link2* п = new node; // Новый узел n->data = k;

n->next = q;

98
if (q)

q->prev = п; else
е п;
n—>prev = 0;

int queue out(Link2*& q, Link2*& е) int k = e— >data;

Link2* d = е; е = d->prev; if (е)
e— >next = 0; else
q е;
delete d; return k;
Для упрощения обработки «головы» и «хвоста» очереди ис—
ПOЛЬ3OBtlH ДВ СВЯЗНЫ Й СПИСОК.
В остальных случаях (т.е. для обычных списков) использо— вание ведущего звена является предпочтительным, т.к. позволяет избежать проверок (операторов if) при добавлении и удалении звеньев, т.е. унифицирует операции со списком независимо от места их выполнения. В противном случае либо требуются от- дельные процедуры, например, вставки звена в начало списка, либо более универсальные процедуры с проверкой места вставки или удаления, как в показанных выше процедурах работы с оче— редью. В обоих случаях общий размер машинного кода этих про— цедур вряд ли окажется меньше размера ведущего звена и гово- рить о каком-либо выигрыше в объёме памяти при отказе от ве- дущего звена не приходится.
Недостатки односвязного списка заключаются в следую-
щем:

1. 
   По такому списку можно перемещаться только от началь—
   

ного звена к конечному. Начинать можно с любого звена в спи-

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

2. 
   Наличие только одной связи снижает надёжность хране- ния данных в односвязном списке.
   
3. 
   Следствием первого недостатка является усложнение взаимодействия операций лоиска и удаления.
   

Достоинствами этого списка являются меньший расход памяти по сравнению с другими связными динамическими струк- турами данных (всего один указатель) и простота операций.

2. 
   Линеііный двусвязный спнсок
   

Этот список свободен от недостатков, присущих односвяз- ному списку. Для этого в каждое звено добавлен еще один ука- затель на тип звена, значением которого является адрес преды- дущего звена списка. Тип звена на языке Си++:

struct Link2 int data;
Link2 *next, *prev;
Структура списка будет выглядеть следующим образом (значения нулевых указателей показаны для языка Паскаль):

data
prev	next

nil
L2
nil next


data
prev nil

data
prev	next

Рис. 9.2 — Линейный двусвязный список