Связный список.

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

Причем это не потребует реорганизации структуры, которая бы потребовалась в массиве. Минусом связного списка, как и других структур типа «список», в сравнении его с массивом, является отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список – структура последовательно доступа, в то время как массив – произвольного. Последний недостаток снижает эффективность ряда операций.

По типу связности выделяют односвязные, двусвязные, XOR-связные, кольцевые и некоторые другие списки.

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

На изображении каждый из блоков представляет элемент (узел) списка. Здесь и далее Head list – заголовочный элемент списка (для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки – поле next (далее за ссылки будет отвечать и поле prev). Признаком отсутствия указателя является поле nil.

Односвязный список не самый удобный тип связного списка, т. к. из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Когда кроме указателя на следующий элемент есть указатель на предыдущий, то такой список называется двусвязным.

Та особенность двусвязного списка, что каждый элемент имеет две ссылки: на следующий и на предыдущий элемент, позволяет двигаться как в его конец, так и в начало. Операции добавления и удаления здесь наиболее эффективны, чем в односвязном списке, поскольку всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент. Но добавление и удаление элемента в двусвязном списке, требует изменения большого количества ссылок, чем этого потребовал бы односвязный список.

Возможность двигаться как вперед, так и назад полезна для выполнения некоторых операций, но дополнительные указатели требуют задействования большего количества памяти, чем таковой необходимо в односвязном списке.

Когда количество памяти, по каким-либо причинам, ограничено, тогда альтернативой двусвязному списку может послужить XOR-связный список. Последний использует логическую операцию XOR (исключающее «ИЛИ», строгая дизъюнкция), которая для двух переменных возвращает истину лишь при условии, что истинно только одно из них, а второе, соответственно, ложно. Таблица истинности операции:

В качестве переменных a и b у нас выступают адреса (на следующий и предыдущий элемент), над которыми выполняется операция XOR, возвращающая реальный адрес следующего элемента.

Еще один вид связного списка – кольцевой список. В кольцевом односвязном списке последний элемент ссылается на первый. В случае двусвязного кольцевого списка – плюс к этому первый ссылается на последний. Таким образом, получается зацикленная структура.

Рассмотрим основные операции над связными списками.

Программная реализация списка.

На примере двусвязного списка, разберем принцип работы этой структуры данных. При реализации списка удобно использовать структуры (в Pascal – записи).

Общая форма описания узла двунаправленного связного списка и указателя на первый элемент списка:

struct имя_списка
{
информационное_поле_1;
информационное_поле_2;
…
информационное_поле_n;
указатель_на_следующий_элемент;
указатель_на_предыдущий_элемент;
};
имя_списка *указатель_на_голову_списка;

Пример:

struct DoubleList //описание узла списка
{
int data; //информационное поле
DoubleList *next; //указатель на следующий элемент
DoubleList *prev; //указатель на предыдущий элемент
};
DoubleList *head; //указатель на первый элемент списка

Теперь, предполагая, что описан узел и указатель на голову списка (см. пример выше), напишем функции обработки связного списка.

Добавление элемента.

Опишем функцию AddList, которая в качестве параметров принимает значение и адрес будущего узла, после чего создает его в списке:

void AddList(int value, int position)
{
DoubleList *node=new DoubleList; //создание нового элемента
node->data=value; //присвоение элементу значения
if (head==NULL) //если список пуст
{
node->next=node; //установка указателя next
node->prev=node; //установка указателя prev
head=node; //определяется голова списка
}
else
{
DoubleList *p=head;
for(int i=position; i>1; i--) p=p->next;
p->prev->next=node;
node->prev=p->prev;
node->next=p; //добавление элемента
p->prev=node;
}
cout<<"\nЭлемент добавлен...\n\n";
}

Удаление элемента.

Функция DeleteList для удаления элемента использует его адрес:

int DeleteList(int position)
{
if (head==NULL) { cout<<"\nСписок пуст\n\n"; return 0; }
if (head==head->next) //если это последний элемент в списке
{
delete head; //удаление элемента
head=NULL;
}
else
{
DoubleList *a=head;
for (int i=position; i>1; i--) a=a->next;
if (a==head) head=a->next;
a->prev->next=a->next; //удаление элемента
a->next->prev=a->prev;
delete a;
}
cout<<"\nЭлемент удален...\n\n";
}

Если список пуст, то выводится сообщение, извещающее об этом, и функция возвращается в место вызова.

Вывод списка.

Функция PrintList выводит на экран все элементы списка:

void PrintList()
{
if (head==NULL) cout<<"Список пуст\n";
else
{
DoubleList *a=head;
cout<<"\nЭлементы списка: ";
do
{
cout<<a->data<<" ";
a=a->next;
} while(a!=head); cout<<"\n\n";
}
}

Вывести список можно и посредством цикла, то есть итеративно.

Теперь соединим эти три функции в одной программе. Если в качестве языка использовался бы Pascal, то для функционирования программы (в нашем случае интерфейса двусвязного списка) пришлось, помимо функций (процедур), написать основной блок программы (begin…end), из которого вызывались бы подпрограммы. В C++ этим блоком является функция main. Программа, реализующая простой интерфейс двусвязного списка:

#include "stdafx.h"
#include <iostream>
using namespace std;
struct DoubleList //описание узла списка
{
int data; //информационное поле
DoubleList *next; //указатель на следующий элемент
DoubleList *prev; //указатель на предыдущий элемент
};
DoubleList *head; //указатель на первый элемент списка
//**********************ДОБАВЛЕНИЕ ЭЛЕМЕНТА**********************
void AddList(int value, int position)
{
DoubleList *node=new DoubleList; //создание нового элемента
node->data=value; //присвоение элементу значения
if (head==NULL) //если список пуст
{
node->next=node; //установка указателя next
node->prev=node; //установка указателя prev
head=node; //определяется голова списка
}
else
{
DoubleList *p=head;
for(int i=position; i>1; i--) p=p->next;
p->prev->next=node;
node->prev=p->prev;
node->next=p;
p->prev=node;
}
cout<<"\nЭлемент добавлен...\n\n";
}
//***********************УДАЛЕНИЕ ЭЛЕМЕНТА***********************
int DeleteList(int position)
{
if (head==NULL) { cout<<"\nСписок пуст\n\n"; return 0; }
if (head==head->next)
{
delete head;
head=NULL;
}
else
{
DoubleList *a=head;
for (int i=position; i>1; i--) a=a->next;
if (a==head) head=a->next;
a->prev->next=a->next;
a->next->prev=a->prev;
delete a;
}
cout<<"\nЭлемент удален...\n\n";
}
//*************************ВЫВОД СПИСКА*************************
void PrintList()
{
if (head==NULL) cout<<"\nСписок пуст\n\n";
else
{
DoubleList *a=head;
cout<<"\nЭлементы списка: ";
do
{
cout<<a->data<<" ";
a=a->next;
} while(a!=head); cout<<"\n\n";
}
}
//************************ГЛАВНАЯ ФУНКЦИЯ************************
void main()
{
setlocale(LC_ALL, "Rus");
int value, position, x;
do
{
cout<<"1. Добавить элемент"<<endl;
cout<<"2. Удалить элемент"<<endl;
cout<<"3. Вывести список"<<endl;
cout<<"0. Выйти"<<endl;
cout<<"\nНомер операции > "; cin>>x;
switch (x)
{
case 1:
cout<<"Значение > "; cin>>value;
cout<<"Позиция > "; cin>>position;
AddList(value, position); break;
case 2:
cout<<"Позиция > "; cin>>position;
DeleteList(position); break;
case 3: PrintList(); break;
}
} while (x!=0);
}

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