Class Node

{…

};

Node *pbeg, *pend; // Указатели на начало и конец списка

public:

List(){pbeg = 0; pend =0;} //Конструктор

~List (); // Деструктор

void add(int d); // Добавление узла в конец списка

Node * find(int i); // Поиск узла по ключу

// Вставка узла d после узла с ключом key:

Node * insert(int key, int d);

bool remove(int key): // Удаление узла

void print(); // Печать списка в прямом направлении

void print_back(); // Печать списка в обратном направлении

};

Рассмотрим реализацию методов класса. Метод add выделяет память под новый объект типа Node и присоединяет его к списку, обновляя указатели на его начало

и конец:

void List::add(int d){

Node *pv = new Node(d); // Выделение памяти под новый узел

if (pbeg == 0)pbeg = pend = pv; // Первый узел списка

else{

// Связывание нового узла с предыдущим:

pv->prev = pend;

pend->next = pv;

pend = pv;

} // Обновление указателя на конец списка

}

При желании получить отсортированный список этот метод можно заменить.

Метод find выполняет поиск узла с заданным ключом и возвращает указатель на него в случае успешного поиска и 0 в случае отсутствия такого узла в списке:

Node * List::find(int d){

Node *pv = pbeg;

while (pv){

if(pv->d == d) break;

pv = pv->next;

}

return pv;}

Метод insert вставляет в список узел после узла с ключом key и возвращает указатель на вставленный узел. Если такого узла в списке нет, вставка не выполняется и возвращается значение 0:

Node * List::insert(int key, int d){

if(Node *pkey = find(key))

{ // Поиск узла с ключом key

/ / Выделение памяти под новый узел и его инициализация:

Node *pv = new Node(d);

/ / Установление связи нового узла с последующим:

pv->next = pkey->next;

/ / Установление связи нового узла с предыдущим:

pv->prev = ркеу;

/ / Установление связи предыдущего узла с новым:

pkey->next = pv;

/ / Установление связи последующего узла с новым:

i f (ркеу!= pend) (pv->next)->prev = pv;

/ / Обновление указателя на конец списка.

/ / если узел вставляется в конец:

else pend = pv;

return pv;

}

return 0;

}

Метод remove удаляет узел с заданным ключом из списка и возвращает значение true в случае успешного удаления и false, если узел с таким ключом в списке не найден:

bool List::remove(int key){

if(Node *pkey = find(key))

{

if (pkey == pbeg){ // Удаление из начала списка

pbeg = pbeg->next;

pbeg->prev = 0;}

else if (pkey == pend){ // Удаление из конца списка

pend = pend->prev;

pend->next - 0;}

else { //Удаление из середины списка

(pkey->prev)->next = pkey->next;

(pkey->next)->prev = pkey->prev;}

delete pkey;

return true;

}

return false;

}

Методы печати списка в прямом и обратном направлении поэлементно просматривают список, переходя по соответствующим ссылкам:

void List:: print (){

Node *pv = pbeg;

cout << endl << "list: ";

while (pv){

cout << pv->d << ' ';

pv = pv->next;

}

cout << endl;

}

void List::print_back(){

Node *pv = pend;

cout << endl << " list back: ";

while (pv){

cout << pv->d << ' ';

pv = pv->prev;

}

cout << endl:

}

Деструктор списка освобождает память из-под всех его элементов:

List:: ~List () {

i f (pbeg!= 0){

Node *pv = pbeg;

while (pv){

pv = pv->next:

delete pbeg;

pbeg = pv;}

}

}

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

int main(){

List L;

for (int i = 2; i<6; i++) L.add(i):