C++實現(xiàn)雙鏈表（Double Linked List）
語言這個東西不用真的會忘秉继， 我記得前前后后C++的基本語法我也看了好幾遍了片酝，一直沒有動手寫過什么東西京闰，所以一遍遍的看，一遍遍的忘... ...
正好最近在看數(shù)據(jù)結構廓俭，想著自己用C++來實現(xiàn)一下靠瞎，一方面是熟悉整個邏輯過程比庄，加深對數(shù)據(jù)結構的理解，另一方面乏盐，也熟悉一下C++佳窑。
雙鏈表與單鏈表相同，都是由結點（Node）組成父能，但結點結構有所不同神凑，結點中有一個數(shù)據(jù)域和兩個指針域，數(shù)據(jù)域存放結點中的數(shù)據(jù)法竞，一個指針域指向下一個結點的地址耙厚，另一個指針指向上一個結點的地址强挫。同單鏈表一樣岔霸，我們所實現(xiàn)的雙鏈表是帶有頭結點的。下圖是結點和雙鏈表結構的示意圖俯渤。
結點示意圖：
Node.png
雙鏈表示意圖：
Double Linked List.png
- 需要說明的是呆细，我的這個程序中的索引是從0開始的，而且默認數(shù)據(jù)都是正的
int類型八匠。- 雙鏈表是從單鏈表中擴充出來的絮爷，除了刪除結點（deleteByIndex）和增加結點（insertByIndex）以及雙鏈表的初始化創(chuàng)建（create）以外很多操作和單鏈表是相同的，這里就不再給出實現(xiàn)代碼了梨树。
單鏈表的類定義：
class List {
private:
class Node {
public:
int data;
Node *prior;
Node *next;
};
Node *head;
int length = 0;
public:
List();
void print();
void create(int n);
int getLength() const;
void insertByIndex(int index, int data);//在索引為index之前的位置插入數(shù)據(jù)為data的結點
void deleteByIndex(int index);//刪除索引為index的結點
};
類中的函數(shù)實現(xiàn)：
List::List() {
head = new Node;
head->data = 0;
head->next = nullptr;
head->prior = nullptr;
}
void List::print() {
Node *cur = head->next;
if (!length) {
cout << "鏈表為空坑夯！" << endl;
return;
}
cout << endl;
cout << "*******************" << endl;
cout << "鏈表中的元素為：" << endl;
while (cur) {
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
cout << "*******************" << endl;
}
void List::create(int n) {
Node *pre = head;
length = n;
int i = 1;
while (i <= n) {
cout << "請輸入第" << i << "個結點的數(shù)據(jù)：";
Node *cur = new Node;
cin >> cur->data;
++i;
pre->next = cur;
cur->prior = pre;
pre = cur;
cur->next = nullptr;
}
}
int List::getLength() const {
cout << "鏈表中的元素個數(shù)為：" << length << endl;
return length;
}
void List::insertByIndex(int index, int data) {
if (index < 0 || index >= length) {
cout << "索引位置不合法" << endl;
} else {
Node *cur = head;
int pos = 0;
while (pos != index) {
cur = cur->next;
++pos;
}
Node *temp = new Node;
temp->data = data;
temp->next = cur->next;
temp->prior = cur;
cur->next->prior = temp;
cur->next = temp;
++length;
cout << data << "插入成功！" << endl;
}
}
void List::deleteByIndex(int index) {
if (index < 0 || index >= length) {
cout << "索引輸入錯誤抡四！" << endl;
} else {
Node *cur = head;
int pos = 0;
while (pos != index) {
cur = cur->next;
++pos;
}
Node *temp = cur->next;
temp->next->prior = temp->prior;
temp->prior->next = temp->next;
delete temp;
--length;
cout << "刪除成功!" << endl;
}
}
測試代碼：
/*
* Software:Jetbrains clion 2022.1
* Created by xiaoxin_zh@foxmail.com
* Implementing Double Linked List with C++
*/
#include <iostram>
using std::cin;
using std::cout;
using std::endl;
int main() {
List list;
int n;
cout << "請輸入鏈表中的結點的個數(shù)：";
cin >> n;
list.create(n);
list.print();
list.getLength();
int index, data;
cout << "請輸入需要插入結點的位置索引和數(shù)值：";
cin >> index >> data;
list.insertByIndex(index, data);
list.print();
list.getLength();
int deleteIndex;
cout << "請輸入需要刪除結點的索引值：";
cin >> deleteIndex;
list.deleteByIndex(deleteIndex);
list.print();
list.getLength();
return 0;
}
注意：一定要注意在刪除和插入結點時的順序柜蜈，否則會發(fā)生“斷鏈”！
假設實現(xiàn)的原始單鏈表有3個結點指巡，數(shù)值分別為12淑履、23、34結構如圖所示：
create.png
在索引為2的前面插入一個數(shù)值為88的結點藻雪，其步驟如圖所示：
insert.png
刪除索引為1的結點秘噪，其步驟如圖所示：
delete.png
測試代碼執(zhí)行：
EXE.png
