"《算法导论》之‘线性表’"：双向循环链表

　　本文双链表介绍部分参考自博文数组、单链表和双链表介绍 以及 双向链表的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位置添加。关键代码如下：

 NodePointer ptr = new Node(), prePtr, postPtr;
 // assert(ptr != NULL);
 ptr->data = val;
 if (pos == )    // insert node right behind 'head'
 {
     postPtr = head->next;
     head->next = ptr;
     postPtr->pre = ptr;

     ptr->pre = head;
     ptr->next = postPtr;
 }

　　2）在链表最后添加结点（即第len位置，其中len为链表原长度）。关键代码如下：

 ...
 if (pos == )    // insert node right behind 'head'
 {
     ...
 }
 else if (pos == len)    // append node
 {
     prePtr = head->pre;
     head->pre = ptr;
     prePtr->next = ptr;

     ptr->pre = prePtr;
     ptr->next = head;
 }

　　3）在链表的中间结点间添加结点。关键代码如下：

 ...
 if (pos == )    // insert node right behind 'head'
 {
     ...
 }
 else if (pos == len)    // append node
 {
     ...
 }
 else                  // others
 {
     prePtr = head->next;
     int count = ;
     while (prePtr != head && count < pos - )
     {
         prePtr = prePtr->next;
         count++;
     }
     postPtr = prePtr->next;

     ptr->next = postPtr;
     ptr->pre = prePtr;
     prePtr->next = ptr;
     postPtr->pre = ptr;
 }

　  1.2 双链表删除节点

　　

　　删除"节点30"
　　删除之前："节点20"的后继节点为"节点30"，"节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40"，"节点40" 的前继节点为"节点30"。
　　删除之后："节点20"的后继节点为"节点40"，"节点40" 的前继节点为"节点20"。

　　对于“添加节点”功能，在具体实现的时候，我们可以分为三种情况：

　　1）删除链表第1个结点。关键代码如下：

 NodePointer ptr, prePtr, postPtr;
 if (pos == )            // delete the first node
 {
     ptr = head->next;
     postPtr = ptr->next;

     head->next = postPtr;
     postPtr->pre = head;
     delete ptr;
 }

　　2）删除链表最后一个结点。关键代码如下：

 ...
 if (pos == )            // delete the first node
 {
     ...
 }
 else if (pos == len - )    // delete the last one
 {
     ptr = head->pre;
     prePtr = ptr->pre;

     prePtr->next = head;
     head->pre = prePtr;
     delete ptr;
 }

　　3）删除链表的中间结点。关键代码如下：

 ...
 if (pos == )            // delete the first node
 {
     ...
 }
 else if (pos == len - )    // delete the last one
 {
     ...
 }
 else                        // others
 {
     ptr = head->next;
     int count = ;
     while (ptr != head && count < pos)
     {
         ptr = ptr->next;
         count++;
     }
     prePtr = ptr->pre;
     postPtr = ptr->next;

     prePtr->next = postPtr;
     postPtr->pre = prePtr;
     delete ptr;
 }

　 2. 代码实现

　　在这里，我设计的类如下：

 #ifndef DOUBLELINKEDLIST
 #define DOUBLELINKEDLIST

 #include <iostream>
 #include <cassert>
 using namespace std;

 typedef int ElementType;
 class Node
 {
 public:
     ElementType data;
     Node * pre;
     Node * next;
 };
 typedef Node * NodePointer;

 class LinkedList
 {
 public:
     LinkedList();
     virtual ~LinkedList();
     LinkedList(const LinkedList& orig);
     LinkedList& operator=(const LinkedList& orig);
     bool isEmpty();
     bool addNode(const int pos, const ElementType val);
     bool deleteNode(const int pos);
     void displayNodes();
     NodePointer getNode(const int pos);
     int getLenOfList();

 private:
     NodePointer head;

 };

 #endif

　　相应的实现代码为：

 // linkedlist.cpp
 #include "linkedlist.h"

 LinkedList::LinkedList()
 {
     head = new Node();
     //assert(head != NULL);
     head->next = head;
     head->pre = head;
 }

 LinkedList::~LinkedList()
 {
     NodePointer ptr = head->next, postPtr;
     while (ptr != head)
     {
         postPtr = ptr;
         ptr = ptr->next;
         delete postPtr;
     }
     delete head;
 }

 LinkedList::LinkedList(const LinkedList& orig)
 {
     // head 初始化这一块不能缺，因为当新声明一个新对象并调用该拷贝构造函数时，
     // 新对象的head并不会被初始化，也就没有调用默认构造函数。要不会出错，因为
     // 在其他地方有用到了类似ptr = head->next的语句，如在函数getLenOfList（）
     // 中，当新对象没有被初始化时，调用该函数就会发生“内存访问错误”。
     head = new Node();
     //assert(head != NULL);
     head->next = head;
     head->pre = head;

     NodePointer ptr = orig.head->next;
     int i = ;
     while (ptr != orig.head)
     {
         addNode(i, ptr->data);
         ptr = ptr->next;
         i++;
     }

 }

 LinkedList& LinkedList::operator=(const LinkedList& orig)
 {
     NodePointer ptr = orig.head->next;
     int i = ;
     while (ptr != orig.head)
     {
         addNode(i, ptr->data);
         ptr = ptr->next;
         i++;
     }

     return *this;
 }

 bool LinkedList::isEmpty()
 {
     return head->next == head && head->pre == head;
 }

 bool LinkedList::addNode(const int pos, const ElementType val)
 {
     bool isSuccess = true;
     int len = getLenOfList();
     // assert(0 <= pos <= len);
     if (pos <  || pos > len)
     {
         cerr << "The node at position " << pos << " you want to add is less than zero or larger than "
             << "the length of list ." << endl;
         isSuccess = false;
         throw out_of_range("out_of_range");
     }
     else
     {
         NodePointer ptr = new Node(), prePtr, postPtr;
         // assert(ptr != NULL);
         ptr->data = val;
         if (pos == )    // insert node right behind 'head'
         {
             postPtr = head->next;
             head->next = ptr;
             postPtr->pre = ptr;

             ptr->pre = head;
             ptr->next = postPtr;
         }
         else if (pos == len)    // append node
         {
             prePtr = head->pre;
             head->pre = ptr;
             prePtr->next = ptr;

             ptr->pre = prePtr;
             ptr->next = head;
         }
         else                  // others
         {
             prePtr = head->next;
             int count = ;
             while (prePtr != head && count < pos - )
             {
                 prePtr = prePtr->next;
                 count++;
             }
             postPtr = prePtr->next;

             ptr->next = postPtr;
             ptr->pre = prePtr;
             prePtr->next = ptr;
             postPtr->pre = ptr;
         }
     }
     return isSuccess;
 }

 bool LinkedList::deleteNode(const int pos)
 {
     bool isSuccess = true;
     int len = getLenOfList();
     // assert(0 <= pos <= len);
     if (len == )
     {
         cerr << "There is no elements in the list." << endl;
         isSuccess = false;
     }
     else
     {
         if (pos <  || pos > len - )
         {
             cerr << "The node at position " << pos << " you want to delete is out of range." << endl;
             isSuccess = false;
             throw out_of_range("out_of_range");
         }
         else
         {
             NodePointer ptr, prePtr, postPtr;
             if (pos == )            // delete the first node
             {
                 ptr = head->next;
                 postPtr = ptr->next;

                 head->next = postPtr;
                 postPtr->pre = head;
                 delete ptr;
             }
             else if (pos == len - )    // delete the last one
             {
                 ptr = head->pre;
                 prePtr = ptr->pre;

                 prePtr->next = head;
                 head->pre = prePtr;
                 delete ptr;
             }
             else                        // others
             {
                 ptr = head->next;
                 int count = ;
                 while (ptr != head && count < pos)
                 {
                     ptr = ptr->next;
                     count++;
                 }
                 prePtr = ptr->pre;
                 postPtr = ptr->next;

                 prePtr->next = postPtr;
                 postPtr->pre = prePtr;
                 delete ptr;
             }
         }
     }

     return isSuccess;
 }

 void LinkedList::displayNodes()
 {
     NodePointer ptr = head->next;
     while (ptr != head)
     {
         cout << ptr->data << endl;
         ptr = ptr->next;
     }
 }

 NodePointer LinkedList::getNode(const int pos)
 {
     int len = getLenOfList();
     if (len == )
     {
         cerr << "There is no element in the list." << endl;
         return NULL;
     }
     else
     {
         // assert(0 <= pos <= len);
         if (pos <  || pos > len - )
         {
             cerr << "The item at position " << pos << " you want to get is less than zero or "
                 << "larger than the length of list." << endl;
             throw out_of_range("out_of_range");
             // return NULL;
         }
         else
         {
             NodePointer ptr = head->next;
             int count = ;
             while (ptr != head && count < pos)
             {
                 ptr = ptr->next;
                 count++;
             }
             return ptr;
         }
     }
 }

 int LinkedList::getLenOfList()
 {
     NodePointer ptr = head->next;
     int len = ;
     while (ptr != head)
     {
         ptr = ptr->next;
         len++;
     }

     return len;

 }

linkedlist.cpp

　　Boost单元测试代码为：

 #define BOOST_TEST_MODULE LinkedList_Test_Module

 #include "stdafx.h"
 #include "..\DoubleLinkedList\linkedlist.h"

 struct LinkedList_Fixture
 {
 public:
     LinkedList_Fixture()
     {
         testLinkedList = new LinkedList();
     }
     ~LinkedList_Fixture()
     {
         delete testLinkedList;
     }

     LinkedList * testLinkedList;
 };

 BOOST_FIXTURE_TEST_SUITE(LinkedList_Test_Suite, LinkedList_Fixture)

 BOOST_AUTO_TEST_CASE(LinkedList_Normal_Test)
 {
     // isEmpty --------------------------------------------
     BOOST_REQUIRE(testLinkedList->isEmpty() == true);

     // getLenOfList ---------------------------------------
     BOOST_REQUIRE(testLinkedList->getLenOfList() == );

     // addNode & getNode  ---------------------------------
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE((testLinkedList->getNode())->data == );
     BOOST_REQUIRE((testLinkedList->getNode())->pre != NULL);
     BOOST_REQUIRE((testLinkedList->getNode())->next != NULL);
     BOOST_REQUIRE(testLinkedList->isEmpty() == false);
     BOOST_REQUIRE(testLinkedList->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE((testLinkedList->getNode())->data == );
     BOOST_REQUIRE((testLinkedList->getNode())->pre != NULL);
     BOOST_REQUIRE((testLinkedList->getNode())->next != NULL);
     BOOST_REQUIRE(testLinkedList->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE((testLinkedList->getNode())->data == );
     BOOST_REQUIRE((testLinkedList->getNode())->pre != NULL);
     BOOST_REQUIRE((testLinkedList->getNode())->next != NULL);
     BOOST_REQUIRE(testLinkedList->getLenOfList() == );

     // deleteNode -----------------------------------------
     BOOST_REQUIRE(testLinkedList->deleteNode() == true);
     BOOST_REQUIRE((testLinkedList->getNode())->data == );
     BOOST_REQUIRE((testLinkedList->getNode())->pre != NULL);
     BOOST_REQUIRE((testLinkedList->getNode())->next != NULL);
     BOOST_REQUIRE(testLinkedList->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList->deleteNode() == true);
     BOOST_REQUIRE((testLinkedList->getNode())->data == );
     BOOST_REQUIRE((testLinkedList->getNode())->pre != NULL);
     BOOST_REQUIRE((testLinkedList->getNode())->next != NULL);
     BOOST_REQUIRE(testLinkedList->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList->deleteNode() == true);
     BOOST_REQUIRE(testLinkedList->getLenOfList() == );

 }

 BOOST_AUTO_TEST_CASE(LinkedList_Abnormal_Test)
 {
     // initialize ------------------------------------------
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);

     // addNode -------------------------------------------
     BOOST_REQUIRE_THROW(testLinkedList->addNode(-, ), out_of_range);
     BOOST_REQUIRE_THROW(testLinkedList->addNode(, ), out_of_range);

     // deleteNode ----------------------------------------
     BOOST_REQUIRE_THROW(testLinkedList->deleteNode(-), out_of_range);
     BOOST_REQUIRE_THROW(testLinkedList->deleteNode(), out_of_range);

     // getNode --------------------------------------------
     BOOST_REQUIRE_THROW(testLinkedList->getNode(-), out_of_range);
     BOOST_REQUIRE_THROW(testLinkedList->getNode(), out_of_range);
 }

 BOOST_AUTO_TEST_CASE(LinkedList_CopyConstructor_Test)
 {
     // initialize ------------------------------------------
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);

     // check copy constructor ------------------------------
     LinkedList * testLinkedList2 = new LinkedList(*testLinkedList);
     BOOST_REQUIRE(testLinkedList2->isEmpty() == false);
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );

     BOOST_REQUIRE(testLinkedList2->deleteNode() == true);
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList2->deleteNode() == true);
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList2->deleteNode() == true);
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );
 }

 BOOST_AUTO_TEST_CASE(LinkedList_EqualOperator_Test)
 {
     // initialize ------------------------------------------
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
     BOOST_REQUIRE(testLinkedList->addNode(, ) == true);

     // check copy constructor ------------------------------
     LinkedList * testLinkedList2 = new LinkedList();
     *testLinkedList2 = *testLinkedList;
     BOOST_REQUIRE(testLinkedList2->isEmpty() == false);
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );

     BOOST_REQUIRE(testLinkedList2->deleteNode() == true);
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList2->deleteNode() == true);
     BOOST_REQUIRE((testLinkedList2->getNode())->data == );
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );

     BOOST_REQUIRE(testLinkedList2->deleteNode() == true);
     BOOST_REQUIRE(testLinkedList2->getLenOfList() == );
 }

 BOOST_AUTO_TEST_SUITE_END()

BoostUnitTest.cpp

　　本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.