前言

這一期我們學(xué)習(xí)雙向循環(huán)鏈表。雙向循環(huán)鏈表不同于單鏈表，雙向循環(huán)鏈表是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它結(jié)合了雙向鏈表和循環(huán)鏈表的特點。

一、定義與結(jié)構(gòu)

雙向循環(huán)鏈表中的每個節(jié)點都包含三個部分：數(shù)據(jù)域（存儲數(shù)據(jù)）、前驅(qū)指針（指向前一個節(jié)點）和后繼指針（指向下一個節(jié)點）。此外，鏈表的頭節(jié)點和尾節(jié)點通過指針相互連接，形成一個閉環(huán)。這種結(jié)構(gòu)使得鏈表可以從任意一個節(jié)點開始遍歷整個鏈表。

二、特點與優(yōu)勢

雙向訪問：雙向鏈表允許從任意節(jié)點向前或向后遍歷，這使得在需要頻繁訪問鏈表前后節(jié)點的場景中，雙向鏈表比單向鏈表更加高效。
循環(huán)特性：雙向循環(huán)鏈表的頭尾相連，形成一個環(huán)，這使得在處理需要循環(huán)訪問所有節(jié)點的任務(wù)時，雙向循環(huán)鏈表比單向循環(huán)鏈表更加方便。
靈活性：由于節(jié)點之間通過指針相互連接，雙向循環(huán)鏈表在插入和刪除節(jié)點時具有較高的靈活性。

三、基本操作

創(chuàng)建鏈表：首先需要初始化頭節(jié)點，并設(shè)置其前驅(qū)指針和后繼指針都指向自己，以形成閉環(huán)。然后，根據(jù)用戶輸入或其他數(shù)據(jù)源，依次插入節(jié)點。
遍歷鏈表：可以從頭節(jié)點或任意節(jié)點開始遍歷整個鏈表。由于鏈表是循環(huán)的，因此遍歷過程會一直進(jìn)行，直到再次回到起始節(jié)點。
插入節(jié)點：在指定位置插入新節(jié)點時，需要調(diào)整新節(jié)點及其相鄰節(jié)點的前驅(qū)和后繼指針。
刪除節(jié)點：刪除指定節(jié)點時，需要調(diào)整其相鄰節(jié)點的前驅(qū)和后繼指針，并釋放被刪除節(jié)點的內(nèi)存空間。
查詢節(jié)點：根據(jù)節(jié)點位置或數(shù)據(jù)值查詢節(jié)點時，需要從頭節(jié)點開始遍歷鏈表，直到找到目標(biāo)節(jié)點或遍歷完整個鏈表。

四、應(yīng)用場景

雙向循環(huán)鏈表在需要頻繁訪問鏈表前后節(jié)點的場景中非常有用。例如，在任務(wù)調(diào)度、緩存管理、圖形界面元素管理等場景中，雙向循環(huán)鏈表可以提供高效的數(shù)據(jù)訪問和操作。

五、實現(xiàn)復(fù)雜度

雖然雙向循環(huán)鏈表提供了更多的靈活性和功能，但其實現(xiàn)復(fù)雜度也相對較高。在插入和刪除節(jié)點時，需要處理更多的指針操作，這可能會增加代碼復(fù)雜性和出錯風(fēng)險。因此，在實現(xiàn)雙向循環(huán)鏈表時，需要特別注意指針的正確性和內(nèi)存管理。

六、動態(tài)圖解

七、代碼模版（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());	//初始化虛擬頭結(jié)點，自己指向自己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的前驅(qū)和后繼節(jié)點，它們本身不變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);	//這里有四個箭頭代表四個方向，我們加入節(jié)點就是要處理好這四個箭頭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;
}

八、經(jīng)典例題

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());	//初始化虛擬頭結(jié)點，自己指向自己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的前驅(qū)和后繼節(jié)點，它們本身不變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);	//這里有四個箭頭代表四個方向，我們加入節(jié)點就是要處理好這四個箭頭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;
}

九、總結(jié)

綜上所述，雙向循環(huán)鏈表是一種功能強大且靈活的數(shù)據(jù)結(jié)構(gòu)，適用于需要頻繁訪問鏈表前后節(jié)點的場景。然而，其實現(xiàn)復(fù)雜度也相對較高，需要開發(fā)者具備扎實的編程基礎(chǔ)和內(nèi)存管理能力。

結(jié)語

當(dāng)前進(jìn)階的數(shù)據(jù)結(jié)構(gòu)比之前學(xué)的初級數(shù)據(jù)結(jié)構(gòu)要復(fù)雜了，希望大家一定要動手敲一遍代碼，敲完之后提交到例題里檢查一下是否正確，出現(xiàn)bug不用慌張，耐心差錯，這樣你的水平才能提升。

希望大家可以一鍵三連，后續(xù)我們一起學(xué)習(xí)，謝謝大家！！！