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

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;