数据结构初阶–双向循环链表（讲解+类模板实现）

带头双向链表的结构

看下面的图，就是我今天要给大家分享有结构——带头双向循环链表。这里的头是不存放任何数据的，就是一个哨兵卫的头结点。

用代码来表示每一个节点就是这样的：

• 数据域和指针域
• 两个指针，一个指向前驱结点，一个指向后继结点
• 给定两个构造函数，有参和无参，分别对结点的指针域和数据域进行初始化

template <class DateType> struct LinkNode {       //数据域       DateType data;       //两个指针       LinkNode<DateType>* prev;       LinkNode<DateType>* next;       LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next){}       LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next){} }; 

带头双向链表的接口实现

要实现的接口

LinkList();//构造函数，初始化头节点 LinkList(const LinkList<DateType>& list2);//拷贝构造，进行两个链表的拷贝 ~LinkList();//析构函数，用来清除链表，释放结点空间 int Length();//求双向循环链表的长度 void CreateList(int n);//常见n个结点的双向循环链表 bool GetElem(int pos,DateType& data);//得到pos位置结点的元素值 LinkNode<DateType>* Locate(int i ,int back_pos);//定位元素，当back_pos=0的时候，从头节点向前查询第i个元素，back_pos！=0的时候，从头节点后查询第i个元素 bool Insert(int pos, const DateType& data, int back_pos);//在pos的位置插入元素，当back_pos！=0的时候，在pos位置后插入元素，当back_pos=0的时候，在pos位置前插入元素 void PrintList(int sign);//输出双向循环链表所有结点的元素值，当sign！=0时，正序打印元素值，当sign=0时，逆序打印 bool Delete(int pos, DateType& data,int back_pos);//删除pos位置的结点 

双向链表的小框架

template<class DateType> class LinkList { public: private: 	LinkNode<DateType>* head;//头节点 }; 

初始化双向链表

在初始化双链表的过程中，我们要开好一个头节点，作为哨兵卫的头节点，然后返回这个节点的指针，接口外面只要用一个节点指针接受这个返回值就好了，具体实现如下：

//构造函数,初始化一个循环双链表 	LinkList() 	{ 		head = new LinkNode<DateType>; 		if (head == NULL) 		{ 			cout << "内存分配失败" << endl; 			exit(-1); 		} 		head->data = 0; 		head->next = head; 		head->prev = head; 	} 

拷贝构造

在拷贝构造中，要注意一件事情，就是最后一个结点的next需要指向头节点，头节点的prev需要指向最后一个结点，形成双向循环链表

//拷贝构造 	LinkList(const LinkList<DateType>& list2) 	{ 		LinkNode<DateType>* p = list2.head->next; 		if (p == NULL) 		{ 			cout << "内存分配失败" << endl; 			exit(-1); 		} 		head = new LinkNode<DateType>; 		LinkNode<DateType>* h = head; 		while (p!=list2.head) 		{ 			LinkNode<DateType>* t = new LinkNode<DateType>; 			h->next = t; 			t->prev = h; 			t->data = p->data; 			p = p->next; 			h = h->next; 		} 		h->next = this->head; 		this->head->prev = h; 	} 

定位结点

因为后面的在指定插入删除元素，需要定位pos位置结点的地址，所以这里旧封装一个函数，直接获取pos位置结点的地址

//定位元素，back_pos=0时从头节点向前查第i个元素，d!=0时，从头节点向后找第i个元素 	LinkNode<DateType>* Locate(int i ,int back_pos) 	{ 		if (head->next == head || i == 0) { 			return head; 		} 		int j = 0; 		LinkNode<DateType>* p = head; 		//从头节点往后找第i个元素 		if (back_pos) 		{ 			while (p->next != head && j != i) 			{ 				p = p->next; 				++j; 			} 			if (p->next == head && j != i) 			{ 				return NULL; 			} 			else 			{ 				return p; 			}  		}//向前找 		else 		{ 			while (p->prev != head && j != i) 			{ 				p = p->prev; 				++j; 			} 			if (p->prev == head && j != i) 				return NULL; 			else 				return p; 		} 	} 

创建双向链表

//创建双循环链表 	void CreateList(int n) 	{ 		DateType* nodetemp = new DateType[n]; 		for (rsize_t i = 0; i < n; i++) 		{ 			cout << "Enter the element:  " << endl; 			cin >> nodetemp[i]; 			Insert(i, nodetemp[i], 1); 		} 		delete[] nodetemp; 		 	} 

打印双向循环链表

因为是双向循环链表，可以很简单的实现正序打印和逆序打印，所以这里用一个标志sign，来指定正序还是逆序打印链表元素

//输出双循环链表所有结点的元素值,分为正序打印和逆序打印 	void PrintList(int sign) 	{ 		//正序打印 		if (sign) 		{ 			cout << "head " ; 			LinkNode<DateType>* p = head; 			while (p->next != head) 			{ 				p = p->next; 				cout << "-> " << p->data; 			} 			cout << "->over" << endl; 		}//逆序打印 		else 		{ 			cout << "head " << endl; 			LinkNode<DateType>* p = head; 			while (p->prev != head) 			{ 				p = p->prev; 				cout << "-> " << p->data; 			} 			cout << "->over" << endl; 		} 	} 

指定位置插入结点

任意位置插入首先要开辟一个节点，然后就是按照所个位置，改变指针的指向来把这个节点连接上去，看具体代码实现如下：

//在pos的位置插入元素 	bool Insert(int pos, const DateType& data, int back_pos) 	{ 		LinkNode<DateType>* p = Locate(pos, back_pos); 		if (!p) 			return false; 		LinkNode<DateType>* new_node = new LinkNode<DateType>(data); 		if (NULL == new_node) 		{ 			cout << "内存分配失败" << endl; 			exit(-1); 		} 		//p结点后插入 		if (back_pos) 		{ 			p->next->prev = new_node; 			new_node->prev = p; 			new_node->next = p->next; 			p->next = new_node; 		}//p结点前插入 		else 		{ 			p->prev->next = new_node; 			new_node->next = p; 			new_node->prev = p->prev; 			p->prev = new_node; 		}return true; 	} 

指定位置删除结点

删除就要考虑链表是否为空，防止删除头节点

//删除pos位置的结点 	bool Delete(int pos, DateType& data,int back_pos) 	{ 		LinkNode<DateType>* p = Locate(pos, back_pos); 		if (!p) 		{ 			return false; 		} 		if (p == head ) 		{ 			cout << "请不要删除头节点" << endl; 			return false; 		} 		data = p->data; 		p->prev->next = p->next; 		p->next->prev = p->prev; 		delete p; 		return true; 	} 

获取链表长度

int Length() 	{ 		LinkNode<DateType>* p = head; 		int i = 0; 		while (p->next != head) 		{ 			++i; 			p = p->next; 		} 		return i;  	} 

销毁链表

在析构函数中实现链表的销毁

//析构函数 	~LinkList() 	{ 		LinkNode<DateType>* p, * q = head->next; 		while (q != head) 		{ 			p = q; 			q = q->next; 			delete p; 		} 	} 

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 /* 双向循环链表 */ template <class DateType> struct LinkNode { 	//数据域 	DateType data; 	//两个指针 	LinkNode<DateType>* prev; 	LinkNode<DateType>* next; 	LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next) 	{} 	LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next) 	{} }; template<class DateType> class LinkList { public: 	//构造函数,初始化一个循环双链表 	LinkList() 	{ 		head = new LinkNode<DateType>; 		if (head == NULL) 		{ 			cout << "内存分配失败" << endl; 			exit(-1); 		} 		head->data = 0; 		head->next = head; 		head->prev = head; 	} 	//拷贝构造 	LinkList(const LinkList<DateType>& list2) 	{ 		LinkNode<DateType>* p = list2.head->next; 		if (p == NULL) 		{ 			cout << "内存分配失败" << endl; 			exit(-1); 		} 		head = new LinkNode<DateType>; 		LinkNode<DateType>* h = head; 		while (p!=list2.head) 		{ 			LinkNode<DateType>* t = new LinkNode<DateType>; 			h->next = t; 			t->prev = h; 			t->data = p->data; 			p = p->next; 			h = h->next; 		} 		h->next = this->head; 		this->head->prev = h; 	} 	//析构函数 	~LinkList() 	{ 		LinkNode<DateType>* p, * q = head->next; 		while (q != head) 		{ 			p = q; 			q = q->next; 			delete p; 		} 	} 	//求双循环链表的长度 	int Length() 	{ 		LinkNode<DateType>* p = head; 		int i = 0; 		while (p->next != head) 		{ 			++i; 			p = p->next; 		} 		return i;  	} 	//创建双循环链表 	void CreateList(int n) 	{ 		DateType* nodetemp = new DateType[n]; 		for (rsize_t i = 0; i < n; i++) 		{ 			cout << "Enter the element:  " << endl; 			cin >> nodetemp[i]; 			Insert(i, nodetemp[i], 1); 		} 		delete[] nodetemp; 		 	} 	//得到位置为pos的结点元素值 	bool GetElem(int pos,DateType& data) 	{ 		LinkNode<DateType>* p = head; 		if (pos<0 || pos>Length()) 		{ 			cout << "输入的位置不合法" << endl; 			return false; 		} 		else { 			p = Locate(pos, 1); 			data = p->data; 		} 		return true; 	} 	//定位元素，back_pos=0时从头节点向前查第i个元素，d!=0时，从头节点向后找第i个元素 	LinkNode<DateType>* Locate(int i ,int back_pos) 	{ 		if (head->next == head || i == 0) { 			return head; 		} 		int j = 0; 		LinkNode<DateType>* p = head; 		//从头节点往后找第i个元素 		if (back_pos) 		{ 			while (p->next != head && j != i) 			{ 				p = p->next; 				++j; 			} 			if (p->next == head && j != i) 			{ 				return NULL; 			} 			else 			{ 				return p; 			}  		}//向前找 		else 		{ 			while (p->prev != head && j != i) 			{ 				p = p->prev; 				++j; 			} 			if (p->prev == head && j != i) 				return NULL; 			else 				return p; 		} 	} 	//在pos的位置插入元素 	bool Insert(int pos, const DateType& data, int back_pos) 	{ 		LinkNode<DateType>* p = Locate(pos, back_pos); 		if (!p) 			return false; 		LinkNode<DateType>* new_node = new LinkNode<DateType>(data); 		if (NULL == new_node) 		{ 			cout << "内存分配失败" << endl; 			exit(-1); 		} 		//p结点后插入 		if (back_pos) 		{ 			p->next->prev = new_node; 			new_node->prev = p; 			new_node->next = p->next; 			p->next = new_node; 		}//p结点前插入 		else 		{ 			p->prev->next = new_node; 			new_node->next = p; 			new_node->prev = p->prev; 			p->prev = new_node; 		}return true; 	} 	//输出双循环链表所有结点的元素值,分为正序打印和逆序打印 	void PrintList(int sign) 	{ 		//正序打印 		if (sign) 		{ 			cout << "head " ; 			LinkNode<DateType>* p = head; 			while (p->next != head) 			{ 				p = p->next; 				cout << "-> " << p->data; 			} 			cout << "->over" << endl; 		}//逆序打印 		else 		{ 			cout << "head " << endl; 			LinkNode<DateType>* p = head; 			while (p->prev != head) 			{ 				p = p->prev; 				cout << "-> " << p->data; 			} 			cout << "->over" << endl; 		} 	} 	//删除pos位置的结点 	bool Delete(int pos, DateType& data,int back_pos) 	{ 		LinkNode<DateType>* p = Locate(pos, back_pos); 		if (!p) 		{ 			return false; 		} 		if (p == head ) 		{ 			cout << "请不要删除头节点" << endl; 			return false; 		} 		data = p->data; 		p->prev->next = p->next; 		p->next->prev = p->prev; 		delete p; 		return true; 	} private: 	LinkNode<DateType>* head;//头节点 }; int main() { 	LinkList<int> list; 	list.CreateList(5); 	list.PrintList(1); 	cout << "-----------------------" << endl; 	LinkList<int> list2(list); 	list2.PrintList(1); 	cout << "-----------------------" << endl; 	list.Insert(0, 10, 1); 	list.PrintList(1); 	cout << list.Length() << endl; 	cout << "-----------------------" << endl; 	int b = 0; 	list.Delete(0, b, 1); 	cout << b << endl; 	list.PrintList(1); 	cout << list.Length() << endl; 	cout << "-----------------------" << endl; 	list.GetElem(3, b); 	cout << b << endl; 	cout <<"---------------------------" << endl; 	system("pause"); 	return EXIT_SUCCESS; } 

链表和顺序表的对比

参考下表：

不同点	顺序表	链表
存储空间上	物理上连续	逻辑上连续
随机访问	支持	不支持
任意位置插入删除	要移动元素，O(N)	只要改变指针指向
插入数据	要考虑扩容，会带来一定的空间消耗	没有容量这个概念，可以按需申请和释放
缓存利用率	高	低