链表结点类最好是定义为链表类的私有内部类. 不过由于该代码用到了模板, 在VS2013下会遇到各种各样的编译问题, 因此改为定义在外部.
template<class T> struct Node { T data; Node* prev; Node* next; Node(const T& src = 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 > ; };
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); };
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; }
原文：http://www.cnblogs.com/roy-mustango/p/4224846.html