458__ __ ___________Часть III. Современное программирование на C++

Двунаправленный список

Двунаправленный список (double-linked list) состоит из узлов, содержащих данные и два указателя: на следующий узел в списке и на предыдущий. Для последнего узла указатель на "следующий" узел имеет значение null. Такой узел называется хвост. Узел в начале, или голова списка имеет нулевой указатель на предыдущий узел. Благодаря наличию этих двух указателей двунаправленный список может быть пройден в обоих направлениях: от головы к хвосту и от хвоста к голове. Однонаправленный список имеет только один указатель на следующий узел, поэтому его можно пройти только в одном направлении: от головы к хвосту.

Двунаправленные списки-контейнеры из элементов типа STUDENT:

typedef TDoubleListImp<STUDENT> STUDENT_LIST; . typedef TSDoubleListImp<STUDENT> SORTED_STUDENT_LIST;

typedef TIDoubleListImp<STUDENT> STUDENT_POINTER_LIST;

typedef TISDoubleListInip<STUDENT> SORTED_STUDENT_POINTER_LIST;

Большинство функций-членов аналогичны функциям для других контейнеров. Add добавляет элемент данных, инкапсулированный внутри узла, в начало списка. AddAtHead также добавляет элемент в начало, a AddAtTail в конец списка. Detach принимает элемент списка в качестве параметра и удаляет узел, КОТОрЫЙ соответствует Такому Элементу. DetachAtHead И DetachAtTail

удаляют начальный и конечный узлы. Все функции-члены Detach для косвенных классов удаляют или не удаляют объект в зависимости от значения необязательного параметра TShouldDeiete: :DeleteType. (См. раздел "Принадлежность контейнеров").

ФУНКЦИИ FirstThat, LastThat, Flush, ForEach, GetItemsInContainer И IsErPpty

ведут себя так же, как и в случае других контейнеров. peekHead и PeekTaii возвращают значения начала и конца соответственно, не удаляя их.

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

Однонаправленный список имеет такие же функции за исключением возможности ПРЯМОГО ДОСТупа К ХВОСТУ, Следовательно, AddAtTail, DetachAtTail,

PeekTaii и операция декремента недоступны.

Листинг 18.15 демонстрирует использование прямого двунаправленного списка на примере класса STUDENT, определенного в листинге 18.5 (student2.h).

ftinclude <iostream.h>

#include <iomanip.h>

^include <classlib\dlistimp.h>

#include "student2.h"