C++實現(xiàn)雙向鏈表代碼分析
前言:
前面文章分析了單向鏈表，并給出了python和C++實現(xiàn)：單鏈表從原理到實現(xiàn)，python和C++兩個版本
本文介紹的雙向鏈表是在單向鏈表基礎上的一個改進，每個節(jié)點指向其直接前驅和直接后繼節(jié)點。因此，從雙向鏈表的任意位置開始，都能訪問所有的節(jié)點。
一、雙向鏈表優(yōu)缺點
雙向鏈表的缺點：
從節(jié)點的結構上可以看出，雙向鏈表的所需的存儲空間大于單向鏈表。同時，對于插入和刪除等操作來說，雙向鏈表的節(jié)點操作更加復雜，涉及到節(jié)點的前后兩個節(jié)點。
雙向鏈表的節(jié)點：
對于雙向鏈表來說，它的每個節(jié)點要指向“直接前驅”和“直接后繼”，所以節(jié)點類需要含有兩個指針域。指向直接前驅的指針使用pre表示，指向后繼的指針使用next表示。
二、C++實現(xiàn)分析
（1）節(jié)點類
雙向鏈表的節(jié)點含有兩個指針域，即直接前驅pre和直接后繼next。節(jié)點類采用的是模板實現(xiàn)，這樣其所存儲的數(shù)據(jù)就不再依賴于特定類型。
template<class T>
class Node {
public:
?? ?Node() {}
?? ?Node *pre;
?? ?Node *next;
? ? // 由于data屬性是私有的
? ? // 所以采用get和set對data進行處理
?? ?void setData(T data) { this->data = data; }
?? ?T getData() { return this->data; }
private:
?? ?T data;
};（2）鏈表類分析
鏈表類應該包含基本的增、改、刪、查等操作，由于其各種功能的實現(xiàn)是很相似的，
所以下面給出了需要實現(xiàn)的典型函數(shù)：
- 構造函數(shù)：
- isEmpty()判斷是否為空；
- size()返回鏈表長度；
- insert()頭插、尾插、中間插入節(jié)點；
- delete()刪除節(jié)點；
- getNode()獲取節(jié)點；
- traversal()遍歷鏈表；
鏈表類的定義如下：
template<class P>
class DoubleLinkedList {
public:
?? ?DoubleLinkedList();
?? ?bool isEmpty();
?? ?Node<P> ?*getNode(int index);
?? ?int size();
?? ?void insert(int data, int index);
?? ?void traversal();
?? ?void remove(int index);
private:
?? ?Node<P> *head;
};（3）鏈表類構造函數(shù)
初始化時需要創(chuàng)建頭節(jié)點，作為頭指針：
template<class P>
DoubleLinkedList<P>::DoubleLinkedList() {
?? ?// 創(chuàng)建頭結點
?? ?head = new Node<P>();
?? ?head->pre = NULL;
?? ?head->next = NULL;
?? ?head->setData(666);
}（4）isEmpty()判斷是否為空
對于雙向鏈表來說，判斷是否為空只需要判斷頭指針是否指向其他Node節(jié)點：
template<class P>
bool DoubleLinkedList<P>::isEmpty() {
?? ?if (head->next == NULL) {
?? ??? ?return true;
?? ?}
?? ?else
?? ?{
?? ??? ?return false;
?? ?}
}（5）size()獲取鏈表長度
獲取鏈表長度時需要判斷鏈表是否為空，從而確定是否采用遍歷的方式計算鏈表的長度。
由于采用的不是循環(huán)鏈表，所以循環(huán)的結束條件是判斷是否指向空節(jié)點：
template<class P>
int DoubleLinkedList<P>::size() {
?? ?if (isEmpty()) {
?? ??? ?return 0;
?? ?}
?? ?else {
?? ??? ?int count = 0;
?? ??? ?Node<P> *current = head->next;
? ? ? ? ? ? // 循環(huán)結束條件
?? ??? ?while (current!=NULL)
?? ??? ?{
?? ??? ??? ?current = current->next;
?? ??? ??? ?count++;
?? ??? ?}
?? ??? ?return count;
?? ?}
}（6）getNode()獲取節(jié)點
在插入和刪除等操作中，需要頻繁的進行節(jié)點獲取操作。
所以應該封裝為單獨的函數(shù)用于節(jié)點獲取，如下：
template<class P>
Node<P> *DoubleLinkedList<P>::getNode(int index) {?
?? ?Node<P> *current = head;
?? ?int currentCount = 0;
? ? // 循環(huán)結束條件
?? ?while (currentCount<=index)
?? ?{
?? ??? ?current = current->next;
?? ??? ?currentCount++;
?? ?}
?? ?return current;
}（7）insert()插入節(jié)點
插入節(jié)點依舊包含頭插法，尾插法和任意位置的插入。插入操作與單向鏈表的最大區(qū)別在于節(jié)點的指針移動較為復雜，需要將插入位置前后兩個節(jié)點與新節(jié)點均建立聯(lián)系：
template<class P>
void DoubleLinkedList<P>::insert(int data, int index) {
?? ?Node<P> *node = new Node<P>();
?? ?node->setData(data);
?? ?// 1、列表為空時
?? ?if (isEmpty()) {
?? ??? ?head->next = node;
?? ??? ?node->pre = head;
?? ??? ?return;
?? ?}
?? ?// 2、頭插法
?? ?if (index == 0) {
?? ??? ?node->next = head->next;
?? ??? ?head->next->pre = node;
?? ??? ?node->pre = head;
?? ??? ?head->next = node;
?? ?}
?? ?// 3、尾插法
?? ?else if (index >= this->size() - 1) {
?? ??? ?// printf("index %d, size %d \n", index, this->size());
?? ??? ?Node<P> *temp = this->getNode(this->size()-1);
?? ??? ?temp->next = node;
?? ??? ?node->pre = temp;
?? ?}
?? ?// 4、任意位置插入
?? ?else
?? ?{
?? ??? ?Node<P> *pre = this->getNode(index);
?? ??? ?Node<P> *next = pre->next;
?? ??? ?node->next = pre->next;
?? ??? ?node->pre = pre;
?? ??? ?pre->next = node;
?? ??? ?node->next->pre = node;
?? ?}
}（8）、remove()刪除節(jié)點
前面已經(jīng)定義了用于獲取節(jié)點的getNode()函數(shù)，所以remove()函數(shù)只需要進行指針移動操作。
將所要刪除的節(jié)點的直接前驅節(jié)點和直接后繼節(jié)點相連：
template<class P>
void DoubleLinkedList<P>::remove(int index) {
?? ?// 保證索引有意義
?? ?if ((index < (this->size()-1)) && (index>0)) {
?? ??? ?Node<P> *node = this->getNode(index);
?? ??? ?Node<P> *pre = node->pre;
?? ??? ?Node<P> *next = node->next;
?? ??? ?pre->next = next;
?? ??? ?next->pre = pre;
?? ?}
}（9）traversal()遍歷鏈表函數(shù)
雖然可以從雙向鏈表的任一個節(jié)點開始遍歷整個鏈表，但是下面的實現(xiàn)依舊是從頭結點開始的，循環(huán)的結束依舊是指向空指針：
template<class P>
void DoubleLinkedList<P>::traversal() {
?? ?if (!isEmpty()) {
?? ??? ?Node<P> *current = head;
?? ??? ?while (current)
?? ??? ?{
?? ??? ??? ?cout << current->getData() << endl;
?? ??? ??? ?current = current->next;
?? ??? ?}
?? ?}
}?到此這篇關于C++實現(xiàn)雙向鏈表代碼分析的文章就介紹到這了,更多相關C++雙向鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
海量點位標注的出現(xiàn)，是為了解決普通設備點超過幾百個性能極速降低的問題。本文將介紹如何通過Qt實現(xiàn)海量點位標注功能，感興趣的可以了解一下2022-01-01
這篇文章主要為大家介紹了C++實現(xiàn)xml解析器示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
在本篇文章里小編給大家整理的是一篇關于c++實現(xiàn)簡單隨機數(shù)的代碼內容，有需要的朋友們可以跟著學習下。2021-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)猜數(shù)字小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01
在C++程序中開啟和禁用Windows設備的無線網(wǎng)卡的方法
這篇文章主要介紹了在C++程序中開啟和禁用Windows設備的無線網(wǎng)卡的方法,包括一些常見錯誤的分析與解決,需要的朋友可以參考下2016-03-03
這篇文章主要為大家介紹了C++關鍵字thread_local學習筆記,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10
這篇文章主要為大家詳細介紹了Linux下C語言實現(xiàn)俄羅斯方塊小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-07-07
這篇文章主要為大家詳細介紹了基于C語言實現(xiàn)簡單掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要介紹了C語言實現(xiàn)基于最大堆和最小堆的堆排序算法示例,分別是基于最大堆的升序排序和基于最小堆的降序排序實例,需要的朋友可以參考下2016-06-06
本文主要介紹 C語言函數(shù)指針的知識,這里整理了詳細的資料及示例代碼以便大家學習參考，有需要學習此部分知識的朋友可以參考下2016-08-08