template<class T>class DLLNode {public:DLLNode() {next = prev = 0;}DLLNode(const T& el, DLLNode<T> *n = 0, DLLNode<T> *p = 0) {info = el; next = n; prev = p;}T info;DLLNode<T> *next, *prev;};
template<class T>class DoublyLinkedList {public:DoublyLinkedList() {head = tail = 0;}void addToDLLTail(const T&);//插入节点到双向链表结尾T deleteFromDLLTail();//删除末尾的节点并返回其值~DoublyLinkedList() {clear();}bool isEmpty() const {return head == 0;}void clear();void setToNull() {head = tail = 0;}void addToDLLHead(const T&);T deleteFromDLLHead();T& firstEl();T* find(const T&) const;protected:DLLNode<T> *head, *tail;friend ostream& operator<<(ostream& out, const DoublyLinkedList<T>& dll) {for (DLLNode<T> *tmp = dll.head; tmp != 0; tmp = tmp->next)out << tmp->info << ‘ ‘;return out;}};
template<class T>void DoublyLinkedList<T>::addToDLLTail(const T& el) {if (tail != 0) {tail = new DLLNode<T>(el,0,tail);tail->prev->next = tail;}else head = tail = new DLLNode<T>(el);}
if (!list.isEmpty())n = list.deleteFromDLLTail();else do not delete;
原文：http://www.cnblogs.com/star91/p/4761752.html