Вы здесь

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

Исходный код на C++: 

Теория

Двусвязный список имеет ряд преимуществ над односвязным списком: добавление нового узла в определённую позицию, удаление i-того элемента из последовательности, просмотр списка в обоих направлениях. При ряде достоинств существуют и недостатки, появляется дополнительная переменная указатель на предыдущий элемент (pred). В данной статье описан принцип работы двусвязного циклического списка. Единственное отличие двусвязного циклического списка от двусвязного списка это то, что последний элемент ссылается на первый, а первый на последний. Данное отличие позволяют исключать проверки на «первый» и «последний» элемент. Двусвязный циклический список (далее просто двусвязный список) визуально можно представить в следующем виде (рис.1).


Рис 1 Двусвязный список в графическом виде.

Рассмотрим несколько стандартных функций для двусвязного списка. Функция push добавить новый элемент в i-ую позицию списка. Функция выполняет следующие действия:
1) создаёт новый элемент;
2) копируем значение информационного поля;
3) если данный элемент является единственным;
 3.1)оба указателя (next и pred) ссылаются на этот элемент (рис. 2),
 3.2) указатель first указывает на единственный элемент в списке.
4) иначе сдвигаем указатель на i-ый элемент и добавляем новый элемент перед i-ым.
Добавим новое значение в двусвязный список (push 4), новый элемент будем добавлять после первого. После операции push список содержит один элемент (рис. 2).


Рис 2 Добавление нового значения.

Добавим ещё несколько значений (push 6 и push 7), каждый новый элемент будем добавлять после первого. Список содержит три элемента (рис. 3) в следующей последовательности.


Рис 3. Добавление новых значений

Функция pop выталкивает i-ый элемент из списка. Функция выполняет следующие действия:
1)если список пуст, выходим из функции;
2) если в список содержит единственный элемент;
  2.1) копируем значение информационного поля
  2.2) удаляем элемент из списка
  2.3) присваиваем заголовку пусто
3)иначе сдвигаем указатель на i-ый элемент;
  3.1)если заголовок указывает на i-ый элемент (first==t), тогда перемещаем заголовок на следующий элемент (First=t->next)
  3.2) копируем значение информационного поля
  3.3) удаляем i-ый элемент из списка
4) возвращаем значение информационного поля.
Выполнив функцию pop над линейным списком (выталкиваем 3-ий элемент). Получим следующее состояние связного списка (рис. 4).


Рис 4. Выталкивание элемента.

Функция view пробегает по всем элементам и выводит в консоль значение информационного поля. Просмотр элементов осуществляется слева направо, но легко можно переписать функцию и изменить просмотр элементов справа налево (заменить a=a->next на a=a->pred). Функция clean удаляет все элементы в списке и присваивает заголовку пусто (first=null). После данной операции список возвращается в исходное состояние.

Программная реализация

typedef int newtp;
struct node//описание структуры
{
newtp data;
node *next;
node *pred;
} *First=NULL;
void push(newtp val,int pos)//добавить узел в список в определённую позицию
{
node *a=new node;
a->data=val;
if(First==NULL)//если это первый элемент в списке
{
a->next=a;
a->pred=a;
First=a;
}
else
{
node *t=First;
for(int i=pos;i>1;i--,t=t->next);
t->pred->next=a;
a->pred=t->pred;
a->next=t;//добавляем элемент перед t
t->pred=a;
}
}
newtp pop(int pos)//удалить узел по индексу из списка
{
if(First==NULL) return (newtp)0;//спсок пуст
newtp val;
if(First==First->next)//если это последний элемент в списке
{
val=First->data;
delete First;
First=NULL;
}
else
{
node *t=First;
for(int i=pos;i>1;i--,t=t->next);
if(t==First)First=t->next;//если пытаемся удалить 1-ый элемент то голова указывает на 2-ой
t->pred->next=t->next;//удаляем t элемент
t->next->pred=t->pred;
val=t->data;
delete t;
}
return val;
}
void clean()//удалить все элементы из списка
{
if(First==NULL)return ;
for(node *a=First->next;a!=First;a=a->next)delete a;
delete First;
First=NULL;
}
void view()//просмотр элементов в списке
{
if(First==NULL)return ;
node *a=First;
do
{
printf ("Value=%d \n",(int)a->data);
a=a->next;
}while(a!=First);
}