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

template <class DataT> class listob {
public:
DataT info; //информация
listob<DataT> *next; //указатель на след. объект
listob<DataT> *prior; //указатель на пред. объект
listob() {
info = 0;
next = NULL;
prior = NULL;
};
listob (DataT c) {
info = c;
next = NULL;
prior = NULL;
};
listob<DataT> *getnext() { return next; }
listob<DataT> *getprior() { return prior; }
void getinfo (DataT &c) { c = info; }
void change (DataT c) { info = c; } //изменение элемента
friend ostream &operator<<(ostream &stream,listob<DataT> o);
friend ostream &operator<<(ostream &stream,listob<DataT> *o);
friend istream &operator>>(istream &stream,listob<DataT> &o);
};
// Перегрузка << для объекта listob
template <class DataT>
ostream &operator<<(ostream &stream,listob<DataT> o)
{
stream << o.info << endl;
return stream;
}
// Перегрузка << для указателя на объект типа listob
template <class DataT>
ostream &operator<<(ostream &stream,listob<DataT> *o)
{
stream << o->info << endl;
return stream;
}
// Перегрузка >> для ccылки на объект типа listob
template <class DataT>
istream &operator>>(istream &stream,listob<DataT> &o)
{
cout << «Введите информацию: » ;
stream >> o.info;
return stream;
}

//Класс, реализующий связнный список

template <class DataT> class dllist : public listob<DataT> {
listob<DataT> *start, *end; //*next, *prior
public:
dllist() { start = end = NULL; }
~dllist() ;

void store(DataT c); //ввод нового элемента
void remove(listob<DataT> *ob); //удаление элемента
void frwdlist(); //отображение списка с начала
void bkwdlist(); // отображение списка с конца

listob<DataT> *find(DataT c); //ук. на найденное совпадение
listob<DataT> *getstart() { return start; }
listob<DataT> *getend() { return end; }
};
// Деструктор dllist
template <class DataT> dllist<DataT> :: ~dllist()
{
listob<DataT> *p, *p1;
p = start;
while (p) {
p1 = p->next;
delete p;
p = p1;
}
}

Класс dllist поддерживает целый ряд операций над списком с двойными ссылками:
— ввод нового элемента списка — функция store();
— удаление элемента из списка — функция remove();
— просмотр списка в любом направлении — функции frwdlist() от начала к концу и bkwdlist() от конца к началу
— поиск в списке конкретного элемента — функция find();
— получение указателей на начало и коней списка