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

Двунаправленный список является сложной динамической структурой, состоящей из последовательности элементов, каждый из которых содержит информационную часть и два указате­ля на соседние элементы. При этом два соседних элемента должны содержать взаимные ссылки друг на друга.

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

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

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле 1;

адресное поле 2;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка;

адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.

Например:

struct list {

type elem ;

list *next, *pred ;

}

list *headlist ;

где type – тип информационного поля элемента списка;

*next, *pred – указатели на следующий и предыдущий элементы этой структуры соответственно.

Переменная-указатель headlist задает список как единый программный объект, ее значение – указатель на первый (или заглавный) элемент списка.

Основные операции, выполняемые над двунаправленным списком, те же, что и для однонаправленного списка. Так как двунаправленный список более гибкий, чем однонаправленный, то при включении элемента в список, нужно использовать указатель как на элемент, за которым происходит включение, так и указатель на элемент, перед которым происходит включение. При исключении элемента из списка нужно использовать как указатель на сам исключаемый элемент, так и указатели на предшествующий или следующий за исключаемым элементы. Но так как элемент двусвязного списка имеет два указателя, то при выполнении операций включения/исключения элемента надо изменять больше связей, чем в односвязном списке. Поиск элемента в двусвязном списке можно вести:

а) просматривая элементы от начала к концу списка;

б) просматривая элементы от конца списка к началу;

в) просматривая список в обоих направлениях одновременно: от начала к середине списка и от конца к середине (учитывая, что элементов в списке может быть четное или нечетное количество).