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

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

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

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

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

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

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

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