模板实现的链表

堆栈链表看起来简单，真让写，还是有一定困难的。动手用模板实现链表，练练手。

#include<iostream>
using namespace std;

template <class T>
class Node {
public:
    Node(T e, Node *ptr=NULL) : data(e), next(ptr) {};
    T data;
    Node *next;
};

template <class T>
class List {
public:
    List() { head=tail=NULL; };
    ~List();
    bool isEmpty() {return (head == NULL)};                //检查List是否为空

    void addToHead(T);                //插入头节点

    void addToTail(T);                //插入尾节点

    T delFromHead();                //删除头结点

    T delFromTail();                //删除尾节点

    int isInList(T) const;            //查找指定元素是否在List中，有则返回第一次找到匹配的位置(从0开始),没有则返回-1

    void deleteNode(T);                //删除指定元素节点

//private:

    Node<T> *head,*tail;            //模板类用的时候记得这么写 Node

};

template <class T>
List<T>::~List() {            //注意类成员函数定义使用模板时的格式 template List::~List(){...}

    Node<T> *ptr;
    while(head != NULL)        //List不为空

    {
        ptr = head;
        head = head->next;
        delete ptr;
    }
}

template <class T>
void List<T>::addToHead(T data) {
    head = new Node<T>(data, head);
    if (tail == NULL)        //原来List为空的话，tail和head都指到该节点上

        tail = head;
}

template <class T>
void List<T>::addToTail(T data) {
    if (tail == NULL)
        head = tail = new Node<T>(data);
    else        //原来List不空，加到末尾

    {
        tail->next = new Node<T>(data);
        tail = tail->next;
    }
}

template <class T>
T List<T>::delFromHead() {
    if(head == NULL)        //List为空

    {
        cerr << "List is empty! Fail to delete from head." << endl;
        exit(1);
    }
    T e = head->data;
    Node<T> *ptr = head;
    if(head == tail)        //只有一个节点

        head = tail = NULL;
    else                    //不只一个节点

        head = head->next;

    delete ptr;        //释放内存

    return e;
}

template <class T>
T List<T>::delFromTail() {
    if(tail == NULL)        //List为空

    {
        cerr << "List is empty! Fail to delete from tail." << endl;
        exit(1);
    }
    T e = tail->data;
    Node<T> *ptr;
    if(tail == head)        //只有一个节点

    {
        ptr = tail;
        tail = head = NULL;
        delete ptr;            //释放内存

    }
    else                    //不止一个节点

    {
        ptr = head;
        while(ptr->next != tail)        //使ptr->next == tail;

            ptr = ptr->next;
        delete tail;
        tail = ptr;
        tail->next = NULL;            //这步不要忘了，使tail->next = NULL;

    }
    return e;
}

template <class T>
int List<T>::isInList(T data) const{        //const函数体在声明和定义时都要写明const

    Node<T> *ptr = head;
    for(int index = 0; ptr->next != NULL; index++) {
        if(ptr->data == data)
            return index;
    }
    return -1;        //没有找到返回-1

}

template <class T>
void List<T>::deleteNode(T data) {
    if (head == NULL)            //检查List是否为空

    {
        cerr << "List is empty." << endl;
        return;
    }
    else if (head == tail)            //只有一个节点

    {
        if (data == head->data) {        //如果data == head->data

            delete head;
            head = tail = NULL;
        }
        else {
            cerr << "Data is no found." << endl;
            return;
        }
    }
    else                //有多个节点

    {
        if (data == head->data) {        //如果data == head->data

            Node<T> *ptr = head;
            head = head->next;
            delete ptr;
        }
        else {
            Node<T> *ptr,*pre;
            for(pre=head, ptr=head->next; (data!=ptr->data) && (ptr!=NULL); pre=ptr, ptr=ptr->next) ;        //别忘了分号

                if(ptr!=NULL)        //找到节点,删除

                {
                    pre->next = ptr->next;
                    if (ptr == tail)        //如果找到的节点是尾节点，则记得要重设尾节点

                        tail = pre;
                    delete ptr;
                }
                else            //没有找到节点

                    cerr << "Data is no found." << endl;
        }
    }
}

void main()
{
    List<int> list;
    list.addToHead(1);
    list.addToHead(2);
    list.addToHead(3);
    list.addToHead(4);
    list.addToHead(5);
    list.delFromHead();
    list.deleteNode(3);
    list.delFromTail();
    Node<int> *p = list.head;
    while(p!=NULL)
    {
        cout << p->data << ' ';
        p = p->next;
    }
}