双线链表

双向链表的特点：
1、以节点为单位，每个节点有上个节点指针和下个节点指针
2、至少包含头节点和尾节点
3、添加节点时先改变新增节点的上下节点指针指向，后修改前后节点的指针指向为当前节点
4、删除节点时修改当前节点的前后节点指向，然后删除当前节点
5、迭代器用来封装节点数据，并提供了操作符的能力，如*，++，==，!=
6、列表的操作有：取头，取尾，删头，删尾，删指定位置，加头，加尾，加指定位置

template <class Object>
class List
{
private:
    struct Node
    {
        Object data;
        Node *prev;
        Node *next;
 
        Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL)
            : data(d), prev(p), next(n)
        {
 
        }
    };
 
public:
    class const_iterator
    {
    public:
        const_iterator() : current(NULL)
        {
 
        }
 
        const Object &operator* () const
        {
            return retrieve();
        }
 
        const_iterator & operator++ ()
        {
            current = current->next;
            return *this;
        }
 
        const_iterator operator++ (int)
        {
            const_iterator old = *this;
            ++(*this);
            return old;
        }
 
        bool operator == (const const_iterator &rhs) const
        {
            return current == rhs.current;
        }
 
        bool operator != (const const_iterator &rhs) const
        {
            return !(*this == rhs);
        }
 
    protected:
        Node *current;
        Object &retrieve() const
        {
            return current->data;
        }
        const_iterator(Node *p) : current(p)
        {
 
        }
 
        friend class List < Object >;
    };
 
    class iterator : public const_iterator
    {
    public:
        iterator()
        {
 
        }
 
        Object & operator* ()
        {
            return retrieve();
        }
 
        iterator &operator++()
        {
            current = current->next;
            return *this;
        }
 
        iterator operator++ (int)
        {
            iterator old = *this;
            ++(*this);
            return old;
        }
 
    protected:
        iterator(Node *p) : const_iterator(p)
        {
 
        }
 
        friend class List < Object >;
    };
 
public:
    List()
    {
        init();
    }
    ~List()
    {
        clear();
        delete head;
        delete tail;
    }
    List(const List &rhs)
    {
        init();
        *this = rhs;
    }
 
    const List &operator = (const List &rhs)
    {
        if (this == &rhs)
        {
            return *this;
        }
        clear();
        for (const_iterator itr = rhs.begin(); itr != rhs.end(); ++itr)
        {
            push_back(*itr);
        }
 
        return *this;
    }
 
    iterator begin()
    {
        return iterator(head->next);
    }
 
    const_iterator begin() const
    {
        return const_iterator(head->next);
    }
 
    iterator end()
    {
        return iterator(tail);
    }
 
    const_iterator end() const
    {
        return const_iterator(tail);
    }
 
    int size() const
    {
        return theSize;
    }
    bool empty() const
    {
        return size() == 0;
    }
 
    void clear()
    {
        while (!empty())
            pop_front();
    }
 
    Object &front()
    {
        return *begin();
    }
 
    const Object & front() const
    {
        return *begin();
    }
    Object &back()
    {
        return *--end();
    }
    const Object &back() const
    {
        return *--end();
    }
    void push_front(const Object &x)
    {
        insert(begin(), x);
    }
    void push_back(const Object &x)
    {
        insert(end(), x);
    }
    void pop_front()
    {
        erase(begin());
    }
    void pop_back()
    {
        erase(--end());
    }
 
    iterator insert(iterator itr, const Object &x)
    {
        Node *p = itr.current;
        theSize++;
        return iterator(p->prev = p->prev->next = new Node(x, p->prev, p));
    }
    iterator erase(iterator itr)
    {
        Node *p = itr.current;
        iterator retVal(p->next);
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;
 
        return retVal;
    }
 
    iterator erase(iterator start, iterator end)
    {
        for (iterator itr = start; itr != end;)
        {
            itr = erase(itr);
        }
 
        return end;
    }
 
private:
    int theSize;
    Node *head;
    Node *tail;
    void init()
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }
};
 
int main()
{
    List<int> nList;
    nList.push_back(1);
    nList.push_back(2);
    nList.push_back(3);
    nList.push_back(4);
    for (List<int>::const_iterator itr = nList.begin(); itr != nList.end(); itr++)
    {
        LOG_INFO("itr vaule:" << *itr);
    }
 
    //
    for (List<int>::iterator itr = nList.begin(); itr != nList.end(); )
    {
        nList.erase(itr++);
    }
 
    LOG_INFO("List size:" << nList.size());
    reutrn 0;
}

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-06-12