双向链表是链表的一个分支，相比单向链表来说多了个一个前向指针 pre，指向当前节点的前一个节点，查找起来更为灵活。
二、链表节点实现
双向链表的节点可以继承单向链表的节点，添加一个 pre 成员即可。两者声明和实现方式都差不多：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
template <typename T> class CDoubleList; template <typename T> class CListNode { public: CListNode() : pre(0), next(0), list(0) {} CListNode(T data, CDoubleList<T>* list = 0, CListNode<T>* pre = 0, CListNode<T>* next = 0) : data(data), list(list), pre(pre), next(next) {} ~CListNode() { // if (next) delete next; pre = 0; next = 0; list = 0; }; CListNode<T> * getPre() const { return pre; } void setPre(CListNode<T> * val) { pre = val; } CListNode<T> * getNext() const { return next; } void setNext(CListNode<T> * val) { next = val; } CDoubleList<T>* getList() const { return list; } void setList(CDoubleList<T>* val) { list = val; } T getData() const { return data; } void setData(T val) { data = val; } private: T data; CListNode<T> * pre; CListNode<T> * next; CDoubleList<T>* list; }; |
二、链表实现
2.1 类声明
双向链表和单链表非常相似，因此没有添加很多操作函数。
在单项链表中，root 节点用来指向第一个节点的地址，在双向链表中依旧可以这么使用，同时还可以使用 root.pre 表示最后一个节点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#pragma once #include "CListNode.h" #include <vector> typedef unsigned int uint; template <typename T> class CDoubleList { public: CDoubleList(); ~CDoubleList(); CListNode<T>* push_back(T data); CListNode<T>* insertAtHead(T data); CListNode<T>* insertAtPre(CListNode<T>* node, T data); CListNode<T>* insertAtSucc(CListNode<T>* node, T data); bool remove(CListNode<T>* node); bool isExist(CListNode<T>* node); uint size() const; // 遍历 std::vector<T> traversal() const; private: CListNode<T>* insert(CListNode<T>* node, T data); // root 和 tail 的 next 指针分别指向 // 第一个节点和最后一个节点 CListNode<T> root; uint len; }; |
2.2 构造和析构
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// 初始化时，`root.pre`和`root.next`都指向空 template <typename T> CDoubleList<T>::CDoubleList() { len = 0; root.setList(this); } // 析构时删除所有的节点 template <typename T> CDoubleList<T>::~CDoubleList() { CListNode<T>* p = root.getNext(), *q; while (p) { q = p->getNext(); delete p; p = q; } root.setNext(0); root.setPre(0); len = 0; } |
2.3 插入节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// 在节点后插入 template<typename T> inline CListNode<T>* CDoubleList<T>::insert(CListNode<T>* node, T data) { if (!isExist(node)) return 0; // 创建新节点插入到指定节点后 CListNode<T> *pNode = new CListNode<T>(data, this, node, node->getNext()); if (!pNode->getNext()) // 如果是在最后插入，更新尾节点 root.setPre(pNode); else // 不是链表结尾插入，更新下一个节点的 pre 指针 node->getNext()->setPre(pNode); node->setNext(pNode); len++; return pNode; } // 插入到末尾 template<typename T> inline CListNode<T>* CDoubleList<T>::push_back(T data) { // 插在尾节点之后 return insertAtSucc(root.getPre() == 0 ? &root : root.getPre(), data); } // 插在链表开头 template<typename T> inline CListNode<T>* CDoubleList<T>::insertAtHead(T data) { return insert(&root, data); } // 作为前驱结点插入 template<typename T> inline CListNode<T>* CDoubleList<T>::insertAtPre(CListNode<T>* node, T data) { if (!isExist(node)) return 0; return insert(node->getPre(), data); } // 作为后继节点插入 template<typename T> inline CListNode<T>* CDoubleList<T>::insertAtSucc(CListNode<T>* node, T data) { return insert(node, data); } |
2.5 删除节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// 移除节点 template<typename T> inline bool CDoubleList<T>::remove(CListNode<T>* node) { if (!isExist(node)) return false; // 更新前驱节点的 next 指针 node->getPre()->setNext(node->getNext()); if (node->getNext()) // 判断是不是最后一个节点 // 不是最后一个节点要更新下一个节点的前驱 node->getNext()->setPre(node->getPre()); else // 如果是最后一个节点，要更新尾节点的指针 root.setPre(node->getPre() == &root ? 0 : node->getPre()); delete node; len--; return true; } |
2.6 其他操作
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// 节点是否存在 template<typename T> inline bool CDoubleList<T>::isExist(CListNode<T>* node) { return this == node->getList(); } template<typename T> inline uint CDoubleList<T>::size() const { return len; } // 遍历链表 template <typename T> inline std::vector<T> CDoubleList<T>::traversal() const { std::vector<T> v; CListNode<T>*p = root.getNext(); while (p) { v.push_back(p->getData()); p = p->getNext(); } return v; } |