Пример описания списка

Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
End;

Создадим первый элемент списка:

New (u); {выделяем место в памяти}
u^. Next:= nil; {указатель пуст}
u^. Inf:=3;

Продолжим формирование списка. Для этого нужно добавить элемент либо в конец списка, либо в голову.

А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:

· получить память для нового элемента;

· поместить туда информацию;

· присоединить элемент к голове списка.

New(x);
Readln(x^.Inf);
x^. Next:= u;
u:= x;

Б)Добавление элемента в конец списка. Для этого введем вспомогательную переменную, которая будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv (хвост).

x:= hv;

New(x^. next); {выделяем память для следующего элемента}

x:= x^.next;
x^.next:= nil;
x^. inf:= 5;
hv:=x;

Просмотр списка

While u<> nil do
Begin
Writeln (u^.inf);
u:= u^.next;>
end;

Удаление элемента из списка

А)Удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель.

x:= u;
u:= u^.next;
dispose(x);

Б) Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.

x:= u;
while (x<> nil) and (x^. inf<> digit) do
begin
dx:= x;
x:= x^.next;
end;
dx:= x^.next:
dispose(x);

В)Удаление из конца списка. Для этого нужно найти предпоследний элемент.

x:= u; dx:= u;
while x^.next<> nil do
begin
dx:= x; x:= x^.next;
end;
dx^.next:= nil;
dispose(x);

Прохождение списка. Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.

summa:= 0;
x:= u;
while x<> nil do
begin
summa:= summa+ x^.inf;
x:= x^.next;
end;

Динамические объекты сложной структуры

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