Двусвязный линейный список
Основным недостатком односвязного списка является невозможность удаления узла, когда известен только указатель на него и неизвестен указатель на предшественника. Этого недостатка лишен двусвязный список, в котором каждый элемент имеет указатели на предшественника и на последователя (рис.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;
Дата добавления: 2014-12-02; просмотров: 1000;