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

站长交易网东莞网络做推广公司

news 2025/11/7 2:11:07
站长交易网,东莞网络做推广公司,自动与手动控制电路图,公司做网站 需要解决哪些问题目录 前言一、定义与结构二、特点与优势三、基本操作四、应用场景五、实现复杂度六、动态图解七、代码模版（c）八、经典例题九、总结结语 前言 这一期我们学习双向循环链表。双向循环链表不同于单链表，双向循环链表是一种特殊的数据结构&…

目录

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

相关文章：

  • 怎么做 在线电影网站wordpress aike主题
  • 网站后台会员管理wordpress教程网59iwp
  • 免费中文网站模板互联网应用技术学什么
  • 前端网站开发教程北京互联网网站建设价格
  • 创业公司用wordpress东莞关键词优化平台
  • 青岛网站建设东橙品牌设计建设银行网站明细多长时间
  • 2013电子商务网站建设百度官网网站登录
  • 纪检网站建设方案图片动画制作
  • 南昌制作网站的公司吗计算机专业论文网站开发
  • 电子商务网站建设外包服务怎么让网站排名下降
  • 开发小网站一般多少钱一个山东 网站备案
  • 中国空间站最新消息新闻自贡网站制作
  • 最棒的网站建设如何建立一个自己的网站啊
  • 建什么网站 做 cpa广州企业网站建设哪家好
  • 做蛋糕的英文网站wordpress 经过天数
  • 做临床研究在哪个网站注册受欢迎的佛山网站制作
  • 鄂州网站建设设计科技狂人
  • 宁波网站制作怎样360推广登陆入口
  • 企业网站的建立费用重庆发布的最新消息今天
  • 四川做网站的公司有哪些河南省建设集团有限公司官网
  • 有没有卖设计的网站网站项目开发案
  • 能建设铁塔的公司网站wordpress 中文字体插件
  • 武威市凉州区建设局网站建设网站服务器自营方式的特点
  • 不用服务器做视频网站手机淘宝网页
  • 网站目录命名盐城市网站
  • 浙江建设局图审网站中关村网站建设公司
  • 群团组织网站建设中山网站建设哪家强
  • 江西做网站的公司绍兴市交通建设有限公司网站
  • 祁东网站设计公司网站开发程序员工资
  • 免费自助建站哪个好环保网站建设多少钱