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

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

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

Node * insert(int key, int d):

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

void printO: // Печать списка в прямом направлении

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:} // Обновление указателя на конец списка

}

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

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

Node * List::find( int d ){

Node *pv = pbeg:

Глава 6. Шаблоны классов

213

while (pv){

if(pv->d ^=ss d)break: pv « pv->next;

}

return pv;

}

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

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

if(Node *pkey ^e find(key)){ // Поиск узла с ключом key // Выделение памяти под новый узел и его инициализация: Node *pv = new Node(d);

// Установление связи нового узла с последующим: pv->next - pkey->next;

// Установление связи нового узла с предыдущим: pv->prev = pkey;

// Установление связи предыдущего узла с новым: pkey->next = pv;

// Установление связи последующего узла с новым: if( pkey !« 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 { II Удаление из середины списка

(pkey->prev)->next - pkey->next; (pkey->next)->prev = pkey->prev;} delete pkey; return true;} return false; }

214

Часть II. Объектно-ориентированное программирование

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

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::4ist(){ if (pbeg != 0){ Node *pv = pbeg: while (pv){

pv = pv->next: delete pbeg: pbeg = pv:} } } Ниже приведен пример программы, использующей класс List. Программа аналогична приведенной на с. 116: она формирует список из 5 чисел, выводит его на экран, добавляет число в список, удаляет число из списка и снова выводит его на экран:

int'main(){

List L:

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

L.printO:

L.print_back():

L.insert(2, 200):

if (!L.remove(5))cout « "not found":

L.printO:

L.print__back(): } Класс Li st предназначен для хранения целых чисел. Чтобы хранить в нем данные любого типа, требуется описать этот класс как шаблон и передать тип в качестве параметра.