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

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

Графически такой список выглядит следующим образом:

Введем структуру, в которой (для простоты, как и раньше) информационной частью info будут целые числа, а адресная часть состоит из двух указателей на предыдущий (Prev) и следующий (Next) элементы:

struct Spis {

int info;

Spis *Prev, *Next;

} ;

Для работы со списком декларируем Spis *begin, *end; – указатели на начало и конец списка соответственно.

Формирование двунаправленного списка проводится в два этапа – формирование первого элемента и добавление нового. Причем добавление может выполняться как в начало, так и в конец списка.