Двусвязный линейный список

Основным недостатком односвязного списка является невоз­мож­ность удаления узла, когда известен только указатель на него и неизвестен указатель на пред­шественника. Этого недостатка лишен двусвязный список, в котором каждый элемент имеет указатели на предшественника и на последователя (рис.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. Удаление узла из двусвязного списка

Функция, выполняющая удаление:

void DeleteUzel(UZEL *p){

p->Left->Right=p->Right;

p->Right->Left=p->Left;

delete p;

}