C++ 双向循环链表类模版实例详解

在上章C++图解单向链表类模板和iterator迭代器类模版详解

我们学习了单链表,所以本章来学习双向循环链表

我们在上个文章代码上进行修改, 由于双向循环链表在我们之前学的单链表上相对于较为复杂,所以需要注意的细节如下所示.

1.插入某个节点流程

如下图所示:

对应代码如下所示:

/*插入一个新的节点*/
   bool insert(int i, const T& value)
   {
       if (!((i>=0) && (i<=m_length))) {
           ThrowException("Invalid parameter i to get value ...");
           return false;
       }
       Node* pre = getNode(i-1);
       Node* node = new Node(value);    // new一个新节点
       node->next = pre->next;          // 将node新节点的next链接到下个节点
       node->prev = pre;                // 将node新节点的prev链接到pre上个节点
       pre->next->prev = node;          // 将下个节点的prev链接到node新节点
       pre->next = node;                // 将上个节点的next链接到node新节点
       m_length +=1;
       return true;
   }

2.构造函数修改

在构造函数中,需要将头节点的next和prev都指向自己,从而实现一个闭环状态,代码如下所示:

LinkedList() { m_header.next = &m_header; m_header.prev = &m_header;    m_length = 0; }

3.重新实现append和prepend函数

因为是个双向循环链表,所以我们很轻松的就能获取到表头节点和表尾节点,代码如下所示:

void append(const T &value)
   {
        Node* node = new Node(value);    // new一个新节点
        node->next = &m_header;          // 新节点的下个节点为头节点
        node->prev = m_header.prev;      // 新节点的上个节点为末尾节点
        node->prev->next = node;         // 新节点的上个节点的下个节点为新节点
        m_header.prev = node;            // 开头节点的上个节点为i
        m_length +=1;
   }
   void prepend(const T &value)
   {
       Node* node = new Node(value);    // new一个新节点
       node->next = m_header.next;      // 新节点的下个节点为头节点的next
       node->prev = &m_header;          // 新节点的上个节点为头节点
       m_header.next = node;            // 设置头结点下个节点为node
       node->next->prev = node;         // 设置之前的节点前驱节点
       m_length +=1;
   }

4.修改迭代器类

由于现在是循环双链表,所以每个节点的next都是有值的,所以我们需要判断m_current当前指标是否等于头节点,如果等于则表示已经到链表末尾了.所以代码如下所示:

bool hasNext()  {  return  (m_current && m_current != list->constHeader()); }

由于现在有prev成员,所以需要增加向前遍历函数:

void toEnd() {  m_current = list->constHeader()->prev; }
bool hasPrev()  { return  (m_current && m_current != list->constHeader()); }
T& previous() { Node *ret = m_current;  m_current = m_current->prev; return ret->value; }

5.LinkedList.h代码如下

#ifndef LinkedLIST_H
#define LinkedLIST_H
#include "throw.h"
// throw.h里面定义了一个ThrowException抛异常的宏,如下所示:
//#include <iostream>
//using namespace std;
//#define ThrowException(errMsg)  {cout<<__FILE__<<" LINE"<<__LINE__<<": "<<errMsg<<endl; (throw errMsg);}
/*链表节点类模板*/
template <typename T>
struct LinkedNode
{
   inline LinkedNode(){ }
   inline LinkedNode(const T &arg): value(arg) { }
   LinkedNode *prev;         // 前驱结点
   LinkedNode *next;         // 后驱节点
   T value;                  // 节点值
};
/*链表类模板*/
template <class T>
class LinkedList
{
protected:
   typedef LinkedNode<T> Node;
   mutable Node m_header;          // 头节点
   int m_length;
public:
   LinkedList() { m_header.next = &m_header; m_header.prev = &m_header;    m_length = 0; }
   ~LinkedList() { clear(); }
   int length()  {return m_length;}
   Node* begin() {return m_header.next;}
   inline Node* constHeader() const  { return &m_header; }
   static bool rangeValid(int i,int len)  {return ((i>=0) && (i<len));}
   inline bool isEmpty() const { return m_length == 0; }
   void append(const T &value)
   {
        Node* node = new Node(value);    // new一个新节点
        node->next = &m_header;          // 新节点的下个节点为头节点
        node->prev = m_header.prev;      // 新节点的上个节点为末尾节点
        node->prev->next = node;         // 新节点的上个节点的下个节点为新节点
        m_header.prev = node;            // 开头节点的上个节点为i
        m_length +=1;
   }
   void prepend(const T &value)
   {
       Node* node = new Node(value);    // new一个新节点
       node->next = m_header.next;      // 新节点的下个节点为头节点的next
       node->prev = &m_header;          // 新节点的上个节点为头节点
       m_header.next = node;            // 设置头结点下个节点为node
       node->next->prev = node;         // 设置之前的节点前驱节点
       m_length +=1;
   }
   /*获取i位置处的节点*/
   Node* getNode(int i)
   {
       Node* ret = &m_header;
       while((i--)>-1) {       // 由于有头节点所以,i为0时,其实ret = m_header->n
           ret = ret->next;
       }
       return ret;
   }
   /*插入一个新的节点*/
   bool insert(int i, const T& value)
   {
       if (!((i>=0) && (i<=m_length))) {
           ThrowException("Invalid parameter i to get value ...");
           return false;
       }
       Node* pre = getNode(i-1);
       Node* node = new Node(value);    // new一个新节点
       node->next = pre->next;          // 将node新节点的next链接到下个节点
       node->prev = pre;                // 将node新节点的prev链接到pre上个节点
       pre->next->prev = node;          // 将下个节点的prev链接到node新节点
       pre->next = node;                // 将上个节点的next链接到node新节点
       m_length +=1;
       return true;
   }
   /*删除一个节点*/
   bool remove(int i)
   {
       if (!rangeValid(i, m_length)) {
           ThrowException("Invalid parameter i to get value ...");
           return false;
       }
       Node* pre = getNode(i-1);
       Node* current = pre->next; // 获取要删除的节点
       pre->next = current->next;       // 将上个节点的next链接到前一个的next中
       current->next->prev = pre;       // 将下个节点的prev链接到pre节点
       delete current;                  // delete空闲的节点
       m_length -=1;
       return true;
   }
   /*获取节点数据*/
   T get(int i)
   {
       T ret;
       if (!rangeValid(i, m_length)) {
           ThrowException("Invalid parameter i to get value ...");
       } else {
           ret = getNode(i)->value;
       }
       return ret;
   }
   /*设置节点*/
   bool set(int i, const T& value)
   {
       if (!rangeValid(i, m_length)) {
           ThrowException("Invalid parameter i to get value ...");
           return false;
       }
       getNode(i)->value = value;
       return true;
   }
   void clear()
   {
       while(m_length > 0) {
           remove(0);
       }
   }
   LinkedList<T>& operator << (const T& value)
   {
       append(value);
       return *this;
   }
   /*在链表中向前查找value所在的索引号.默认从from索引号0(表头)开始.如果未找到则返回-1.*/
   int indexOf(const T &value, int from =0)
   {
       int ret = 0;
       Node* node = m_header.next;
       while(node) {
          if (ret >= from && node->value == value) {
              return ret;
          }
          node = node->next;
          ret+=1;
       }
       return -1;
   }
};
/*链表迭代器类模板*/
template <class T>
class LinkedListIterator
{
   typedef LinkedNode<T> Node;
   LinkedList<T> *list;
   Node *m_current;     // 当前指标
public:
   explicit LinkedListIterator(LinkedList<T> &l):list(&l) { m_current = l.begin(); }
   void toBegin() { m_current = list->begin(); }
   void toEnd() {  m_current = list->constHeader()->prev; }
   bool hasHeader()  { return (m_current && m_current == list->constHeader()); }
   bool hasNext()  {  return  (m_current && m_current != list->constHeader()); }
   T& next() { Node *ret = m_current;  m_current = m_current->next; return ret->value; }
   bool hasPrev()  { return  (m_current && m_current != list->constHeader()); }
   T& previous() { Node *ret = m_current;  m_current = m_current->prev; return ret->value; }
   T& value()
   {
       if (m_current == nullptr) {
           ThrowException(" Current value is empty ...");
       }
       return m_current->value;
   }
   T& move(int i)  {
       if (!list->rangeValid(i, list->length())) {
           ThrowException("Invalid parameter i to get value ...");
       }
       m_current = list->getNode(i);
       return value();
   }
};
#endif // LinkedLIST_H

6.测试运行

测试代码如下所示:

LinkedList<int> list;
   for(int i = 0; i< 5; i++)
     list.append(i);
   LinkedListIterator<int> it(list);
   cout<<"list.length:"<<list.length()<<endl;
   // 向后遍历
   it.toBegin();
   while (it.hasNext())
       cout<<"next:"<<it.next()<<endl;
   cout<<endl;
   // 向前遍历
   it.toEnd();                 // 将指标移动到尾结点
   while (it.hasPrev())
       cout<<"previous:"<<it.previous()<<endl;

运行打印:

while循环打印30次,代码如下所示:

it.toBegin();
   int i = 30;
   while(i--) {
       if (it.hasHeader()) it.next();      // 如果到头结点,需要舍弃掉
       cout<<"i:"<<i<<" value:"<<it.next()<<endl;
   }

来源：https://blog.csdn.net/qq_37997682/article/details/123117485