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

   Связный (линейный) список является структурой данных, в произвольно выбранное место которого могут включаться данные, а также изыматься оттуда.

   Каждая компонента списка определяется ключом.Обычно ключ -  либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи.

   Основные отличия связного списка от стека и очереди следующие:

   - для чтения доступна любая компонента списка;

   - новые компоненты можно добавлять в любое место списка;

   - при чтении компонента не удаляется из списка.

   Над списками выполняются следующие операции:

   - начальное формирование списка (запись первой компоненты);

   - добавление компоненты в конец списка;

   - чтение компоненты с заданным ключом;

   - вставка компоненты в заданное место списка (обычно после  компоненты с заданным ключом);

   -исключение компоненты с заданным ключом из списка.

   Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель,первая из которых определяет начало  списка, вторая - конец списка, остальные- вспомогательные.

   Описание компоненты списка и переменных типа указатель дадим следующим образом: 

   type

    PComp= ^Comp;

    Comp= record

           D:T;

           pNext:PComp

          end;

   var

    pBegin, pEnd, pCKey, pPreComp, pAux: PComp; 

где pBegin - указатель начала списка, pEnd - указатель  конца списка, pCKey, pPreComp, pAux - вспомогательные указатели.

   Начальное формирование списка, добавление компонент в конец списка выполняется так же, как и при формировании очереди.                                                                                                                                                                                                                                                           

   Для чтения и вставки компоненты по ключу необходимо выполнить поиск компоненты с заданным ключом:   

  pCKey:=pBegin;

  while (pCKey<>NIL) and (Key<>pCKey^.D) DO

   pCKey:=pCKey^.pNext;  

Здесь Key - ключ, тип которого совпадает с типом данных компоненты.

   После выполнения  этих операторов указатель pСKey будет определять компоненту с заданным ключом или такая компонента не будет найдена.

   Пусть pCKey определяет компоненту с заданным ключом. Вставка новой компоненты выполняется следующими операторами.

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

  pCKey:=pBegin;

  while (pCKey<>NIL) and (Key<>pCKey^.D) do

   begin

    pPreComp:=pCKey;

    pCKey:=pCKey^.pNext

   end;   

Здесь указатель pCKey определяет компоненту с заданным ключом, указатель pPreComp содержит адрес предыдущей компоненты.   

   Удаление компоненты с ключом Key выполняется оператором.

                                                                                                                                                                   

   Пример. Составить программу, которая формирует список, добавляет в него произвольное количество компонент, выполняет вставку и удаление компоненты по ключу,а затем читает и выводит весь список на  экран дисплея. В    качестве данных взять строку символов.Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.

 

 Program LISTLINKED;

  uses Crt;

  type

   Alfa= String[10];

   PComp= ^Comp;

   Comp= record

          sD:Alfa;

          pNext:PComp

         end;

  var

   pBegin, pEnd, pAux, pCKey, pPreComp: PComp;

   sC, sKey: Alfa;

   bCond: Boolean;

  Procedure CreateLL(var pBegin,pEnd: PComp; var sC: Alfa);

   begin

    New(pBegin);

    pBegin^.pNext:=NIL;

    pBegin^.sD:=sC;

    pEnd:=pBegin

   end;

  Procedure AddLL(var pEnd: PComp; var sC: Alfa);

   var pAux: PComp;

   begin

    New(pAux);

    pAux^.pNext:=NIL;

    pEnd^.pNext:=pAux;

    pEnd:=pAux;

    pEnd^.sD:=sC

   end;

  Procedure Find(var sKey: Alfa; var pBegin,pCKey,pPreComp: PComp;

                 var bCond: Boolean);

   begin

    pCKey:=pBegin;

    while (pCKey <> NIL) and (sKey <> pCKey^.D) do

     begin

      pPreComp:=pCKey;

      pCKey:=pCKey^.pNext

     end;

    if (pCKey = NIL) and (sKey <> pCKey^.sD) then bCond:=FALSE

                                            else bCond:=TRUE

   end;

  Procedure InsComp(var sKey,sC: Alfa);

   var pAux:PComp;

   begin

    Find(sKey,pBegin,pCKey,pPreComp,bCond);

    New(pAux);

    pAux^.sD:=sC;

    pAux^.pNext:=pCKey^.pNext;

    pCKey^.pNext:=pAux

   end;

  Procedure DelComp(var sKey: Alfa; var pBegin: PComp);

   begin

    Find(sKey,pBegin,pCKey,pPreComp,bCond);

    pPreComp^.pNext:=pCKey^.pNext

   end;

  begin

   ClrScr;

   writeln(' ВВЕДИ СТРОКУ ');

   readln(sC);

   CreateLL(pBegin,pEnd,sC);

   repeat

    writeln('ВВЕДИ СТРОКУ ');

    readln(sC);

    AddLL(pEnd,sC)

   until sC='END';

   writeln(' ***** ВЫВОД ИСХОДНОГО СПИСКА *****');

   pAux:=pBegin;

   repeat

    writeln(pAux^.sD);

    pAux:=pAux^.pNext;

   until pAux=NIL;

   writeln;

   writeln('ВВЕДИ КЛЮЧ ДЛЯ ВСТАВКИ СТРОКИ');

   readln(sKey);

   writeln('ВВЕДИ ВСТАВЛЯЕМУЮ СТРОКУ');

   readln(sC);

   InsComp(sKey,sC);

   writeln;

   writeln('ВВЕДИ КЛЮЧ УДАЛЯЕМОЙ СТРОКИ');

   readln(sKey);

   DelComp(sKey,pBegin);

   writeln;

   writeln(' ***** ВЫВОД ИЗМЕНЕННОГО СПИСКА *****');

    pAux:=pBegin;

    repeat

     writeln(pAux^.sD);

     pAux:=pAux^.pNext;

    until pAux=NIL

  end.