C++实现数据结构之带头双向循环链表_c++ 双向循环

本文主要讲的是带头双向循环链表（若发现有错，请指正！）

目录

什么是带头双向循环链表？

 看到这图，你可能会想这链表结构这么复杂，有什么用呢？

代码实现链表！！！

完整功能的头文件

打印链表

初始化头节点（即哨兵位）

创建新节点

头插

头删

尾插

尾删

查找

插入

删除

注意！！！

释放内存

以上便是代码实现链表的功能

使用插入功能代替头插

使用插入功能代替尾插

使用删除功能代替头删

使用删除功能代替尾删

完整cpp文件实现

优势

关于单链表及推荐题

顺序表和链表的联系以及区别

---

什么是带头双向循环链表？

带头即是有一个没有数值域的头节点。

双向即是与单链表不同，双向链表的节点是有一个数值域和两个指针域：一个是指向下一个节点的指针，另一个是指向上一个节点的指针（*prev，*next）

循环链表即是头节点的 *prev 指向链表的最后一个节点，最后一个节点的 *next 指向哨兵位。

上面所描述的便是带头双向循环链表，可以根据下图理解

 看到这图，你可能会想这链表结构这么复杂，有什么用呢？

这种结构自然会有它独特的优势：这种结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环结构。这个结构虽然复杂，但是使用代码实现以后会发现结构带来许多优势，实现反而简单了，后面代码实现了就可以知道了。

代码实现链表！！！

该链表的功能有头插、头删、尾插、尾删、查找、插入和删除。

完整功能的头文件

#pragma once
 
struct ListNode
{
	int data;
	ListNode* next;
	ListNode* prev;
};
 
//打印链表
void showList(ListNode* head);
 
//初始化哨兵位
ListNode* ListInit();
 
//创建新结点
ListNode* BuyNewNode(int x);
 
//头插
void ListPushFront(ListNode* head, int x);
 
//头删
void ListPopFront(ListNode* head);
 
//尾插    
void ListPushBack(ListNode* head, int x);
 
//尾删
void ListPopBack(ListNode* head);
 
//查找
ListNode* ListFind(ListNode* head, int x);
 
//插入  在pos位置前面插入  pos可以由查找函数得到  插入函数可以取代头插
void ListInsert(ListNode* pos, int x);
 
//删除  删除pos位置  删除函数可以取代尾删
void ListErase(ListNode* pos);
 
//释放内存
void ListDestroy(ListNode* head);

 

打印链表

//打印链表
void showList(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		cout << cur->data << " ";
		cur = cur->next;
	}
	cout << endl;
}

初始化头节点（即哨兵位）

需要注意的是只有头节点的时候，头节点的 *prev 和 *next 都要指向自己

//初始化哨兵位
ListNode* ListInit()
{
	ListNode* head = new ListNode;
	head->next = head;
	head->prev = head;
	return head;
}

因为下面会有许多插入新节点的操作，所以我们需要创建新节点，为了使代码整洁，我们可以将创建新节点的操作封装成函数

创建新节点

//创建新节点
ListNode* BuyNewNode(int x)
{
	ListNode* newNode = new ListNode;
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

头插

//头插
void ListPushFront(ListNode* head, int x)
{
	ListNode* newNode = BuyNewNode(x);
	ListNode* cur = head->next;
	head->next = newNode;
	newNode->prev = head;
	newNode->next = cur;
	cur->prev = newNode;
}

头删

//头删
void ListPopFront(ListNode* head)
{
	assert(head);
	assert(head->next != head);
	ListNode* cur = head->next;
	ListNode* next = cur->next;
	head->next = next;
	next->prev = head;
	delete cur;
}

尾插

//尾插
void ListPushBack(ListNode* head, int x)
{
	//断言  head为NULL时，程序崩溃并且提醒什么地方错误
	assert(head);
 
	//开始尾插
	ListNode* newNode = BuyNewNode(x);
	ListNode* tail = head->prev;
	tail->next = newNode;
	newNode->prev = tail;
	//newNode->data = x;
	newNode->next = head;
	head->prev = newNode;
 
}

尾删

//尾删
void ListPopBack(ListNode* head)
{
	assert(head);
	assert(head->next != head);
	ListNode* tail = head->prev;
	tail->prev->next = head;
	head->prev = tail->prev;
	delete tail;
 
}

查找

//查找
ListNode* ListFind(ListNode* head, int x)
{
	assert(head);
	assert(head->next != head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

插入

//插入  在pos位置前面插入  pos可以由查找函数得到  插入函数可以取代头插,尾插
void ListInsert(ListNode* pos, int x)
{
	ListNode* newNode = BuyNewNode(x);
	ListNode* prev = pos->prev;
	prev->next = newNode;
	newNode->prev = prev;
	newNode->next = pos;
	pos->prev = newNode;
}

删除

//删除  删除pos位置  删除函数可以取代尾删，头删
void ListErase(ListNode* pos)
{
	assert(pos);
	assert(pos->next != pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	delete pos;
}

注意！！！

因为我们创建新节点是要使用new关键字的，所以自然要有delete关键字，所以我们还需要释放内存

释放内存

//释放内存
void ListDestroy(ListNode* head)
{
	ListNode* cur = head->next;
	while (cur != head)
	{
		ListNode* next = cur->next;
		delete cur;
		cur = next;
	}
	delete head;
}

以上便是代码实现链表的功能

看完上面代码，你可能会想：似乎实现起来好像也不简单呀！那是我还没展现出来

其实可以发现，当我们有了插入和删除的功能后，我们完全可以使用插入代替头插、尾插，使用删除代替头删、尾删

下面我们来重新实现头插、尾插，头删、尾删。

使用插入功能代替头插

//头插
void ListPushFront(ListNode* head, int x)
{
	/*ListNode* newNode = BuyNewNode(x);
	ListNode* cur = head->next;
	head->next = newNode;
	newNode->prev = head;
	newNode->next = cur;
	cur->prev = newNode;*/
 
	//用插入函数ListInsert代替头插
	ListInsert(head->next, x);
}

使用插入功能代替尾插

//尾插
void ListPushBack(ListNode* head, int x)
{
	//断言  head为NULL时，程序崩溃并且提醒什么地方错误
	assert(head);
 
	//开始尾插
	//ListNode* newNode = BuyNewNode(x);
	//ListNode* tail = head->prev;
	//tail->next = newNode;
	//newNode->prev = tail;
	newNode->data = x;
	//newNode->next = head;
	//head->prev = newNode;
 
	//用插入函数ListInsert代替尾插
	ListInsert(head, x);
}

使用删除功能代替头删

//头删
void ListPopFront(ListNode* head)
{
	assert(head);
	/*assert(head->next != head);
	ListNode* cur = head->next;
	ListNode* next = cur->next;
	head->next = next;
	next->prev = head;
	delete cur;*/
 
	//使用删除函数ListErase代替头删
	ListErase(head->next);
}

使用删除功能代替尾删

//尾删
void ListPopBack(ListNode* head)
{
	assert(head);
	assert(head->next != head);
	/*ListNode* tail = head->prev;
	tail->prev->next = head;
	head->prev = tail->prev;
	delete tail;*/
 
	//使用删除函数ListErase代替尾删
	ListErase(head->prev);
}

完整cpp文件实现

#include"list.h"
#include<assert.h>
#include<iostream>
using namespace std;
 
//初始化哨兵位
ListNode* ListInit()
{
	ListNode* head = new ListNode;
	head->next = head;
	head->prev = head;
	return head;
}
 
ListNode* BuyNewNode(int x)
{
	ListNode* newNode = new ListNode;
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
 
//尾插
void ListPushBack(ListNode* head, int x)
{
	//断言  head为NULL时，程序崩溃并且提醒什么地方错误
	assert(head);
 
	//开始尾插
	//ListNode* newNode = BuyNewNode(x);
	//ListNode* tail = head->prev;
	//tail->next = newNode;
	//newNode->prev = tail;
	newNode->data = x;
	//newNode->next = head;
	//head->prev = newNode;
 
	//用插入函数ListInsert代替尾插
	ListInsert(head, x);
}
 
//打印链表
void showList(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		cout << cur->data << " ";
		cur = cur->next;
	}
	cout << endl;
}
 
//尾删
void ListPopBack(ListNode* head)
{
	assert(head);
	assert(head->next != head);
	/*ListNode* tail = head->prev;
	tail->prev->next = head;
	head->prev = tail->prev;
	delete tail;*/
 
	//使用删除函数ListErase代替尾删
	ListErase(head->prev);
}
 
//头插
void ListPushFront(ListNode* head, int x)
{
	/*ListNode* newNode = BuyNewNode(x);
	ListNode* cur = head->next;
	head->next = newNode;
	newNode->prev = head;
	newNode->next = cur;
	cur->prev = newNode;*/
 
	//用插入函数ListInsert代替头插
	ListInsert(head->next, x);
}
 
//头删
void ListPopFront(ListNode* head)
{
	assert(head);
	/*assert(head->next != head);
	ListNode* cur = head->next;
	ListNode* next = cur->next;
	head->next = next;
	next->prev = head;
	delete cur;*/
 
	//使用删除函数ListErase代替头删
	ListErase(head->next);
}
 
//查找
ListNode* ListFind(ListNode* head, int x)
{
	assert(head);
	assert(head->next != head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
//插入  在pos位置前面插入  pos可以由查找函数得到  插入函数可以取代头插,尾插
void ListInsert(ListNode* pos, int x)
{
	ListNode* newNode = BuyNewNode(x);
	ListNode* prev = pos->prev;
	prev->next = newNode;
	newNode->prev = prev;
	newNode->next = pos;
	pos->prev = newNode;
}
 
//删除  删除pos位置  删除函数可以取代尾删，头删
void ListErase(ListNode* pos)
{
	assert(pos);
	assert(pos->next != pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	delete pos;
}
 
//释放内存   
void ListDestroy(ListNode* head)
{
	ListNode* cur = head->next;
	while (cur != head)
	{
		ListNode* next = cur->next;
		delete cur;
		cur = next;
	}
	delete head;
}

优势

修改后是不是就发现了代码量大大的减少了

这只是带头双向循环链表的一个优势，还有更重要的优势，便是时间复杂度减小

普通的链表，当进行尾插、尾删时，我们都是需要通过while循环找到最后一个节点，实现起来时间复杂度是O(N)，而带头双向循环链表只需要O(1)，因为头节点的 *prev 指向的便是最后一个节点，不需要循环找到最后一个节点。

而且插入、删除某个节点也不需要复杂的代码实现找节点的上一个节点位置，就可以实现插入和删除功能。

关于单链表及推荐题

单链表相对比较简单，我便不发布文章讲解了，下面可以推荐几道关于单链表的题

1.反转单链表：https://leetcode-cn.com/problems/reverse-linked-list/

2.链表的中间结点：https://leetcode-cn.com/problems/middle-of-the-linked-list/

3.合并两个有序链表：https://leetcode-cn.com/problems/merge-two-sorted-lists/

4.判断链表是否有环？：https://leetcode-cn.com/problems/linked-list-cycle/

5.求环形链表的入口点？：https://leetcode-cn.com/problems/linked-list-cycle-ii/

顺序表和链表的联系以及区别

顺序表：

                优点：空间连续，支持随机访问

                缺点：1、中间或前面部分的的插入删除时间复杂度为O(N)

                           2、增容的代价比较大

   链表：

                优点：1、任意位置插入删除时间复杂度为O(1)

                           2、没有增容消耗，按需申请节点空间，不用了直接释放

                缺点：以节点为单位存储，不支持随机访问