双向链表VS2008编译实现

DoubleList.h

#ifndef  DOUBLELIST_H
#define DOUBLELIST_H
#include <iostream>
using std::cout;
using std::endl;
using std::ostream;

template <typename T>
class DoubleList;

template <typename T>
ostream & operator << (ostream & out, const DoubleList<T> & dl);
template<class T>
class DoubleNode{
    friend DoubleList<T>;
private:
    T data;
    DoubleNode<T> *left,*right;
};

template<class T>
class DoubleList{
    friend ostream & operator << <T> (ostream & out, const DoubleList<T> & dl);
public:
    DoubleList() {LeftEnd = RightEnd = 0;}
    ~DoubleList();
    int Length() const;
    bool IsEmpty() const {return LeftEnd == 0;}
    bool Find(int k, T & x) const;
    int Search(const T & x) const;
    DoubleList<T> & Delete(int k,const T & x);
    DoubleList<T> & Insert(int k, const T & x);
    void Output(ostream & out) const;
private:
    DoubleNode<T> *LeftEnd,*RightEnd;
};

template<typename T>
DoubleList<T>::~DoubleList()
{
    DoubleNode<T> *next;
    while(LeftEnd)
    {
        next = LeftEnd->right;
        delete LeftEnd;
        LeftEnd = next;
    }
    /*可替换部分
    while(RightEnd)
    {
        next = RightEnd->left;
        delete RightEnd;
        RightEnd = next;
    }
    */
}

template<typename T>
int DoubleList<T>::Length() const
{
    DoubleNode<T> * current = LeftEnd;
    int len = 0;
    while (current)
    {
        len++;
        current = current->right;
    }
    /*可替换部分
    DoubleNode<T> * current = RightEnd;
    int len = 0;
    while(current)
    {
        len++;
        current = current->left;
    }
    */
    return len;
}

template<typename T>
bool DoubleList<T>::Find(int k, T & x) const
{//找出第k个节点值，返回给x
    if (k<0) return false;
    DoubleNode<T> *current = LeftEnd;
    int index = 0;
    while (index < k && current)
    {
        current = current->right;
        index++;
    }
    if (current)
    {
        x = current->data;
        return true;
    }
    return false;
}

template <typename T>
int DoubleList<T>::Search(const T & x) const
{
    DoubleNode<T> * current = LeftEnd;
    int index = 0;
    while (current && current->data != x)
    {
        current = current->right;
        index++;
    }

    /*
    DoubleNode<T> * current = RightEnd;
    int index 0;
    while (current && current->data != x)
    {
        current = current->left;
        index++;
    }
    */
    if(current) return index;
    return -1;
}

template <typename T>
void DoubleList<T>::Output(ostream & out) const
{
    DoubleNode<T> * current;
    for (current = LeftEnd; current;current = current->right)
        out << current->data<<" ";
    /*for (current= RightEnd; current;current = current->left)
        out<< current->data<<" ";*/
}

template <typename T>
ostream & operator << (ostream & out, const DoubleList<T> & dl)
{
    dl.Output(out);
    return out;
}

template <typename T>
DoubleList<T> & DoubleList<T>::Delete(int k, const T & x)
{
    if (k < 0 || !LeftEnd)
        cout<<"OutOfBounds"<<endl;
    DoubleNode<T> * p = LeftEnd;
    if(k == 0)
        LeftEnd = LeftEnd->right;
    else
    {
        DoubleNode<T> * q = LeftEnd;
        for (int index = 0; index < k-1 && q; index++)
            q = q->right;
        if (!q || !q->right)
        {
            cout<<"OutOfBounds"<<endl;
        }
        p= q->right;
        q->right = p->right;
        if (!p->right)
            RightEnd = q;
        else
            p->right->left = q;
    }
    x = p->data;
    delete p;
    return *this;
}

template <typename T>
DoubleList<T> & DoubleList<T>::Insert(int k, const T & x)
{
    if (k < 0)
        cout<<"OutOfBounds"<<endl;
    DoubleNode<T> * p = LeftEnd;

    for (int index = 0; index < k && p; index++)
        p = p->right;

    if (k > 0 && !p)
        cout<<"OutOfBounds"<<endl;
    DoubleNode<T> * y = new DoubleNode<T>;
    y->data = x;
    if (k)
    {
        y->right = p->right;
        p->right->left = y;
        p->right = y;
        y->left = p;
        if (!( y->right))
            RightEnd = y;
    }
    else
    {
        y->right = LeftEnd;
        LeftEnd = y;
    }
    return *this;
}

#endif

main.cpp

#include <iostream>
#include "DoubleList.h"

using namespace std;

int  main()
{
    DoubleList<int> bob;
    cout<<bob.IsEmpty()<<endl;
    cout<<bob.Length()<<endl;
    bob.Insert(0,33);
    bob.Insert(0,22);
    cout<<bob.Length()<<endl;
    cout<<bob<<endl;
    return 0;
}