Чтобы сослаться на двунаправленный кольцевой список как на единый программный объект, используется указатель, значением которого является ссылка на заглавное звено списка.

Р ассмотренный выше способ образования двунаправленного списка не является единственно возможным: можно не включать заглавное звено списка в кольцо:

Каждый метод имеет свои достоинства и недостатки, в частности во вставке элементов в конец или начало.

Над списками определены те же основные операции, что и над цепочками:

 поиск элемента в списке;

 вставка заданного элемента в указанное место списка;

 удаление из списка заданного элемента.

Удаление элемента. Для исключения элемента достаточно изменить ссылку в поле *СЛЕД у предшествующего ему звена и ссылку в поле *ПРЕД у звена, следующего за исключаемым. Для экономичного расходования памяти удаленное из списка звено рекомендуется уничтожить оператором dispose.

Поиск элемента производится перебором элементов с помощью ссылок, содержащихся в каждом звене.

2.15.2 Очередь

Самыми распространенными случаями линейного односвязного списка

являются очередь и стек.

Очередь  это частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента строго в конец (хвост) списка, а извлечение (удаление) строго из начала (головы) очереди.

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

начало конец

взять добавить

Очередь  динамическая структура или дисциплина обслуживания, организованная по принципу FIFO (first in-first out). "Первым пришел - первым ушел". Основные операции для работы с очередями: добавление нового элемента в конец очереди (занесение заказа на обслуживание); удаление элемента из начала очереди для его обслуживания, при этом выбранный элемент, естественно, исключается из очереди. Таким образом, в очереди доступны только ее начало и конец.

Для создания очереди и работы с ней необходимо иметь как минимум два указателя: на начало очереди (BegP) и на конец очереди EndQ. Кроме того, для освобождения памяти удаляемых элементов и удобства работы с очередью требуется дополнительный временный указатель (t).

Функции, которые могут быть использованы при работе с очередями:

1) ADDE1( ) [insert( )] вставляет элемент (добавить в очередь элемент), отводит память под очередной элемент, заносит в него нужную информацию и ставит в конец очереди;

2) GetDELEl( ) [take_off( )] удаляет из очереди ее первый элемент, свобождает память и перемещает указатель начала очереди на следующий элемент.

Пример. Создание очереди (односвязного списка) добавлением элементов в начало

Program queue0; {queue0.pas}

Uses crt;

Type

ptr=^elem;

elem=record

inf: integer;

next: ptr

end;

Var beg_p, t, end_q: ptr;

x: integer;

i: byte;

Procedure ADDEl(val:integer); {Добавление элемента}

Var pt:ptr;

Begin

new(pt);

pt^.inf:=val;

pt^.next:=nil;

if end_q = nil then Beg_p:=pt {если создается первый элемент}

else end_q^.next:=pt; {если создается очередной элемент}

End_q:=pt

End;

Procedure GetDelEl(Var Val:integer);

var pt:ptr;

begin

val:=beg_p^.inf;

pt:=beg_p;

beg_P:=pt^.next;

if Beg_p=nil then end_q:=nil; {если удаляется последний элемент}

dispose(pt)

end;

BEGIN

clrscr;

Beg_p:=nil;

end_q:=nil; {Начальная установка указателей}

for i:=1 to 10 do AddEl(i);{Создание очереди из 10 элементов}

{Удаление очереди с распечаткой значений ее элементов}

while Beg_p<>nil do

begin

GetDelEl(x);

writeln('x=',x:4)

end;

END.