Связанный список представляет собой структуру данных, которая состоит из узлов (как правило, записей), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи).
Приведем основные базисные операции для работы с однонаправленным связанным списком.
Link[q]:=link[p]; Link[p]:=q;
Здесь q – индекс элемента, который должен быть вставлен в список после элемента с индексом p.
If link[x]<>null then Link[x]:=[link[x]] else \{Элемент x не имеет преемника\};
Отметим, что элемент, следующий в списке за элементом x, называется преемником элемента x, а элемент, pасположенный перед элементом x, называется предшественником элемента x. Если элемент x не имеет преемника, то содержащемуся в нем указателю присваивается значение nil.
Prev:=0; While(link[prev]<>nil)and(link[prev]<>x)do Prev:=link[prev]; If link[prev]=x then Btgin link[prev]:=y; link[y]:=x end Else \{Элемент x не найден\}; Здесь link[0]является началом списка.
Отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка.
В двунаправленном связанным списке каждый элемент имеет два указателя (succlink - описывает связь элемента с преемником, predlink - с предшественником).
Приведем основные базисные операции для работы с двунаправленным связанным списком.
Ответ 1Включение y перед элементом x:
Succlink[y]:=x; Predlink[y]:=predlink[x]; Succlink[predlink[x]]:=y; Predlink[x]:=y;
Ответ 2Включение элемента y после элемента x:
Succlink[y]:=succlink[x]; Predlink[y]:=x; Predlink[succlink[x]]:=y; Succlink[x]:=y;
Ответ 3Исключение элемента x.
Predlink[succlink[x]]:=predlink[x]; Succlink[predlink[x]]:=succlink[x];
Программа 3.Список целых чисел.
{Создается список целых чисел. Числа выбираются случайным образом из интервала 0..9999, затем он упорядочивается, сначала - по возрастанию, затем - по убыванию.