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;