Doubly-Linked-List

**双向链表(Doubly-Linked List)** 双向链表是一种数据结构，它在单链表的基础上增加了前向指针，使得每个节点不仅知道下一个节点的地址，还知道上一个节点的地址。这种数据结构提供了在链表中向前和向后遍历节点的能力，而不仅仅是单向移动。 ### 1. 结构组成 一个双向链表节点通常包含以下部分： - 数据域（Data）：存储实际的数据。 - 后继指针（Next）：指向链表中的下一个节点。 - 前驱指针（Prev）：指向链表中的上一个节点。 例如，节点定义如下： ```c++ struct Node { int data; Node* next; Node* prev; }; ``` ### 2. 操作与优势 双向链表支持以下常见的操作： - **插入操作**：可以在链表的头部、尾部以及任意位置插入新节点，由于前向指针的存在，插入操作比单链表更高效。 - **删除操作**：同样可以在任意位置删除节点，删除操作也因为双向链接而变得更简单。 - **遍历操作**：可以从前向后或从后向前遍历链表，提供更大的灵活性。 - **反向遍历**：双向链表可以轻松地反向遍历，这是单链表无法做到的。 ### 3. 初始化与销毁 初始化一个双向链表通常包括创建头节点（通常不存储数据）并设置其前后指针为NULL。销毁链表则涉及遍历整个链表并释放每个节点的内存。 ```c++ // 初始化 Node* head = new Node(); head->next = nullptr; head->prev = nullptr; // 销毁 while (head) { Node* temp = head; head = head->next; delete temp; } ``` ### 4. 常见操作的实现 #### 插入节点 - **在头部插入**： ```c++ void insertAtHead(int value) { Node* newNode = new Node(); newNode->data = value; newNode->next = head; newNode->prev = nullptr; if (head != nullptr) { head->prev = newNode; } head = newNode; } ``` - **在尾部插入**： ```c++ void insertAtTail(int value) { Node* newNode = new Node(); newNode->data = value; newNode->next = nullptr; if (head == nullptr) { head = newNode; } else { Node* current = head; while (current->next != nullptr) { current = current->next; } current->next = newNode; newNode->prev = current; } } ``` #### 删除节点 - **按值删除**： ```c++ void deleteByValue(int value) { Node* current = head; while (current != nullptr) { if (current->data == value) { if (current->prev) { current->prev->next = current->next; } else { head = current->next; } if (current->next) { current->next->prev = current->prev; } delete current; return; } current = current->next; } } ``` ### 5. 应用场景 双向链表在许多场景下都有广泛的应用，如： - **实现高效迭代器**：在迭代器设计中，双向链表允许双向移动，提供更好的性能体验。 - **实现撤销/重做功能**：在文本编辑器或编程环境中，双向链表可以用于记录操作历史，方便进行撤销和重做。 - **缓存管理**：LRU（最近最少使用）缓存淘汰算法常使用双向链表来维护数据项的顺序。 ### 6. 性能分析 - **空间复杂度**：每个节点除了存储数据外，还需要额外的两个指针，因此空间开销比单链表大。 - **时间复杂度**：插入和删除操作的时间复杂度主要取决于找到插入或删除位置所需的时间，通常是O(n)，但比单链表在某些情况下的O(n)更快。 双向链表通过提供双向遍历的能力，弥补了单链表的一些不足，但同时也带来了额外的空间成本。在选择链表类型时，应根据具体应用场景和需求权衡其优缺点。