C++双链表模板类

#include <iostream>
using namespace std;

class OutOfBound {};
class IllegalSize {};

template <class elemType>
class list {
public:
    virtual void clear() = 0;
    virtual int length()const = 0;
    virtual void insert(int i, const elemType &x) = 0;
    virtual void remove(int i) = 0;
    virtual int search(const elemType &x)const = 0;
    virtual elemType visit(int i)const = 0;
    virtual void traverse()const = 0;
    virtual ~list() {}
};

template <class elemType>
class linkList :public list<elemType> {
private:
    struct node {
        elemType data;
        node *prev;
        node *next;
        node(const elemType &x, node *p = NULL, node *n = NULL) {
            data = x;
            prev = p;
            next = n;
        }
        node() :next(NULL), prev(NULL) {}
        ~node() {}
    };
    node *head, *tail;
    int currentLength;
    node *move(int i)const {
        node *p = head->next;
        if (i<0 || i>currentLength)
            throw OutOfBound();
        while (i--)
            p = p->next;
        return p;
    }

public:
    linkList(int initSize = 10);
    void clear();
    int length()const { return currentLength; }
    void insert(int i, const elemType &x);
    void remove(int i);
    int search(const elemType &x)const;
    elemType visit(int i)const;
    void traverse()const;
    ~linkList() { 
        clear(); 
        delete head;
        delete tail;
    }
};

template<class elemType>
linkList<elemType>::linkList(int initSize) {
    head = new node;
    head->next = tail = new node;
    tail->prev = head;
    currentLength = 0;
}

template<class elemType>
void linkList<elemType>::clear() {
    node *p = head->next,*q;
    head->next = tail;
    tail->prev = head;
    while (p != tail) {
        q = p->next;
        delete p;
        p = q;
    }
    currentLength = 0;
}

template<class elemType>
void linkList<elemType>::insert(int i, const elemType &x) {
    node *pos, *tmp;
    pos = move(i);
    tmp = new node(x, pos->prev, pos);
    pos->prev->next = tmp;
    pos->prev = tmp;
    ++currentLength;
}

template<class elemType>
void linkList<elemType>::remove(int i) {
    node *pos;
    pos = move(i);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    delete pos;
    --currentLength;
}

template<class elemType>
int linkList<elemType>::search(const elemType &x)const {
    node *tmp = head->next;
    int i = 0;
    while (tmp != tail && tmp->data != x) {
        tmp = tmp->next;
        ++i;
    }
    if (tmp == tail)
        return -1;
    else
        return i;
}

template<class elemType>
elemType linkList<elemType>::visit(int i)const {
    node *tmp = move(i);
    return tmp->data;
}

template<class elemType>
void linkList<elemType>::traverse()const {
    node *tmp = head->next;
    while (tmp != tail) {
        cout << tmp->data << endl;
        tmp = tmp->next;
    }
}

int main() {
    linkList<int> l;
    for (int i = 0; i < 20; ++i)
        l.insert(i, i);
    l.traverse();
    cout << l.visit(10) << endl;
    cout << l.search(10) << endl;
    l.insert(10, 100);
    cout << l.visit(10) << endl;
    l.remove(10);
    cout << l.visit(10) << endl;
    return 0;
}