双向链表(Dlist) 用模板实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stdlib.h>
using namespace std;
template<typename T>
 struct Node
 {

     Node(const T& d)
        : _next(NULL)
        , _prev(NULL)
        , _data(d)
     {}
    Node<T>*  _next;
    Node<T>*  _prev;
    T _data;
 };
 template<typename T>
 class Dlist
 {
 public:
     Dlist()
         :_head(NULL)
         ,_tail(NULL)
     {}

     ~Dlist()
     {
        Node<T>* cur = _head;
        while(cur)
        {
            Node<T>* del = cur;
            cur=cur->_next;
            delete del;
            del = NULL;
        }    
     }
 public:
     void PushBack(const T& d);
     void PushFront(const T& d);
     void PopBack();
     void PopFront();
     void Reverse();
     void Print()
     {
         Node<T>* cur = _head;
         while(cur)
         {
            cout<<cur->_data <<"<=> ";
            cur=cur->_next;
         }
         cout<<"over"<<endl;     
     }
 private:
     Node<T>* _head;
     Node<T>* _tail;
 };
template<typename T>
void  Dlist<T>::PushBack(const T& d)
{
    Node<T>* newNode = new Node<T>(d);
    if(_head == NULL)
    {
        _head = newNode;
        _tail = _head;
    }
    else
    {
        _tail->_next = newNode;
        newNode->_prev = _tail;
        _tail =newNode;
    }
}
template<typename T>
void Dlist<T>::PushFront(const T& d)
{
    Node<T>* newNode = new Node <T>(d);
    if(_head == NULL)
    {
        _head = newNode;
        _tail = _head;
    }
    else
    {
        newNode->_next = _head;
        _head = newNode;
    }
}
template<typename T>
void Dlist<T>::PopBack()
{
    if(_head == NULL)
        return;
    else if(_head->_next == NULL)
    {
        delete _head;
        _head = NULL;
        _tail = NULL;
    }
    else
    {
        _tail=_tail->_prev ;
        delete _tail ->_next ;
        _tail->_next = NULL;
    }
}
template<typename T>
void Dlist<T>::PopFront()
{
    if(_head == NULL)
        return;
    else if(_head->_next==NULL)
    {
    delete _head;
    _head=NULL;
    _tail=NULL;
    }
    else
    {
    Node<T>* del = _head;
    _head = _head->_next ;
    delete del;
    del = NULL;
    }
}
template<typename T>
void Dlist<T>::Reverse()
{
        Node<T>* cur = _head;
        Node<T>* prev = NULL;
        Node<T>* pnewhead=NULL;
        while(cur)
        {
          prev = cur;
          cur = cur->_next;
          prev->_next = pnewhead;
          pnewhead = prev;
        }
        _head = pnewhead;    
}

int main()
{
    Dlist<int> s1;
    s1.PushBack(1);
    s1.PopFront();
    s1.Print ();
    s1.PushBack(2);
    s1.PushBack(3);
    s1.PushBack(4);
    s1.Print ();
    s1.Reverse ();
    s1.Print ();
    s1.PushFront (2);
    s1.Print ();
    s1.PopBack();
    s1.Print ();
    s1.PopFront();
    s1.Print ();
    s1.PopFront ();
    s1.Print ();
    system("pause");
    return 0;
}

运行结果如下：

双向链表(Dlist) 用模板实现

原文：http://10798301.blog.51cto.com/10788301/1757187