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

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


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.