当前位置： 首页 > article >正文

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

article 2025/2/3 1:33:08

目录

  • 前言
  • 一、定义与结构
  • 二、特点与优势
  • 三、基本操作
  • 四、应用场景
  • 五、实现复杂度
  • 六、动态图解
  • 七、代码模版（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.kler.cn/a/529161.html

相关文章：

  • 5.4.2 结构化设计方法+结构化程序设计方法
  • jstat命令详解
  • 无心剑七绝《深度求索》
  • list的使用，及部分功能的模拟实现（C++）
  • 索引的底层数据结构、B+树的结构、为什么InnoDB使用B+树而不是B树呢
  • PyQt6医疗多模态大语言模型（MLLM）实用系统框架构建初探（上.文章部分）
  • 8.攻防世界Web_php_wrong_nginx_config
  • pandas中的str使用方法
  • 【回溯+剪枝】电话号码的字母组合 括号生成
  • 五.简单函数
  • 【学习笔记】深度学习网络-正则化方法
  • 【NLP251】Transformer中的Attention机制
  • 【Proteus】NE555纯硬件实现LED呼吸灯效果，附源文件，效果展示
  • 设计心得——平衡和冗余
  • C语言：输入正整数链表并选择删除任意结点
  • ComfyUI安装调用DeepSeek——DeepSeek多模态之图形模型安装问题解决（ComfyUI-Janus-Pro）
  • 一文学会HTML编程之视频+图文详解详析
  • Selenium 使用指南：从入门到精通
  • 17.2 图形绘制8
  • ASP.NET Core与配置系统的集成
  • redex快速体验
  • 力扣动态规划-16【算法学习day.110】
  • 《苍穹外卖》项目学习记录-Day5在Java中操作Redis_Spring Data Redis
  • torch numpy seed使用方法
  • Easy系列PLC尺寸测量功能块(激光微距应用)
  • 2007-2019年各省科学技术支出数据