线性表--带有头节点的双向循环链表C++语言描述，实现链表的基本操作以及拷贝控制

链表描述的基本知识和单向链表的描述见线性表–单向链表。
使用头节点的循环链表可以使得链表的一些操作程序更加简洁，运行速度更快。例如我们的index_of操作，就可以将要查找的元素放入头节点的数据域，在循环条件中仅仅需要判断while(currentNode->element!=_given_element)一个表达式，不需要像前面我们实现的未带有头节点的单向链表一样进行两个表达式的判别while(currentNode!=nullptr && currentNode->element!=_given_element)，因为在头节点链表中我们可以肯定即使链表中没有需要查找的元素 _given_element我们也能停止循环(当遍历到头节点时循环终止)。
使用双向链表则可以降低链表基本操作的时间复杂度。比如insert/get/erase操作，当用户给出的索引小于size/2时，就可以直接从链表的左边进行遍历，反之则从右边进行遍历(需要注意的是，我们实现的链表的插入操作是在索引处前插，而删除操作是直接删除给定索引节点，也就是说要插入的节点的后继节点实际就是索引处的节点，而要删除的节点的后继节点实际是索引处节点的后一个节点，因此从右边开始遍历的情况下，为了找出给定索引的节点的后继节点，插入操作的循环步数要比删除操作多一步)。
也因此相较于单链表，我们需要更多地考虑对头节点以及增删节点的相邻节点的指针维护。
与单链表一样，在拷贝控制时尤其需要注意对原有链表元素的内存资源的释放，避免直接拷贝指针导致内存泄漏或者二次delete。

自定义的异常类
illegalParameterValue.h

#pragma once
//========================自定义的参数异常类==========================
#include <iostream>
#include <string>
using std::cout; using std::cin; using std::ends; using std::endl; using std::cerr;
using std::string;
class illegalParameterValue {
public:
	illegalParameterValue(const string& _message="Illegal parameter value!") :message(_message) { }
	string what() const { return message; }
	void output()const { cout << message << endl; }
private:
	string message;
};

需要实现线性表抽象数据类(ADT)的接口
myLinearList.h

#pragma once
//========================线性表的抽象描述========================
template <typename T>
class myLinearList {
public:
	virtual ~myLinearList() { }
	virtual bool empty()const = 0;//是否为空线性表
	virtual size_t get_size()const = 0;//返回线性表的元素个数
	virtual T& get_element(size_t index)const = 0;//返回索引处的元素值
	virtual size_t index_of(const T& element)const = 0;//返回该元素第一次出现的索引
	virtual void insert(const T&, size_t index) = 0;//在指定索引处位置插入元素
	virtual void erase(size_t index) = 0;//删除指定索引位置的元素
	virtual void output(std::ostream& os = cout) const = 0;//遍历输出线性表
};

对上述抽象类的扩展
myExtendedLinearList.h

#pragma once
//========================拓展的线性表的抽象类========================
#include "myLinearList.h"
//增加几个接口 实现这个抽象类的extendedChain类需要改进erase和insert代码
template <typename T>
class myExtendedLinearList : public myLinearList<T> {
public:
	virtual ~myExtendedLinearList() { }
	virtual void clear() = 0;
	virtual void push_back(const T& element) = 0;//将元素element插入到表尾
};

双向节点

#pragma once
template <typename T>
struct myBidirNode{
	//同时具有前驱节点、后继节点
	myBidirNode<T>* prev;
	myBidirNode<T>* next;
	T element;

	myBidirNode() = default;
	//构造节点时 要么传入一个数据域的元素构造一个悬空的节点(prev/next都为空)
	//要么同时传入数据域的元素和指针域的两个节点指针
	myBidirNode(const T& _element):element(_element),prev(nullptr),next(nullptr){ }
	myBidirNode(const T& _element,myBidirNode<T>* _prev,myBidirNode<T>* _next)
		:element(_element),prev(_prev),next(_next){ }
};

用于双向循环链表的自定义双向迭代器类

#pragma once
#include "myBidirNode.h"
template <typename T>
class myBidirIteraotr {
public:
	//公有成员
	typedef std::bidirectional_iterator_tag iterator_category;//迭代器类型标签
	typedef T value_type;//值类型
	typedef std::ptrdiff_t difference_type;//标识迭代器之间的距离 C++17 弃用
	typedef T* pointer;//指向被迭代的类型(T)的指针
	typedef T& reference;//被迭代类型(T)的引用
	//构造函数
	myBidirIteraotr(myBidirNode<T>* _ptr=nullptr) :node_ptr(_ptr) { }
	//解引用操作
	T operator*() const { return node_ptr->element; }
	T* operator->() const { return &(node_ptr->element); }
	//递增递减
	myBidirIteraotr& operator++() { node_ptr=node_ptr->next; return *this; }
	myBidirIteraotr& operator--() { node_ptr=node_ptr->prev; return *this; }
	myBidirIteraotr operator++(int) { myBidirIteraotr<T> ret = *this; ++(*this); return ret; }
	myBidirIteraotr operator--(int) { myBidirIteraotr<T> ret = *this; --(*this); return ret; }
	//相等
	bool operator==(const myBidirIteraotr& rhs)const { return node_ptr == rhs.node_ptr; }
	bool operator!=(const myBidirIteraotr& rhs)const { return node_ptr != rhs.node_ptr; }
protected:
	myBidirNode<T>* node_ptr;//指向元素的指针
};

带头节点的双向循环链表的具体实现
一些操作注意事项及思考见注释

#pragma once
#include "illegalParameterValue.h"
#include "myExtendedLinearList.h"
#include "myBidirNode.h"
#include "myBidirIterator.h"

#include <sstream>

//带有头节点的双向循环链表
template <typename T>
class doubleCircularChain:public myExtendedLinearList<T>{
public:
	doubleCircularChain();
	doubleCircularChain(const doubleCircularChain<T>& copiedChain);
	doubleCircularChain(doubleCircularChain<T>&& movedChain) noexcept;
	~doubleCircularChain();

	doubleCircularChain& operator=(doubleCircularChain<T>& rhs);//为了区分重载 必须将rhs声明为左值引用类型
	doubleCircularChain& operator=(doubleCircularChain<T>&& rhs) noexcept;

	bool empty()const { return size == 0; }
	size_t get_size()const { return size; }
	T& get_element(size_t index)const;
	size_t index_of(const T& _element)const;
	void insert(const T& _element, size_t index);
	void erase(size_t index);
	void output(std::ostream& os = cout) const;
	void clear();
	void push_back(const T& _element);
	void pop_back();
	myBidirIteraotr<T> begin()const { return myBidirIteraotr<T>(firstNode); }//循环链表不要--begin()
	myBidirIteraotr<T> end()const { return myBidirIteraotr<T>(headerNode); }//循环链表不要++end()
	T& front()const;
	T& back()const;

protected:
	myBidirNode<T>* headerNode;
	myBidirNode<T>* firstNode;
	myBidirNode<T>* lastNode;
	size_t size;

	void check_index(size_t index)const;
};

template <typename T>
doubleCircularChain<T>::doubleCircularChain():firstNode(nullptr),lastNode(nullptr),size(0) {
	//创建一个空链表 头节点的前驱后继都指向自己
	headerNode = new myBidirNode<T>();
	headerNode->prev = headerNode;
	headerNode->next = headerNode;
}

template <typename T>
doubleCircularChain<T>::doubleCircularChain(const doubleCircularChain<T>& copiedChain) {
	size = copiedChain.size;
	headerNode = new myBidirNode<T>();//新建头节点
	if (size == 0) {//如果拷贝对象是空链表
		headerNode->prev = headerNode;
		headerNode->next = headerNode;
		lastNode = firstNode = nullptr;
	}
	else {
		myBidirNode<T>* copiedNodePtr = copiedChain.firstNode;
		//拷贝第一个节点
		firstNode = new myBidirNode<T>(copiedNodePtr->element,headerNode,nullptr);
		headerNode->next = firstNode;//更新headerNode->next
		myBidirNode<T>* newNodePtr = firstNode;
		while (copiedNodePtr->next!=copiedChain.headerNode) {
			copiedNodePtr = copiedNodePtr->next;
			newNodePtr->next = new myBidirNode<T>(copiedNodePtr->element,newNodePtr,nullptr);
			newNodePtr = newNodePtr->next;
		}
		newNodePtr->next = headerNode;//更新最后节点的next
		headerNode->prev = newNodePtr;//更新headerNode->prev
		lastNode = newNodePtr;//更新lastNode
	}
}

template <typename T>
doubleCircularChain<T>::doubleCircularChain(doubleCircularChain<T>&& movedChain) noexcept
	:headerNode(movedChain.headerNode),firstNode(movedChain.firstNode),lastNode(movedChain.lastNode),size(movedChain.size){
	//移动构造函数直接接管资源
	//并将被移动对象置于可析构状态
	movedChain.headerNode = movedChain.firstNode = movedChain.lastNode = nullptr;
	movedChain.size = 0;
}

template <typename T>
doubleCircularChain<T>::~doubleCircularChain() {
	if (headerNode!=nullptr) {//不用析构空表
		cout << "destructing:";
		while (firstNode != headerNode) {//删除链表每个节点
			myBidirNode<T>* nextNodePtr = firstNode->next;//保存后继节点
			delete firstNode;
			cout << "-deleted-";
			firstNode = nextNodePtr;
		}
		//最后删除头节点
		delete headerNode;
		lastNode = headerNode = nullptr;
		size = 0;
		cout << "destructed successfully!" << endl;
	}
}

template <typename T>
void doubleCircularChain<T>::check_index(size_t index)const {
	if (index < 0 || index >= size) {
		std::ostringstream oss;
		oss << "index must be >=0 and <" << size << ", while index= " << index << " is illegal!";
		throw illegalParameterValue(oss.str());
	}
}

template <typename T>
T& doubleCircularChain<T>::front()const {
	check_index(0);//不能对空指针进行解引用
	return firstNode->element ;
}

template <typename T>
T& doubleCircularChain<T>::back()const {
	check_index(0);//不能对空指针进行解引用
	return lastNode->element;
}

template <typename T>
T& doubleCircularChain<T>::get_element(size_t index)const {
	check_index(index);
	myBidirNode<T>* nodePtr;
	if (index < size / 2) {//如果索引在链表左边则从firstNode找起
		 nodePtr= firstNode;
		for (size_t i = 0; i < index;++i) {
			nodePtr = nodePtr->next;
		}
	}
	else {
		nodePtr = lastNode;
		for (size_t i = size - 1; i > index;--i) {
			nodePtr = nodePtr->prev;
		}
	}
	return nodePtr->element;
}

template <typename T>
size_t doubleCircularChain<T>::index_of(const T& _element)const {
	headerNode->element = _element;//将要找的元素放入头节点 减少代码量 提高效率
	myBidirNode<T>* nodePtr = headerNode->next;
	size_t pos = 0;
	while (nodePtr->element!=_element) {
		nodePtr = nodePtr->next;
		++pos;
	}
	if (nodePtr == headerNode)//没有找到或者是空表
		return -1;
	return pos;
}


template <typename T>
void doubleCircularChain<T>::erase(size_t index) {
	check_index(index);
	myBidirNode<T>* deleteNodePtr;
	if (index == 0) {//要删除首节点
		deleteNodePtr = firstNode;
		headerNode->next = firstNode->next;//更新headerNode
		firstNode->next->prev = headerNode;//更新后继节点的指针
		firstNode = firstNode->next;//更新firstNode
	}
	else if (index==size-1) {//要删除尾节点
		deleteNodePtr = lastNode;
		headerNode->prev = lastNode->prev;//更新headerNode
		lastNode->prev->next = headerNode;//更新前驱节点的指针
		lastNode = lastNode->prev;//更新lastNode
	}
	else if (index < size / 2) {//如果索引在链表左边则从firstNode找起
		myBidirNode<T>* preNodePtr = firstNode;
		for (size_t i = 0; i < index - 1;++i) {//找到前驱节点
			preNodePtr = preNodePtr->next;
		}
		deleteNodePtr = preNodePtr->next;//找到要删除的节点
		preNodePtr->next = deleteNodePtr->next;//更新前驱节点的指针
		deleteNodePtr->next->prev = preNodePtr;//更新后继节点的指针
	}
	else {//否则从lastNode找起
		myBidirNode<T>* nextNodePtr = lastNode;
		for (size_t i = size - 1; i > index + 1; --i) {//找到后继节点
			nextNodePtr = nextNodePtr->prev;
		}
		deleteNodePtr = nextNodePtr->prev;//找到要删除的节点
		nextNodePtr->prev = deleteNodePtr->prev;//更新后继节点的指针
		deleteNodePtr->prev->next = nextNodePtr;//更新前驱节点的指针
	}
	cout << "-node " << index << " deleted-" << endl;
	delete deleteNodePtr;
	--size;
}

template <typename T>
void doubleCircularChain<T>::insert(const T& _element,size_t index) {
	if (index < 0 || index > size) {
		std::ostringstream oss;
		oss << "insert index must be >=0 and <=" << size << ", while index= " << index << " is illegal!";
		throw illegalParameterValue(oss.str());
	}
	if (size==0) {//当前链表为空链表
		//构造一个新headerNode
		headerNode = new myBidirNode<T>();
		//firstNode和lastNode都指向新节点 与headerNode构成循环
		firstNode = lastNode = new myBidirNode<T>(_element,headerNode,headerNode);
		headerNode->next = lastNode;
		headerNode->prev = firstNode;
	}
	else if (index == 0) {//插入位置为首节点
		//firstNode指向新节点 前驱为headerNode 后继为原来的firstNode
		firstNode = new myBidirNode<T>(_element, headerNode, firstNode);
		headerNode->next = firstNode;//更新headerNode指向现在的firstNode
		firstNode->next->prev = firstNode;//更新原来的firstNode的prev指向现在的firstNode
	}
	else if (index == size) {//插入位置为尾节点
		//lastNode指向新节点 前驱为原来的lastNode 后继为headerNoded
		lastNode = new myBidirNode<T>(_element, lastNode, headerNode);
		headerNode->prev = lastNode;//更新headerNode指向现在的lastNode
		lastNode->prev->next = lastNode;//更新原来的lastNode的nex指向现在的lastNode
	}
	else if (index < size / 2) {//插入位置在链表的左半边 则从firstNode找起
		myBidirNode<T>* preNodePtr = firstNode;
		for (size_t i = 0; i < index - 1;++i) {//找到前驱节点
			preNodePtr = preNodePtr->next;
		}
		//前驱节点的next指向新节点 新节点前驱为前驱节点 后继为前驱节点原来的后继节点
		preNodePtr->next = new myBidirNode<T>(_element,preNodePtr,preNodePtr->next);
		preNodePtr->next->next->prev = preNodePtr->next;//更新插入节点的后继节点的prev指向新插入的节点
	}
	else {//插入位置在链表的右半边 则从lastNode找起
		myBidirNode<T>* nextNodePtr = lastNode;
		for (size_t i = size; i > index + 1;--i) {//找到后继节点
			nextNodePtr = nextNodePtr->prev;
		}
		//后继节点的prev指向新节点 新节点的前驱为原来的前驱节点 后继为后继节点
		nextNodePtr->prev = new myBidirNode<T>(_element,nextNodePtr->prev,nextNodePtr);
		nextNodePtr->prev->prev->next = nextNodePtr->prev;//更新插入节点的前驱节点的next指向新插入的节点
	}
	++size;
}

//思考:为什么索引在链表右边时,插入操作要比删除操作多一步循环?
//即erase :for(size_t i=size-1;i>index+1;--i)
//而insert:for(size_t i=size;i>index+1;--i)
//因为插入是在索引处前插 即要插入的节点的后继节点实际是索引处的节点
//而删除则是在索引处删除 所以删除的节点的后继节点实际是索引处的后一个节点


template <typename T>
void doubleCircularChain<T>::output(std::ostream& os)const {
	if (size == 0)
		os << "empty list!";
	else {
		for (myBidirIteraotr<T> iter = begin(); iter != end();++iter) {
			os << *iter << ends;
		}
	}
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const doubleCircularChain<T>& chain) {
	chain.output(os);
	return os;
}

template <typename T>
void doubleCircularChain<T>::clear() {
	//doubleCircularChain<T>::~doubleCircularChain();//直接调用析构函数
	//可能clear后还需要保留对象进行后续操作 因此不应该使用析构函数来定义clear
	if (headerNode != nullptr) {//不用析构空表
		cout << "destructing:";
		while (firstNode != headerNode) {//删除链表每个节点
			myBidirNode<T>* nextNodePtr = firstNode->next;//保存后继节点
			delete firstNode;
			cout << "-deleted-";
			firstNode = nextNodePtr;
		}
		//最后删除头节点
		delete headerNode;
		lastNode = headerNode = nullptr;
		size = 0;
		cout << "destructed successfully!" << endl;
	}
}

template <typename T>
void doubleCircularChain<T>::push_back(const T& _element) {
	insert(_element,size);//尾插
}

template <typename T>
void doubleCircularChain<T>::pop_back() {
	erase(size-1);
}

template <typename T>
doubleCircularChain<T>& doubleCircularChain<T>::operator=(doubleCircularChain<T> &rhs) {
	//使用拷贝交换技术完成拷贝赋值运算符operator=的定义 既能保证析构原始资源 又能拷贝右侧资源
	//它是异常安全且天然自赋值安全的
	//为了区分重载 必须将rhs声明为左值引用类型 因此需要在函数内部重新拷贝一个临时对象
	doubleCircularChain<T> temp(rhs);
	std::swap(size, temp.size);
	std::swap(headerNode, temp.headerNode);
	std::swap(firstNode, temp.firstNode);
	std::swap(lastNode, temp.lastNode);
	return *this;
}

template <typename T>
doubleCircularChain<T>& doubleCircularChain<T>::operator=(doubleCircularChain<T>&& rhs) noexcept{
	if (&rhs!=this) {//避免自赋值
		//移动赋值运算符operator=直接接管资源
		size = rhs.size;
		headerNode = rhs.headerNode;
		firstNode = rhs.firstNode;
		lastNode = rhs.lastNode;
		//将右侧对象置于可析构状态
		rhs.size = 0; 
		rhs.headerNode = rhs.firstNode = rhs.lastNode = nullptr;
	}
	return *this;
}

测试代码

#include "doubleCircularChain.h"
//========================双向循环链表doubleCircularChain========================
int main() {
	doubleCircularChain<int> list1;
	if (list1.empty())
		cout << "at first, list1 is empty, size=" << list1.get_size() << endl;
	//test insert/push_back/front/back/get_element/index_of
	//insert one by one to test the pointer 一个一个元素地插入 来测试是否指针是否正确更新
	cout << "-----------insert/push_back-----------" << endl;
	list1.push_back(103);
	cout << "size of int list:" << list1.get_size() << " , they are: " << list1 << endl;
	cout << "front/back="<< list1.front() << "/" << list1.back() << endl;
	cout << "list1[0]=" <<list1.get_element(0)<< endl;
	cout << "103=list1[" << list1.index_of(103) << "]" << endl << "---------" << endl;

	list1.insert(100,0);
	cout << "size of int list:" << list1.get_size() << " , they are: " << list1 << endl;
	cout << "front/back=" << list1.front() << "/" << list1.back() << endl;
	cout << "list1[0]=" << list1.get_element(0) << ends
		 << "list1[1]=" << list1.get_element(1) << endl;
	cout << "100=list1[" << list1.index_of(100) << "]" << ends
		<< "103=list1[" << list1.index_of(103) << "]" << endl << "---------" << endl;

	list1.insert(102,1);
	list1.insert(101,1);

	list1.push_back(105);
	cout << "size of int list:" << list1.get_size() << " , they are: " << list1 << endl;
	cout << "front/back=" << list1.front() << "/" << list1.back() << endl;
	cout << "list1[0]=" << list1.get_element(0)<< ends
		<< "list1[1]=" << list1.get_element(1) << ends
		<< "list1[2]=" << list1.get_element(2) << ends
		<< "list1[3]=" << list1.get_element(3) << ends
		<< "list1[4]=" << list1.get_element(4) << ends << endl;
	cout << "100=list1[" << list1.index_of(100) << "]" << ends
		<< "101=list1[" << list1.index_of(101) << "]" << ends
		<< "102=list1[" << list1.index_of(102) << "]" << ends
		<< "103=list1[" << list1.index_of(103) << "]" << ends
		<< "105=list1[" << list1.index_of(105) << "]" << endl << "---------" << endl;

	list1.insert(104,4);
	cout << "size of int list:" << list1.get_size() << " , they are: " << list1 << endl;
	cout << "front/back=" << list1.front() << "/" << list1.back() << endl;
	cout << "list1[0]=" << list1.get_element(0)<< ends
		<< "list1[1]=" << list1.get_element(1) << ends
		<< "list1[2]=" << list1.get_element(2) << ends
		<< "list1[3]=" << list1.get_element(3) << ends
		<< "list1[4]=" << list1.get_element(4) << ends
		<< "list1[5]=" << list1.get_element(5) << ends << endl;
	cout << "100=list1[" << list1.index_of(100) << "]" << ends
		<< "101=list1[" << list1.index_of(101) << "]" << ends
		<< "102=list1[" << list1.index_of(102) << "]" << ends
		<< "103=list1[" << list1.index_of(103) << "]" << ends
		<< "104=list1[" << list1.index_of(104) << "]" << ends
		<< "105=list1[" << list1.index_of(105) << "]" << endl << "---------" << endl;

	cout << "-----------erase/pop_back-----------" << endl;
	list1.pop_back();
	cout << "size of int list:" << list1.get_size() << " , they are: " << list1 << endl;
	cout << "front/back=" << list1.front() << "/" << list1.back() << endl;
	if (list1.index_of(105) == -1)
		cout << "105 has been removed!" << endl;

	list1.erase(0);
	cout << "size of int list:" << list1.get_size() << " , they are: " << list1 << endl;
	cout << "front/back=" << list1.front() << "/" << list1.back() << endl;

	list1.erase(2);
	cout << "size of int list:" << list1.get_size() << " , they are: " << list1 << endl;
	cout << "front/back=" << list1.front() << "/" << list1.back() << endl;

	//test copy constructor
	cout << "-----------copy constructor-----------" << endl;
	doubleCircularChain<int> list2(list1);
	list2.insert(100,0);
	list2.insert(103,3);
	list2.push_back(105);
	cout << "size of list1/2:" << list1.get_size() << "/" << list2.get_size() << endl;
	cout << "list1: " << list1 << endl
		<< "list2: " << list2 << ends
		<<  "front/back=" << list2.front() << "/" << list2.back() << endl;

	//test move constructor
	cout << "-----------move constructor-----------" << endl;
	doubleCircularChain<int> moved_list(std::move(list2));
	cout << "size of list2/moved_list:" << list2.get_size() << "/" << moved_list.get_size() << endl;
	cout << "list2:" << list2 << endl;
	cout << "moved_list:" << moved_list << endl;

	//test copy assignment
	cout << "-----------copy assignment-----------" << endl;
	list2.push_back(1);//因为list2是空表才没有对拷贝赋值运算符operator=的临时对象rhs进行析构 加上这句可以看到析构语句
	list2 = moved_list;
	cout << "size of list2/moved_list:" << list2.get_size() << "/" << moved_list.get_size() << endl;
	cout << "list2:" << list2 << endl;
	cout << "moved_list:" << moved_list << endl;
	//self-assignment
	list2 = list2;

	//test clear
	cout << "-----------clear-----------" << endl;
	moved_list.clear();
	cout << "size of movd_list:" << moved_list.get_size();
	cout<<", they are: " << moved_list << endl;

	//test move assignment
	cout << "-----------move assignment-----------" << endl;
	moved_list = std::move(list2);
	cout << "size of list2/moved_list:" << list2.get_size() << "/" << moved_list.get_size() << endl;
	cout << "list2:" << list2 << endl;
	cout << "moved_list:" << moved_list << endl;


	//test exception
	try
	{
		list2.pop_back();
	}
	catch (const illegalParameterValue& e)
	{
		cout << e.what() << endl;
		cout <<"size of list2:"<< list2.get_size() << endl;
	}

	//其他一些随意的测试
	cout << "--------------------------------" << endl;
	for (auto iter = moved_list.begin(); iter != moved_list.end();++iter) {
		cout << *iter << ends;
	}
	cout << endl;
	for (auto iter = moved_list.end(); iter != moved_list.begin();) {
		cout << *(--iter) << ends;
	}
	cout << endl;
	cout << *(--moved_list.begin()) << ends << *(++moved_list.end()) << endl;
	return 0;
}