На этом шаге мы рассмотрим двунаправленные списки..

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

    Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка.

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

    Построим модель двунаправленного списка. Двунаправленный список строится подобно однонаправленному списку, причем в записи должно быть предусмотрено место для двух указателей. Итак, каждый элемент двунаправленного списка представим записью языка Pascal, которая состоит из трех полей:

    1) информационного поля или поля данных;

    2) ссылки на следующий элемент списка;

    3) ссылки на предыдущий элемент списка.

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

 Type
   PtrRec = ^Rec;
   Rec = record
       Element : TypeElement; 	{поле данных}
       pNext : PtrRec; 	{прямой указатель}
       pPrev : PtrRec; 	{обратный указатель}
     End;

    Двунаправленный список, так же как и однонаправленный, может иметь заглавные звенья и не иметь их.

    Изобразим схематично случай, когда заглавное звено одно:

Рис.1. Двунаправленный список с одним заглавным звеном

    Изобразим пустой двунаправленный список с одним заглавным звеном:

Рис.2. Пустой двунаправленный список с одним заглавным звеном

    Приведем вариант структуры двунаправленного списка с двумя заглавными звеньями:

Рис.3. Двунаправленный список с двумя заглавными звеньями

    Соответствующий пустой двунаправленный список с двумя заглавными звеньями выглядит так:

Рис.4. Пустой двунаправленный список с двумя заглавными звеньями

    Рассмотрим три свойства двунаправленных списков:

    1) по списку можно двигаться в любом направлении;

    2) если List есть указатель на любой элемент двунаправленного списка, то выполняются следующие свойства

 List = List^.pNext^.pPrev

 List = List^.pPrev ^.pNext

Рис.5. Графическая иллюстрация свойств двунаправленного списка

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

Над двунаправленными списками выполняются следующие операции:
• начальное формирование списка (запись первой компоненты);
• добавление компоненты в конец списка;
• вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);
• определение первого или последнего элементов в двунаправленном списке;
• чтение компоненты с заданным ключом; с заданным свойством;
• исключение компоненты с заданным ключом из списка;
• упорядочивание узлов линейного списка в определенном порядке.

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

 Var
   pBegin, pEnd, pCKey, pAux : PtrRec;

    При описании процедур будем предполагать наличие в программе приведенных выше описаний типов для двунаправленных списков.

    На следующем шаге мы рассмотрим двунаправленные списки с заглавным звеном.

Предыдущий шаг Содержание Следующий шаг