Class Node

{

public:

Data d;

Node* next;

Node* prev;

Node (Data dat = 0)

{

d = dat; next = 0; prev = 0;

}

};

Node* pbeg,*pend;

public:

List(){pbeg = 0;pend=0;}

~List();

void add(Data d);

Node* find(Data i);

bool remove (Data key);

Node* insert(Data key, Data d);

void print();

void print_back();

};

template <class Data>

List<Data>::~List()

{

if(pbeg!=0)

{

Node* pv = pbeg;

while(pv)

{

pv = pv->next;

delete pbeg;

pbeg = pv;

}

}

}

template <class Data>

void List<Data>::print()

{

Node* pv = pbeg;

cout << char(10) << " list ";

while(pv)

{

cout << pv->d << " ";

pv = pv->next;

}

cout << char(10);

}

template <class Data>

void List<Data>::print_back()

{

Node* pv = pend;

cout << char(10) << " list back ";

while(pv)

{

cout << pv->d << " ";

pv = pv->prev;

}

cout << char(10);

}

template <class Data>

void List<Data>::add(Data d)

{

Node* pv = new Node(d);

if(pbeg == 0)pbeg = pend = pv;

else

{

pv->prev = pend;

pend->next = pv;

pend = pv;

}

}

template <class Data>

typename List<Data>:: Node*

List<Data>::insert(Data key, Data d)

{

if(Node*pkey = find(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;

}

template <class Data>

typename List<Data>::Node*

List<Data>::find(Data d)

{

Node *pv = pbeg;

while(pv)

{

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

pv = pv->next;

}

return pv;

}

template <class Data>

bool List<Data>::remove(Data key)

{

if(Node*pkey = find(key))

{

if (pkey == pbeg)

{

pbeg = pbeg->next;

pbeg->prev = 0;

}

else if (pkey == pend)

{

pend = pend->prev;

pbeg->next = 0;

}

else

{

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

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

}

delete pkey;

return true;

}

return false;

}