C++模板类实现单链表

c++模板类实现单链表

#include<iostream>
using namespace std;
#include<assert.h>
#include<string>
template<class T>
struct  LinkNode
{
    LinkNode<T>* _next;
    T _data;

    LinkNode(const T& x)
        :_data(x)
        ,_next(NULL)
    {}
};

template<class T>
class List
{
    typedef LinkNode<T> Node;
public:
List() //构造函数
        :_head(NULL), _tail(NULL)
    {
    }
List(const List<T>& s) //拷贝构造函数
        :_head(NULL), _tail(NULL)
    {
if (s._head == NULL)
        {
return;
        }
else
        {
            Node *cur(s._head);    //调用尾插的方法
while (cur)
            {
                PushBack(cur->_data);
                cur = cur->_next;
            }
        }
    }
void Swap(List<T>& s) //交换函数
    {
        swap(_head, s._head);
        swap(_tail, s._tail);
    }
List<T>& operator=(List<T> s) //赋值运算符的重载
    {
        Swap(s);
return *this;
    }
    ~List() //析构函数
    {
        clear();
    }
void clear() //清理函数
    {
        Node *cur = _head;
while (cur)
        {
            Node *next = cur->_next;
            delete cur;
            cur = next;
        }
        _head = _tail = NULL;
    }
void Display() //显示函数
    {
        Node *cur = _head;
while (cur)
        {
            cout << cur->_data << " ";
            cur = cur->_next;
        }
        cout << endl;
    }
void PushBack(const T& x) //尾插
    {
if (_head == NULL)
        {
            _head = _tail = new Node(x);
        }
else
        {
            Node* tmp = new Node(x);
            _tail->_next = tmp;
            _tail = tmp;
        }
    }
void PushFront(const T& x) //头插
    {
if (_head == NULL)
        {
            _head = _tail = new Node(x);
        }
else
        {
            Node *tmp = new Node(x);
            tmp->_next = _head;
            _head = tmp;
        }
    }
void PopBack() //尾删
    {
if (_head == NULL)
        {
return;
        }
else if (_head->_next == NULL)
        {
            delete _tail;
            _head = _tail = NULL;
        }
else
        {
            Node*tmp = _head;
while (tmp->_next != _tail)
            {
                tmp = tmp->_next;
            }
            delete _tail;
            _tail = tmp;
            _tail->_next = NULL;
            tmp = NULL;
        }
    }
void PopFront() //头删
    {
if (_head == NULL)
        {
return;
        }
else if (_head->_next == NULL)
        {
            delete _head;
            _head = _tail = NULL;
        }
else
        {
            Node *_del = _head;
            _head = _del->_next;
            delete _del;
            _del = NULL;
        }
    }
    Node* Find(T x) //查找函数
    {
if (_head == NULL)
return NULL;
else
        {
            Node *cur(_head);
while (cur != NULL)
            {
if (cur->_data == x)
                {
                    break;
                }
                cur = cur->_next;
            }
return cur;
        }
    }
void Insert(Node* pos, T x) // 指定元素前插入数据
    {
        assert(pos);
if (pos == _head)
        {
            PushFront(x);
        }
else
        {
            Node *tmp = new Node(x); 
            Node *cur = _head;
while (cur->_next != pos)
            {
                cur = cur->_next;
            }
            tmp->_next = pos;
            cur->_next = tmp;
        }
    }
void Destroy()//销毁单链表
    {
if (_head == NULL)
        {
            _head = _tail = NULL;
        }
else
        {
            Node *cur(_head);
while (cur != NULL)
            {
                cur = cur->_next;
                delete _head;
                _head = cur;
            }
            _head = _tail = NULL;
        }
    }
void Erase(Node* pos) //删除指定元素
    {
        assert(pos);
if (pos == _head)
        {
            _head = _head->_next;
            delete pos;
        }
else
        {
            Node* cur(_head);
while (cur->_next != pos)
            {
                cur = cur->_next;
            }
            cur->_next = pos->_next;
            delete pos;
            pos = NULL;
        }
    }
    Node* Reverse() //单链表的逆置
    {
        Node *pre = _head;
        Node *cur = _head->_next;
        Node *next = NULL;
if (_head == NULL || _head->_next == NULL)
return NULL;
while (cur != NULL)
        {
            next = cur->_next;
            cur->_next = pre;
            pre = cur;
            cur = next;
        }
        _head->_next = NULL;
        _head = pre;
return _head;
    }
protected:
    Node *_head;
    Node *_tail;
};


void test1()//尾插和头插
{
List<int> s1;
    s1.PushBack(3);
    s1.PushBack(4);
    s1.PushFront(2);
    s1.PushFront(1);
    s1.Display();
}
void test2() //尾删和头删
{
List<int> s2;
    s2.PushBack(3);
    s2.PushBack(4);
    s2.PushFront(2);
    s2.PushFront(1);
    s2.PopBack();
    s2.PopBack();
    s2.PopFront();
    s2.PopFront();
    s2.Display();
}
void test3() //指定元素前插入数据和销毁链表
{
List<int> s3;
    s3.PushBack(3);
    s3.PushBack(4);
    s3.PushFront(2);
    s3.PushFront(1);
    s3.Insert(s3.Find(1), 0);
    s3.Display();
    s3.Destroy(); 
    s3.Display();
}
void test4() //拷贝构造
{
List<int> s3;
    s3.PushBack(3);
    s3.PushBack(4);
    s3.PushFront(2);
    s3.PushFront(1);
List<int> s4(s3);
    s4.Display();
}
void test5() //赋值运算符的重载
{
List<int> s3;
    s3.PushBack(3);
    s3.PushBack(4);
    s3.PushFront(2);
    s3.PushFront(1);
List<int> s5 = s3;
    s5.Display();
}
void test6() //测试插入字符串
{
List<string> s6;
    s6.PushBack("abc");
    s6.PushBack("123456789123456789");
    s6.Display();
}
void test7() //单链表指定元素删除
{
List<int> s7;
    s7.PushBack(3);
    s7.PushBack(4);
    s7.PushFront(2);
    s7.PushFront(1);
    s7.Erase(s7.Find(1));
    s7.Display();
}
void test8() //单链表的逆置
{
List<int> s8;
    s8.PushBack(1);
    s8.PushBack(2);
    s8.PushBack(3);
    s8.PushBack(4);
    s8.Reverse();
    s8.Display();
}
int main()
{
//test1();
//test2();
//test3();
//test4();
//test5();
//test6();
//test7();
    test8();
    system("pause");
return 0;
}

需要指出的是这里的类型不是List，而是List。代码均已测试。