【数据结构】双向链表（Doubly Linked List）

双向链表（Doubly Linked List）是一种链式数据结构，它的每个节点都包含三个部门：数据、指向前一个节点的指针（prev），以及指向下一个节点的指针（next）。与单向链表不同，双向链表答应从任意节点向前或向后遍历，提供了更灵活的操纵方式。
双向链表的结构

双向链表的每个节点都有以下三个部门：

• 数据部门：存储节点中的实际数据。
  
• 前向指针 (prev)：指向当前节点的前一个节点，头节点的 prev 为 nullptr。
  
• 后向指针 (next)：指向当前节点的下一个节点，尾节点的 next 为 nullptr。
  

这种双指针的结构答应我们高效地在链表中进行插入、删除等操纵。
双向链表的操纵

• 插入操纵：在双向链表中插入一个新节点时，需要更新前后两个节点的指针，因此插入操纵比单向链表略复杂，但仍然能在 O(1) 时间内完成（假设已经找到插入点）。
  
• 删除操纵：删除一个节点时，需要修改前后节点的指针，也需要处置处罚边界条件，如删除头节点或尾节点。
  
• 遍历操纵：可以从任意节点开始，向前或向后遍历链表。
  

C++ 实现

下面是一个简单的 C++ 双向链表实现，包含插入、删除、遍历等常用操纵。

1. #include <iostream>
3. struct Node {
4.     int data;
5.     Node* prev;
6.     Node* next;
8.     // 构造函数
9.     Node(int value) : data(value), prev(nullptr), next(nullptr) {}
10. };
12. class DoublyLinkedList {
13. private:
14.     Node* head;
16. public:
17.     // 构造函数初始化空链表
18.     DoublyLinkedList() : head(nullptr) {}
20.     // 在链表头插入新节点
21.     void insertAtHead(int value) {
22.         Node* newNode = new Node(value);
23.         if (head != nullptr) {
24.             newNode->next = head;
25.             head->prev = newNode;
26.         }
27.         head = newNode;
28.     }
30.     // 在链表尾插入新节点
31.     void insertAtTail(int value) {
32.         Node* newNode = new Node(value);
33.         if (head == nullptr) {
34.             head = newNode;
35.             return;
36.         }
37.         Node* temp = head;
38.         while (temp->next != nullptr) {
39.             temp = temp->next;
40.         }
41.         temp->next = newNode;
42.         newNode->prev = temp;
43.     }
45.     // 删除指定值的节点
46.     void deleteNode(int value) {
47.         Node* temp = head;
48.         while (temp != nullptr && temp->data != value) {
49.             temp = temp->next;
50.         }
51.         if (temp == nullptr) {
52.             std::cout << "Node with value " << value << " not found.\n";
53.             return;
54.         }
55.         if (temp->prev != nullptr) {
56.             temp->prev->next = temp->next;
57.         } else {
58.             head = temp->next;
59.         }
60.         if (temp->next != nullptr) {
61.             temp->next->prev = temp->prev;
62.         }
63.         delete temp;
64.     }
66.     // 正向遍历链表
67.     void traverseForward() {
68.         Node* temp = head;
69.         while (temp != nullptr) {
70.             std::cout << temp->data << " ";
71.             temp = temp->next;
72.         }
73.         std::cout << std::endl;
74.     }
76.     // 反向遍历链表
77.     void traverseBackward() {
78.         if (head == nullptr) return;
79.         Node* temp = head;
80.         while (temp->next != nullptr) {
81.             temp = temp->next;
82.         }
83.         while (temp != nullptr) {
84.             std::cout << temp->data << " ";
85.             temp = temp->prev;
86.         }
87.         std::cout << std::endl;
88.     }
90.     // 析构函数：释放内存
91.     ~DoublyLinkedList() {
92.         Node* temp = head;
93.         while (temp != nullptr) {
94.             Node* next = temp->next;
95.             delete temp;
96.             temp = next;
97.         }
98.     }
99. };
101. int main() {
102.     DoublyLinkedList dll;
103.     dll.insertAtHead(10);
104.     dll.insertAtHead(20);
105.     dll.insertAtTail(30);
106.     dll.insertAtTail(40);
108.     std::cout << "Forward traversal: ";
109.     dll.traverseForward(); // 输出: 20 10 30 40
111.     std::cout << "Backward traversal: ";
112.     dll.traverseBackward(); // 输出: 40 30 10 20
114.     dll.deleteNode(10);
115.     std::cout << "After deleting 10, forward traversal: ";
116.     dll.traverseForward(); // 输出: 20 30 40
118.     return 0;
119. }

复制代码

代码阐明

• Node 结构体：每个节点包含 data、prev 和 next 三个成员变量，用于存储节点的数据和链表的双向连接。
  
• DoublyLinkedList 类：
  
  
  
  • insertAtHead：在链表头插入节点，注意要更新新头节点和原头节点的指针。
    
  • insertAtTail：遍历链表到末端，然后在尾部插入节点。
    
  • deleteNode：找到目的节点，修改前后节点的指针，使链表跳过该节点。
    
  • traverseForward 和 traverseBackward：分别用于正向和反向遍历链表。
    
  
  
• 内存管理：链表析构函数会遍历链表并释放所有节点，制止内存走漏。
  

应用场景

双向链表广泛应用于需要双向遍历或频繁插入、删除操纵的场景，比如：

• 欣赏器汗青记载：答应用户前进和退却欣赏网页。
  
• 音乐播放列表：可以向前或向后切换歌曲。
  
• 内存管理：操纵系统的内存块分配常常利用双向链表进行管理。
  

通过利用双向链表，可以提高程序处置处罚数据的灵活性和效率。在 C++ 中实现双向链表，既磨练了对指针操纵的掌握，也有助于理解动态数据结构的原理。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。