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

Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы.

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

При вставке нового элемента в двусвязный список могут быть три случая: элемент вставляется в начало, в середину и в конец списка.

Построение двусвязного списка выполняется аналогично построению односвязного за исключением того, что необходимо установить две ссылки. Поэтому в структуре должны быть описаны два указателя связи:

struct sp

{

int x;

sp *next;

sp *prev;

};

Как и в односвязных списках, для получения элемента данных двусвязного списка необходимо переходить по ссылкам до тех пор, пока не будет найден искомый элемент.

При удалении элемента двусвязного списка могут возникать три случая: удаление первого элемента, удаление элемента из середины и удаление последнего элемента.