进阶数据结构——双向循环链表

news/2025/2/3 0:05:02 标签: 数据结构, 链表

目录

  • 前言
  • 一、定义与结构
  • 二、特点与优势
  • 三、基本操作
  • 四、应用场景
  • 五、实现复杂度
  • 六、动态图解
  • 七、代码模版（c++）
  • 八、经典例题
  • 九、总结
  • 结语

前言

这一期我们学习双向循环链表。双向循环链表不同于单链表，双向循环链表是一种特殊的数据结构，它结合了双向链表和循环链表的特点。

在这里插入图片描述

一、定义与结构

双向循环链表中的每个节点都包含三个部分：数据域（存储数据）、前驱指针（指向前一个节点）和后继指针（指向下一个节点）。此外，链表的头节点和尾节点通过指针相互连接，形成一个闭环。这种结构使得链表可以从任意一个节点开始遍历整个链表。

二、特点与优势

双向访问：双向链表允许从任意节点向前或向后遍历，这使得在需要频繁访问链表前后节点的场景中，双向链表比单向链表更加高效。
循环特性：双向循环链表的头尾相连，形成一个环，这使得在处理需要循环访问所有节点的任务时，双向循环链表比单向循环链表更加方便。
灵活性：由于节点之间通过指针相互连接，双向循环链表在插入和删除节点时具有较高的灵活性。

三、基本操作

创建链表：首先需要初始化头节点，并设置其前驱指针和后继指针都指向自己，以形成闭环。然后，根据用户输入或其他数据源，依次插入节点。
遍历链表：可以从头节点或任意节点开始遍历整个链表。由于链表是循环的，因此遍历过程会一直进行，直到再次回到起始节点。
插入节点：在指定位置插入新节点时，需要调整新节点及其相邻节点的前驱和后继指针。
删除节点：删除指定节点时，需要调整其相邻节点的前驱和后继指针，并释放被删除节点的内存空间。
查询节点：根据节点位置或数据值查询节点时，需要从头节点开始遍历链表，直到找到目标节点或遍历完整个链表。

四、应用场景

双向循环链表在需要频繁访问链表前后节点的场景中非常有用。例如，在任务调度、缓存管理、图形界面元素管理等场景中，双向循环链表可以提供高效的数据访问和操作。

五、实现复杂度

虽然双向循环链表提供了更多的灵活性和功能，但其实现复杂度也相对较高。在插入和删除节点时，需要处理更多的指针操作，这可能会增加代码复杂性和出错风险。因此，在实现双向循环链表时，需要特别注意指针的正确性和内存管理。

六、动态图解

在这里插入图片描述

七、代码模版（c++）

#include<iostream>
using namespace std;

template<typename T>
struct Node {
	T data;
	Node* next;
	Node* prev;
	Node(const T& value):data(value),next(NULL),prev(NULL){}
};

template<class T>
class doubleLinkedNode {
private:
	Node<T>* m_dummyHead;
	int m_size;
public:
	doubleLinkedNode();
	~doubleLinkedNode();

	void push_front(const T& value);
	void push_back(const T& value);
	void insert_after(Node<T>* node, const T& value);
	void delete_node(Node<T>* node);
	void modify(Node<T>* node, const T& value);
	Node<T>* find(const T& value) const;

	void print()const;
	int size()const;
	bool empty()const;
};


template<class T>
doubleLinkedNode<T>::doubleLinkedNode():m_size(0){
	m_dummyHead = new Node<T>(T());	//初始化虚拟头结点，自己指向自己
	m_dummyHead->next = m_dummyHead;	
	m_dummyHead->prev = m_dummyHead;
}

template<class T>
doubleLinkedNode<T>::~doubleLinkedNode(){
	while (m_size > 0) {
		delete_node(m_dummyHead->next);
	}
	delete m_dummyHead;
	m_dummyHead = NULL;
}

// m_dummyHead <=> m_dummyHead ->next
// m_dummyHead <=> newNode <=> m_dummyHead -> next
template<class T>
void doubleLinkedNode<T>::push_front(const T& value){
	Node<T>* newNode = new Node<T>(value);
	newNode->prev = m_dummyHead;
	newNode->next = m_dummyHead->next;	//要好好理解一下这里，为什么不直接是 m_dummyHead-next=newNode
	m_dummyHead->next->prev = newNode;
	m_dummyHead->next = newNode;

	++m_size;
}

// m_dummyHead <=> m_dummyHead ->next
// m_dummyHead -> prev <=> newNode <=> m_dummyHead
template<class T>
void doubleLinkedNode<T>::push_back(const T& value){
	Node<T>* newNode = new Node<T>(value);
	newNode->prev = m_dummyHead->prev;
	newNode->next = m_dummyHead;		//一定要注意要改变的是newNode和m_dummyHead的前驱和后继节点，它们本身不变
	m_dummyHead->prev->next= newNode;
	m_dummyHead->prev = newNode;
	
	m_size++;
}

//插入前：node <=> node->next
//插入后：node <=> newNode <=> node->next
template<class T>
void doubleLinkedNode<T>::insert_after(Node<T>* node,const T& value){
	if (!node || node == m_dummyHead)return;
	Node<T>* newNode = new Node<T>(value);	//这里有四个箭头代表四个方向，我们加入节点就是要处理好这四个箭头
	newNode->prev = node;		//这里处理的是newNode的  <-
	newNode->next = node->next;	//  newNode ->
	node->next->prev = newNode; //node->next  <-
	node->next = newNode;		//node ->

	m_size++;
}

//插入前：node -> prev <=> node <=> node->next
//插入后：node -> prev <=> node->next
template<class T>
void doubleLinkedNode<T>::delete_node(Node<T>* node){
	if (!node || node == m_dummyHead)return;
	node->prev->next = node->next;
	node->next->prev = node->prev;
	delete node;

	m_size--;
}

template<class T>
void doubleLinkedNode<T>::modify(Node<T>* node, const T& value){
	if (!node || node == m_dummyHead)return;
	node->data = value;
}

template<class T>
Node<T>* doubleLinkedNode<T>::find(const T& value) const{
	Node<T>* curr = m_dummyHead->next;
	while (curr != m_dummyHead) {
		if (curr->data == value)return curr;
		curr = curr->next;
	}
	return NULL;
}

template<class T>
void doubleLinkedNode<T>::print() const{
	Node<T>* curr = m_dummyHead->next;
	while (curr != m_dummyHead) {
		cout << curr->data << " ";
		curr = curr->next;
	}
	cout << endl;
}

template<class T>
int doubleLinkedNode<T>::size() const{
	return m_size;
}

template<class T>
bool doubleLinkedNode<T>::empty() const {
	return m_size == 0;
}

int main() {
	doubleLinkedNode<int> dll;
	for (int i = 1; i <= 10; i++) {
		dll.push_back(i);
	}
	int M;
	cin >> M;
	while (M--) {
		int x;
		cin >> x;
		Node<int>* fn = dll.find(x);
		dll.delete_node(fn);
		dll.push_front(x);
		dll.print();
	}
	
	return 0;
}

八、经典例题

1. 小王子双链表

#include<iostream>
using namespace std;

template<typename T>
struct Node {
	T data;
	Node* next;
	Node* prev;
	Node(const T& value):data(value),next(NULL),prev(NULL){}
};

template<class T>
class doubleLinkedNode {
private:
	Node<T>* m_dummyHead;
	int m_size;
public:
	doubleLinkedNode();
	~doubleLinkedNode();

	void push_front(const T& value);
	void push_back(const T& value);
	void insert_after(Node<T>* node, const T& value);
	void delete_node(Node<T>* node);
	void modify(Node<T>* node, const T& value);
	Node<T>* find(const T& value) const;

	void print()const;
	int size()const;
	bool empty()const;
};


template<class T>
doubleLinkedNode<T>::doubleLinkedNode():m_size(0){
	m_dummyHead = new Node<T>(T());	//初始化虚拟头结点，自己指向自己
	m_dummyHead->next = m_dummyHead;	
	m_dummyHead->prev = m_dummyHead;
}

template<class T>
doubleLinkedNode<T>::~doubleLinkedNode(){
	while (m_size > 0) {
		delete_node(m_dummyHead->next);
	}
	delete m_dummyHead;
	m_dummyHead = NULL;
}

// m_dummyHead <=> m_dummyHead ->next
// m_dummyHead <=> newNode <=> m_dummyHead -> next
template<class T>
void doubleLinkedNode<T>::push_front(const T& value){
	Node<T>* newNode = new Node<T>(value);
	newNode->prev = m_dummyHead;
	newNode->next = m_dummyHead->next;	//要好好理解一下这里，为什么不直接是 m_dummyHead-next=newNode
	m_dummyHead->next->prev = newNode;
	m_dummyHead->next = newNode;

	++m_size;
}

// m_dummyHead <=> m_dummyHead ->next
// m_dummyHead -> prev <=> newNode <=> m_dummyHead
template<class T>
void doubleLinkedNode<T>::push_back(const T& value){
	Node<T>* newNode = new Node<T>(value);
	newNode->prev = m_dummyHead->prev;
	newNode->next = m_dummyHead;		//一定要注意要改变的是newNode和m_dummyHead的前驱和后继节点，它们本身不变
	m_dummyHead->prev->next= newNode;
	m_dummyHead->prev = newNode;
	
	m_size++;
}

//插入前：node <=> node->next
//插入后：node <=> newNode <=> node->next
template<class T>
void doubleLinkedNode<T>::insert_after(Node<T>* node,const T& value){
	if (!node || node == m_dummyHead)return;
	Node<T>* newNode = new Node<T>(value);	//这里有四个箭头代表四个方向，我们加入节点就是要处理好这四个箭头
	newNode->prev = node;		//这里处理的是newNode的  <-
	newNode->next = node->next;	//  newNode ->
	node->next->prev = newNode; //node->next  <-
	node->next = newNode;		//node ->

	m_size++;
}

//插入前：node -> prev <=> node <=> node->next
//插入后：node -> prev <=> node->next
template<class T>
void doubleLinkedNode<T>::delete_node(Node<T>* node){
	if (!node || node == m_dummyHead)return;
	node->prev->next = node->next;
	node->next->prev = node->prev;
	delete node;

	m_size--;
}

template<class T>
void doubleLinkedNode<T>::modify(Node<T>* node, const T& value){
	if (!node || node == m_dummyHead)return;
	node->data = value;
}

template<class T>
Node<T>* doubleLinkedNode<T>::find(const T& value) const{
	Node<T>* curr = m_dummyHead->next;
	while (curr != m_dummyHead) {
		if (curr->data == value)return curr;
		curr = curr->next;
	}
	return NULL;
}

template<class T>
void doubleLinkedNode<T>::print() const{
	Node<T>* curr = m_dummyHead->next;
	while (curr != m_dummyHead) {
		cout << curr->data << " ";
		curr = curr->next;
	}
	cout << endl;
}

template<class T>
int doubleLinkedNode<T>::size() const{
	return m_size;
}

template<class T>
bool doubleLinkedNode<T>::empty() const {
	return m_size == 0;
}

int main() {
	doubleLinkedNode<int> dll;
	for (int i = 1; i <= 10; i++) {
		dll.push_back(i);
	}
	int M;
	cin >> M;
	while (M--) {
		int x;
		cin >> x;
		Node<int>* fn = dll.find(x);
		dll.delete_node(fn);
		dll.push_front(x);
		dll.print();
	}
	
	return 0;
}

九、总结

综上所述，双向循环链表是一种功能强大且灵活的数据结构，适用于需要频繁访问链表前后节点的场景。然而，其实现复杂度也相对较高，需要开发者具备扎实的编程基础和内存管理能力。

结语

当前进阶的数据结构比之前学的初级数据结构要复杂了，希望大家一定要动手敲一遍代码，敲完之后提交到例题里检查一下是否正确，出现bug不用慌张，耐心差错，这样你的水平才能提升。
在这里插入图片描述

希望大家可以一键三连，后续我们一起学习，谢谢大家！！！
在这里插入图片描述


http://www.niftyadmin.cn/n/5840385.html

相关文章

分析伏羲万年历

分析伏羲万年历

功能分析 日历功能 https://github.com/6tail/lunar-java Lunar https://6tail.cn/calendar/api.html Http抓包 使用Charles进行HTTPS抓包 https://zhaojian.blog.csdn.net/article/details/130281149 找到代理的ip地址 ifconfig | grep inet | grep 192 设置手机代理 常…
阅读更多...
1979-2021年 全国各省、地级市、区县空气流通系数

1979-2021年 全国各省、地级市、区县空气流通系数

1979-2021年 全国各省、地级市、区县空气流通系数.ziphttps://download.csdn.net/download/2401_84585615/89649517 https://download.csdn.net/download/2401_84585615/89649517 1979-2021年&#xff0c;全国各省、地级市、区县空气流通系数的研究数据&#xff0c;对于分析我国…
阅读更多...
【LeetCode】5. 贪心算法：买卖股票时机

【LeetCode】5. 贪心算法：买卖股票时机

太久没更了&#xff0c;抽空学习下。 看一道简单题。 class Solution:def maxProfit(self, prices: List[int]) -> int:cost -1profit 0for i in prices:if cost -1:cost icontinueprofit_ i - costif profit_ > profit:profit profit_if cost > i:cost iret…
阅读更多...
蓝桥杯之c++入门（二）【输入输出（上）】

蓝桥杯之c++入门（二）【输入输出（上）】

目录 前言1&#xff0e;getchar和 putchar1.1 getchar()1.2 putchar() 2&#xff0e;scanf和 printf2.1 printf2.1.1基本用法2.1.2占位符2.1.3格式化输出2.1.3.1 限定宽度2.1.3.2 限定小数位数 2.2 scanf2.2.1基本用法2.2.2 占位符2.2.3 scanf的返回值 2.3练习练习1&#xff1a…
阅读更多...
DIFY源码解析

DIFY源码解析

偶然发现Github上某位大佬开源的DIFY源码注释和解析&#xff0c;目前还处于陆续不断更新地更新过程中&#xff0c;为大佬的专业和开源贡献精神点赞。先收藏链接&#xff0c;后续慢慢学习。 相关链接如下&#xff1a; DIFY源码解析
阅读更多...
基于改进的强跟踪技术的扩展Consider Kalman滤波算法在无人机导航系统中的应用研究

基于改进的强跟踪技术的扩展Consider Kalman滤波算法在无人机导航系统中的应用研究

在无人机组合导航系统中&#xff0c;精确的状态估计对于任务的成功执行至关重要。然而&#xff0c;系统面临的非线性特性和不确定性&#xff0c;如传感器的量测偏差和动态环境变化&#xff0c;常常导致传统Kalman滤波算法失效。因此&#xff0c;提出一种鲁棒且有效的滤波算法&a…
阅读更多...
二级C语言：二维数组每行最大值与首元素交换、删除结构体的重复项、取出单词首字母

二级C语言：二维数组每行最大值与首元素交换、删除结构体的重复项、取出单词首字母

目录 一、程序填空 --- 二维数组每行最大值与首元素交换 题目 分析 知识点 --- 交换语句 二、程序修改 --- 删除结构体的重复项 题目 分析 三、程序设计 --- 取出单词首字母 题目 分析 前言 本章讲解&#xff1a;二维数组每行最大值与首元素交换、删除结构体的重复项…
阅读更多...
玉米苗和杂草识别分割数据集labelme格式1997张3类别

玉米苗和杂草识别分割数据集labelme格式1997张3类别

数据集格式&#xff1a;labelme格式(不包含mask文件&#xff0c;仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数)&#xff1a;1997 标注数量(json文件个数)&#xff1a;1997 标注类别数&#xff1a;3 标注类别名称:["corn","weed","Bean…
阅读更多...
最新文章

Copyright @ 2022~2023