一. 链表结点类

链表结点类最好是定义为链表类的私有内部类. 不过由于该代码用到了模板, 在VS2013下会遇到各种各样的编译问题, 因此改为定义在外部.

template<class T>struct Node{    T      data;    Node*  prev;    Node*  next;    Node(const T& src = http://www.mamicode.com/T(), Node* p = NULL, Node* n = NULL) :        data(src), prev(p), next(n){}    friend class LinkedList < T > ;};

二. 迭代器类

由于双向链表的遍历, 插入, 删除操作涉及大量的重复的指针操作. 为了提高代码复用性, 我们引入迭代器类.

引入迭代器之后, 就有必要引入两个私有哨兵(sentinel/sentry node)结点: head和tail. 建议写成公共内部类. 但本文中由于VS编译环境对模板的语法要求太苛刻, 只能从权改为外部类

head的作用:

1.便于判断链表的空和满.
2.简化链表操作. 主要是便于取到链表的第一个元素, 无论第一个元素经历多少次更迭. 其次还有便于反向遍历时控制迭代器的终止条件

tail的作用:

1. 便于在尾部插入(这也是双向链表和单向链表的区别之一:单向链表只能在当前结点的后面插入, 双向链表最好在当前结点之前插入)
2. 使用迭代器时, 便于控制正向遍历的终止条件.

template<class T>class iterator<T>{public:    Node<T>*           current;    LinkedList<T>*  host;public:    iterator<T>(Node* c, LinkedList<T>* h) :        current(c), host(h){}    //迭代器的解引用    T& operator* ()    {        return current->data;    }    const T& operator* () const    {        return current->data;    }    //迭代器的移动    //前置++    iterator<T>& operator++()    {        current = current->next;        return *this;    }    //后置++, 出于代码需要, 这里面的后置++并不能真正的移动迭代器, 只是向后peek一下    iterator<T>  operator++(int)    {        auto i = iterator<T>(this->current->next, this->host);        return i;    }    iterator<T>& operator--()    {        current = current->prev;        return *this;    }    // 并不移动, 只是向前peek    iterator<T>  operator--(int)    {        auto i = iterator<T>(this->current->prev, this->host);        return i;    }    //迭代器的比较    bool operator==(const iterator<T>& src) const    {        return (current == src.current && host == src.host);    }    bool operator!=(const iterator<T>& src) const    {        return (current != src.current || host != src.host);    }    friend class LinkedList < T > ;};

三. 链表类ADT

template <class T>class LinkedList{private:    int    sz;    Node<T>*  head;    Node<T>*  tail;    void   init();   //initialize head and tail;public:public:    LinkedList();    LinkedList(const LinkedList& src);    virtual ~LinkedList();    LinkedList& operator= (const LinkedList& src);    iterator<T> begin();    iterator<T> end();    const iterator<T> begin() const;    const iterator<T> end()   const;    int size() const    {        return sz;    }    bool isEmpty() const    {        return sz==0;    }    void clear();    void pushBack(const T& src);    void pushFront(const T& src);    void popBack();    void popFront();    iterator<T> insert (iterator<T> it, const T& src);    iterator<T> remove (iterator<T> it);    iterator<T> remove (iterator<T> from, iterator<T> to);};

四. begin()和end()操作

template <class T>iterator<T> LinkedList<T>::begin(){    return iterator<T>(head->next, this);}template <class T>const iterator<T> LinkedList<T>::begin() const {    return iterator<T>(head->next,this);}template <class T>iterator<T> LinkedList<T>::end(){    return iterator<T>(tail, this);}template <class T>const iterator<T> LinkedList<T>::end() const{    return iterator<T>(tail, this);}

五. 插入

1. 插入指定的迭代器位置

template <class T>iterator<T> LinkedList<T>::insert(iterator<T> it, const T& src){    Node<T>* p = it.current;    ++sz;    /*     * return处是对如下代码的简化     * Node* myPrev = p->prev; //待插入结点的前驱     * Node* myNext = p;       //待插入结点的后继     * Node* myNode = new Node(it, myPrev, myNext); //申请新节点, 并连接前驱和后继     * p->prev->next = myNode; //让前驱,后继和自己连接     * p->prev = myNode;            */    return iterator<T>(p->prev = p->prev->next = new Node(src, p->prev, p), this);    // 最终结果是插入到it的前面.}

2. 插入在头部或尾部

template <class T>void LinkedList<T>::pushBack(const T& src){    insert(end(), src);}template <class T>void LinkedList<T>::pushFront(const T& src){    insert(begin(), src);}

六. 删除结点

1. 删除指定迭代器位置的结点

template <class T>iterator<T> LinkedList<T>::remove(iterator<T> it){    Node<T>* p = it.current;    --sz;    iterator<T> result(p->next, this);    p->prev->next = p->next;    p->next->prev = p->prev;    delete p;    return result;}template <class T>iterator<T> LinkedList<T>::remove(iterator<T> from, iterator<T> to){    if(sz==0) return begin();    for(auto it = from; it!= to; )        it=remove(it);    return to;}

2. 其他删除操作

template <class T>void LinkedList<T>::popBack(){    remove(--end());}template <class T>void LinkedList<T>::popFront(){    remove(begin());}template <class T>void LinkedList<T>::clear(){    remove(begin(), --end());}

七. 内存管理

template <class T>LinkedList<T>::LinkedList(){    init();}template <class T>LinkedList<T>::LinkedList(const LinkedList& src){    init();    *this = src; //call the overloaded operator=}template <class T>LinkedList<T>::~LinkedList(){    clear();    delete head;    delete tail;}template <class T>LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& src){    if (this==&src)    {        return *this;    }    clear();    for (iterator<T> it = src.begin(); it!=src.end(); ++it)    {        this->pushBack(*it);    }    return *this;}template <class T>void LinkedList<T>::init(){    sz = 0;    head = new Node();    tail = new Node();    head->next = tail;    tail->prev = head;}

双向链表

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 双向链表