Линейный двусвязный список

Этот список свободен от недостатков, присущих односвязному списку. Для этого в каждое звено добавлен еще один указатель на тип звена, значением которого является адрес предыдущего звена списка. Тип звена на языках Си/Си++:

struct Link2

{

int data;

Link2 *next, *prev;

};

Структура списка будет выглядеть следующим образом (значения нулевых указателей показаны для языка Паскаль):

Ведущее звено этого списка создаётся следующим набором операторов:

Link2 *L2 = new Link2;

L2->next = NULL;

L2->prev = NULL;

По операторам создания ведущего звена можно судить о том, является список, 1- или 2-связным, линейным или кольцевым. Нулевые значения указателей next и prev являются признаком линейного списка.

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

Преимущества двусвязного списка:

есть возможность перестроить поврежденный список;

проще выполняются некоторые операции (например, удаление).

Операции с 2-связным списком. Всё, что касалось операций добавления звена и его удаления для 1-связного списка, справедливо и для 2-связного. Так же должен соблюдаться правильный порядок проведения (или удаления) связей между звеньями, но таких операций стало больше, т.к. должны обрабатываться 2 указателя. Кроме того, каждая из операций обладает дополнительными особенностями:

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

2. Возможность перемещаться по списку в обоих направлениях позволяет напрямую задавать удаляемое звено (а не ему предшествующее, как в 1-связном списке). Следствием этого является упрощение как операции удаления, так и операции поиска.

Добавление звена в произвольную позицию за ведущим звеном

void Insert2(Link2* St,int data)

{

Link2* q=new Link2; // 1 Выделение памяти под звено

q->data=data; // 2 Ввод данных

q->next=St->next; // 3 Проведение связи от нового звена вперёд

q->prev=St; // 4 Проведение связи от нового звена назад

St->next=q; // 5 Проведение связи от предыдущего звена к новому

if(q->next) // Проверка наличия следующего звена

q->next->prev=q; // 6 Проведение связи от следующего звена к новому

}

Удаление звена из любого места списка за ведущим звеном

void Delete2(Link2* del)

{

del->prev->next=del->next; // 1 Обработка связи вперёд

if(del->next)

del->next->prev=del->prev; // 2 Обработка связи назад

delete del; // 3 Освобождение памяти

}

Поиск в 2-связном списке

int Search2(Link2* Start,Link2*& Find,int Key)

{

Link2* Cur=Start->next;

int Success=0;

while(Cur && !Success)

{

if(Cur->data==Key)

{

Find=Cur;

Success=1;

break;

}

Cur=Cur->next;

}

return Success;

}

Эта процедура поиска фактически является (за исключением типа данных Link2 вместо Link1) процедурой "обычного" поиска (т.е. не для удаления) в 1-связном списке.

Операция просмотра списка в прямом направлении ничем не отличается от просмотра 1-связного списка.