Основным недостатком односвязного списка является невозможность удаления узла, когда известен только указатель на него и неизвестен указатель на предшественника. Этого недостатка лишен двусвязный список, в котором каждый элемент имеет указатели на предшественника и на последователя (рис.10).
Рис 10. Узел двусвязного списка
Точно так же, как и односвязный список, двусвязный может иметь голову и быть кольцевым. На рис. 11 изображен кольцевой двусвязный список с головой.
Рис. 11. Двусвязный циклический список с головой
Узел двусвязного списка может быть представлен структурой:
struct UZEL{
<тип> Info; // данные узла
UZEL *Left; // указатель на предшественника
UZEL *Right; // указатель на последователя
};
Операция вставки нового узла представлена на рис 12.
Рис.12. Вставка узла в двусвязный список вслед за узлом P
Как и прежде, пунктиром обозначены связи, изменившиеся после выполнения операции. Функция, выполняющая операцию вставки, приведена ниже.
UZEL *InsertUzel(UZEL *p){
// функция вставляет новый узел справа от P
// и возвращает указатель на новый узел
UZEL *Z;
Z=new UZEL;
If(Z==NULL) return NULL; // нет памяти в куче
Z->Left=p;
Z->Right=p->Right;
p->Right->Left=X;
p->Right=X;
return X;
}
Операция удаления узла изображена на рис 13.
Рис 13. Удаление узла из двусвязного списка
Функция, выполняющая удаление:
void DeleteUzel(UZEL *p){
p->Left->Right=p->Right;
p->Right->Left=p->Left;
delete p;
}
