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

前言

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

在这里插入图片描述

一、定义与结构

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

二、特点与优势

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

三、基本操作

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

四、应用场景

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

五、实现复杂度

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

六、动态图解

在这里插入图片描述

七、代码模版（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;
}