首页 > 代码库 > 双向循环链表（C++实现，兼具Boost单元测试）
双向循环链表（C++实现，兼具Boost单元测试）
本文双链表介绍部分参考自博文数组、单链表和双链表介绍 以及 双向链表的C/C++/Java实现。
1 双链表介绍
双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双链表的示意图如下：
表头为空，表头的后继节点为"节点10"(数据为10的节点)；"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的前继节点是"节点10"；"节点20"的后继节点是"节点30"，"节点30"的前继节点是"节点20"；...；末尾节点的后继节点是表头。
1.1 双链表添加节点
在"节点10"与"节点20"之间添加"节点15"
添加之前："节点10"的后继节点为"节点20"，"节点20" 的前继节点为"节点10"。
添加之后："节点10"的后继节点为"节点15"，"节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20"，"节点20" 的前继节点为"节点15"。
对于“添加节点”功能，在具体实现的时候，我们可以分为三种情况（个人觉得这样逻辑比较清晰，当然有些代码是可以合并的。）：
1）在链表第0位置添加。关键代码如下：
1 NodePointer ptr = new Node(), prePtr, postPtr; 2 // assert(ptr != NULL); 3 ptr->data =http://www.mamicode.com/ val; 4 if (pos == 0) // insert node right behind ‘head‘ 5 { 6 postPtr = head->next; 7 head->next = ptr; 8 postPtr->pre = ptr; 9 10 ptr->pre = head;11 ptr->next = postPtr;12 }
2）在链表最后添加结点（即第len位置，其中len为链表原长度）。关键代码如下：
1 ... 2 if (pos == 0) // insert node right behind ‘head‘ 3 { 4 ... 5 } 6 else if (pos == len) // append node 7 { 8 prePtr = head->pre; 9 head->pre = ptr;10 prePtr->next = ptr;11 12 ptr->pre = prePtr;13 ptr->next = head;14 }
3）在链表的中间结点间添加结点。关键代码如下：
1 ... 2 if (pos == 0) // insert node right behind ‘head‘ 3 { 4 ... 5 } 6 else if (pos == len) // append node 7 { 8 ... 9 }10 else // others11 {12 prePtr = head->next;13 int count = 0;14 while (prePtr != head && count < pos - 1)15 {16 prePtr = prePtr->next;17 count++;18 }19 postPtr = prePtr->next;20 21 ptr->next = postPtr;22 ptr->pre = prePtr;23 prePtr->next = ptr;24 postPtr->pre = ptr;25 }
1.2 双链表删除节点
删除"节点30"
删除之前："节点20"的后继节点为"节点30"，"节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40"，"节点40" 的前继节点为"节点30"。
删除之后："节点20"的后继节点为"节点40"，"节点40" 的前继节点为"节点20"。
对于“添加节点”功能，在具体实现的时候，我们可以分为三种情况：
1）删除链表第1个结点。关键代码如下：
1 NodePointer ptr, prePtr, postPtr; 2 if (pos == 0) // delete the first node 3 { 4 ptr = head->next; 5 postPtr = ptr->next; 6 7 head->next = postPtr; 8 postPtr->pre = head; 9 delete ptr;10 }
2）删除链表最后一个结点。关键代码如下：
1 ... 2 if (pos == 0) // delete the first node 3 { 4 ... 5 } 6 else if (pos == len - 1) // delete the last one 7 { 8 ptr = head->pre; 9 prePtr = ptr->pre;10 11 prePtr->next = head;12 head->pre = prePtr;13 delete ptr;14 }
3）删除链表的中间结点。关键代码如下：
1 ... 2 if (pos == 0) // delete the first node 3 { 4 ... 5 } 6 else if (pos == len - 1) // delete the last one 7 { 8 ... 9 }10 else // others11 {12 ptr = head->next;13 int count = 0;14 while (ptr != head && count < pos)15 {16 ptr = ptr->next;17 count++;18 }19 prePtr = ptr->pre;20 postPtr = ptr->next;21 22 prePtr->next = postPtr;23 postPtr->pre = prePtr;24 delete ptr;25 }
2. 代码实现
在这里，我设计的类如下：
1 #ifndef DOUBLELINKEDLIST 2 #define DOUBLELINKEDLIST 3 4 #include <iostream> 5 #include <cassert> 6 using namespace std; 7 8 typedef int ElementType; 9 class Node10 {11 public:12 ElementType data;13 Node * pre;14 Node * next;15 };16 typedef Node * NodePointer;17 18 class LinkedList19 {20 public:21 LinkedList();22 virtual ~LinkedList();23 LinkedList(const LinkedList& orig);24 LinkedList& operator=(const LinkedList& orig);25 bool isEmpty();26 bool addNode(const int pos, const ElementType val);27 bool deleteNode(const int pos);28 void displayNodes();29 NodePointer getNode(const int pos);30 int getLenOfList();31 32 private:33 NodePointer head;34 35 };36 37 #endif
相应的实现代码为：
1 // linkedlist.cpp 2 #include "linkedlist.h" 3 4 LinkedList::LinkedList() 5 { 6 head = new Node(); 7 //assert(head != NULL); 8 head->next = head; 9 head->pre = head; 10 } 11 12 LinkedList::~LinkedList() 13 { 14 NodePointer ptr = head->next, postPtr; 15 while (ptr != head) 16 { 17 postPtr = ptr; 18 ptr = ptr->next; 19 delete postPtr; 20 } 21 delete head; 22 } 23 24 LinkedList::LinkedList(const LinkedList& orig) 25 { 26 // head 初始化这一块不能缺，因为当新声明一个新对象并调用该拷贝构造函数时， 27 // 新对象的head并不会被初始化，也就没有调用默认构造函数。要不会出错，因为 28 // 在其他地方有用到了类似ptr = head->next的语句，如在函数getLenOfList（） 29 // 中，当新对象没有被初始化时，调用该函数就会发生“内存访问错误”。 30 head = new Node(); 31 //assert(head != NULL); 32 head->next = head; 33 head->pre = head; 34 35 NodePointer ptr = orig.head->next; 36 int i = 0; 37 while (ptr != orig.head) 38 { 39 addNode(i, ptr->data); 40 ptr = ptr->next; 41 i++; 42 } 43 44 } 45 46 LinkedList& LinkedList::operator=(const LinkedList& orig) 47 { 48 NodePointer ptr = orig.head->next; 49 int i = 0; 50 while (ptr != orig.head) 51 { 52 addNode(i, ptr->data); 53 ptr = ptr->next; 54 i++; 55 } 56 57 return *this; 58 } 59 60 bool LinkedList::isEmpty() 61 { 62 return head->next == head && head->pre == head; 63 } 64 65 bool LinkedList::addNode(const int pos, const ElementType val) 66 { 67 bool isSuccess = true; 68 int len = getLenOfList(); 69 // assert(0 <= pos <= len); 70 if (pos < 0 || pos > len) 71 { 72 cerr << "The node at position " << pos << " you want to add is less than zero or larger than " 73 << "the length of list ." << endl; 74 isSuccess = false; 75 throw out_of_range("out_of_range"); 76 } 77 else 78 { 79 NodePointer ptr = new Node(), prePtr, postPtr; 80 // assert(ptr != NULL); 81 ptr->data =http://www.mamicode.com/ val; 82 if (pos == 0) // insert node right behind ‘head‘ 83 { 84 postPtr = head->next; 85 head->next = ptr; 86 postPtr->pre = ptr; 87 88 ptr->pre = head; 89 ptr->next = postPtr; 90 } 91 else if (pos == len) // append node 92 { 93 prePtr = head->pre; 94 head->pre = ptr; 95 prePtr->next = ptr; 96 97 ptr->pre = prePtr; 98 ptr->next = head; 99 }100 else // others101 {102 prePtr = head->next;103 int count = 0;104 while (prePtr != head && count < pos - 1)105 {106 prePtr = prePtr->next;107 count++;108 }109 postPtr = prePtr->next;110 111 ptr->next = postPtr;112 ptr->pre = prePtr;113 prePtr->next = ptr;114 postPtr->pre = ptr;115 }116 }117 return isSuccess;118 }119 120 bool LinkedList::deleteNode(const int pos)121 {122 bool isSuccess = true;123 int len = getLenOfList();124 // assert(0 <= pos <= len);125 if (len == 0)126 {127 cerr << "There is no elements in the list." << endl;128 isSuccess = false;129 }130 else131 {132 if (pos < 0 || pos > len - 1)133 {134 cerr << "The node at position " << pos << " you want to delete is out of range." << endl;135 isSuccess = false;136 throw out_of_range("out_of_range");137 }138 else139 {140 NodePointer ptr, prePtr, postPtr;141 if (pos == 0) // delete the first node142 {143 ptr = head->next;144 postPtr = ptr->next;145 146 head->next = postPtr;147 postPtr->pre = head;148 delete ptr;149 }150 else if (pos == len - 1) // delete the last one151 {152 ptr = head->pre;153 prePtr = ptr->pre;154 155 prePtr->next = head;156 head->pre = prePtr;157 delete ptr;158 }159 else // others160 {161 ptr = head->next;162 int count = 0;163 while (ptr != head && count < pos)164 {165 ptr = ptr->next;166 count++;167 }168 prePtr = ptr->pre;169 postPtr = ptr->next;170 171 prePtr->next = postPtr;172 postPtr->pre = prePtr;173 delete ptr;174 }175 }176 }177 178 return isSuccess;179 }180 181 void LinkedList::displayNodes()182 {183 NodePointer ptr = head->next;184 while (ptr != head)185 {186 cout << ptr->data << endl;187 ptr = ptr->next;188 }189 }190 191 NodePointer LinkedList::getNode(const int pos)192 {193 int len = getLenOfList();194 if (len == 0)195 {196 cerr << "There is no element in the list." << endl;197 return NULL;198 }199 else200 {201 // assert(0 <= pos <= len);202 if (pos < 0 || pos > len - 1)203 {204 cerr << "The item at position " << pos << " you want to get is less than zero or "205 << "larger than the length of list." << endl;206 throw out_of_range("out_of_range");207 // return NULL;208 }209 else210 {211 NodePointer ptr = head->next;212 int count = 0;213 while (ptr != head && count < pos)214 {215 ptr = ptr->next;216 count++;217 }218 return ptr;219 }220 }221 }222 223 int LinkedList::getLenOfList()224 {225 NodePointer ptr = head->next;226 int len = 0;227 while (ptr != head)228 {229 ptr = ptr->next;230 len++;231 }232 233 return len;234 235 }
Boost单元测试代码为：
1 #define BOOST_TEST_MODULE LinkedList_Test_Module 2 3 #include "stdafx.h" 4 #include "..\DoubleLinkedList\linkedlist.h" 5 6 struct LinkedList_Fixture 7 { 8 public: 9 LinkedList_Fixture() 10 { 11 testLinkedList = new LinkedList(); 12 } 13 ~LinkedList_Fixture() 14 { 15 delete testLinkedList; 16 } 17 18 LinkedList * testLinkedList; 19 }; 20 21 BOOST_FIXTURE_TEST_SUITE(LinkedList_Test_Suite, LinkedList_Fixture) 22 23 BOOST_AUTO_TEST_CASE(LinkedList_Normal_Test) 24 { 25 // isEmpty -------------------------------------------- 26 BOOST_REQUIRE(testLinkedList->isEmpty() == true); 27 28 // getLenOfList --------------------------------------- 29 BOOST_REQUIRE(testLinkedList->getLenOfList() == 0); 30 31 // addNode & getNode --------------------------------- 32 BOOST_REQUIRE(testLinkedList->addNode(0, 1) == true); 33 BOOST_REQUIRE((testLinkedList->getNode(0))->data =http://www.mamicode.com/= 1); 34 BOOST_REQUIRE((testLinkedList->getNode(0))->pre != NULL); 35 BOOST_REQUIRE((testLinkedList->getNode(0))->next != NULL); 36 BOOST_REQUIRE(testLinkedList->isEmpty() == false); 37 BOOST_REQUIRE(testLinkedList->getLenOfList() == 1); 38 39 BOOST_REQUIRE(testLinkedList->addNode(1, 3) == true); 40 BOOST_REQUIRE((testLinkedList->getNode(1))->data =http://www.mamicode.com/= 3); 41 BOOST_REQUIRE((testLinkedList->getNode(1))->pre != NULL); 42 BOOST_REQUIRE((testLinkedList->getNode(1))->next != NULL); 43 BOOST_REQUIRE(testLinkedList->getLenOfList() == 2); 44 45 BOOST_REQUIRE(testLinkedList->addNode(1, 2) == true); 46 BOOST_REQUIRE((testLinkedList->getNode(1))->data =http://www.mamicode.com/= 2); 47 BOOST_REQUIRE((testLinkedList->getNode(1))->pre != NULL); 48 BOOST_REQUIRE((testLinkedList->getNode(1))->next != NULL); 49 BOOST_REQUIRE(testLinkedList->getLenOfList() == 3); 50 51 // deleteNode ----------------------------------------- 52 BOOST_REQUIRE(testLinkedList->deleteNode(1) == true); 53 BOOST_REQUIRE((testLinkedList->getNode(1))->data =http://www.mamicode.com/= 3); 54 BOOST_REQUIRE((testLinkedList->getNode(1))->pre != NULL); 55 BOOST_REQUIRE((testLinkedList->getNode(1))->next != NULL); 56 BOOST_REQUIRE(testLinkedList->getLenOfList() == 2); 57 58 BOOST_REQUIRE(testLinkedList->deleteNode(1) == true); 59 BOOST_REQUIRE((testLinkedList->getNode(0))->data =http://www.mamicode.com/= 1); 60 BOOST_REQUIRE((testLinkedList->getNode(0))->pre != NULL); 61 BOOST_REQUIRE((testLinkedList->getNode(0))->next != NULL); 62 BOOST_REQUIRE(testLinkedList->getLenOfList() == 1); 63 64 BOOST_REQUIRE(testLinkedList->deleteNode(0) == true); 65 BOOST_REQUIRE(testLinkedList->getLenOfList() == 0); 66 67 } 68 69 BOOST_AUTO_TEST_CASE(LinkedList_Abnormal_Test) 70 { 71 // initialize ------------------------------------------ 72 BOOST_REQUIRE(testLinkedList->addNode(0, 1) == true); 73 BOOST_REQUIRE(testLinkedList->addNode(1, 2) == true); 74 BOOST_REQUIRE(testLinkedList->addNode(2, 3) == true); 75 76 // addNode ------------------------------------------- 77 BOOST_REQUIRE_THROW(testLinkedList->addNode(-1, 100), out_of_range); 78 BOOST_REQUIRE_THROW(testLinkedList->addNode(10, 100), out_of_range); 79 80 // deleteNode ---------------------------------------- 81 BOOST_REQUIRE_THROW(testLinkedList->deleteNode(-1), out_of_range); 82 BOOST_REQUIRE_THROW(testLinkedList->deleteNode(10), out_of_range); 83 84 // getNode -------------------------------------------- 85 BOOST_REQUIRE_THROW(testLinkedList->getNode(-1), out_of_range); 86 BOOST_REQUIRE_THROW(testLinkedList->getNode(10), out_of_range); 87 } 88 89 BOOST_AUTO_TEST_CASE(LinkedList_CopyConstructor_Test) 90 { 91 // initialize ------------------------------------------ 92 BOOST_REQUIRE(testLinkedList->addNode(0, 1) == true); 93 BOOST_REQUIRE(testLinkedList->addNode(1, 2) == true); 94 BOOST_REQUIRE(testLinkedList->addNode(2, 3) == true); 95 96 // check copy constructor ------------------------------ 97 LinkedList * testLinkedList2 = new LinkedList(*testLinkedList); 98 BOOST_REQUIRE(testLinkedList2->isEmpty() == false); 99 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 3);100 BOOST_REQUIRE((testLinkedList2->getNode(0))->data =http://www.mamicode.com/= 1);101 BOOST_REQUIRE((testLinkedList2->getNode(1))->data =http://www.mamicode.com/= 2);102 BOOST_REQUIRE((testLinkedList2->getNode(2))->data =http://www.mamicode.com/= 3);103 104 BOOST_REQUIRE(testLinkedList2->deleteNode(1) == true);105 BOOST_REQUIRE((testLinkedList2->getNode(1))->data =http://www.mamicode.com/= 3);106 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 2);107 108 BOOST_REQUIRE(testLinkedList2->deleteNode(1) == true);109 BOOST_REQUIRE((testLinkedList2->getNode(0))->data =http://www.mamicode.com/= 1);110 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 1);111 112 BOOST_REQUIRE(testLinkedList2->deleteNode(0) == true);113 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 0);114 }115 116 BOOST_AUTO_TEST_CASE(LinkedList_EqualOperator_Test)117 {118 // initialize ------------------------------------------119 BOOST_REQUIRE(testLinkedList->addNode(0, 1) == true);120 BOOST_REQUIRE(testLinkedList->addNode(1, 2) == true);121 BOOST_REQUIRE(testLinkedList->addNode(2, 3) == true);122 123 // check copy constructor ------------------------------124 LinkedList * testLinkedList2 = new LinkedList();125 *testLinkedList2 = *testLinkedList;126 BOOST_REQUIRE(testLinkedList2->isEmpty() == false);127 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 3);128 BOOST_REQUIRE((testLinkedList2->getNode(0))->data =http://www.mamicode.com/= 1);129 BOOST_REQUIRE((testLinkedList2->getNode(1))->data =http://www.mamicode.com/= 2);130 BOOST_REQUIRE((testLinkedList2->getNode(2))->data =http://www.mamicode.com/= 3);131 132 BOOST_REQUIRE(testLinkedList2->deleteNode(1) == true);133 BOOST_REQUIRE((testLinkedList2->getNode(1))->data =http://www.mamicode.com/= 3);134 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 2);135 136 BOOST_REQUIRE(testLinkedList2->deleteNode(1) == true);137 BOOST_REQUIRE((testLinkedList2->getNode(0))->data =http://www.mamicode.com/= 1);138 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 1);139 140 BOOST_REQUIRE(testLinkedList2->deleteNode(0) == true);141 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 0);142 }143 144 BOOST_AUTO_TEST_SUITE_END()
本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.
双向循环链表（C++实现，兼具Boost单元测试）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。