双向链表(Doubly Linked List)是一种链式数据结构,它的每个节点都包含三个部分:数据、指向前一个节点的指针(prev
),以及指向下一个节点的指针(next
)。与单向链表不同,双向链表允许从任意节点向前或向后遍历,提供了更灵活的操作方式。
双向链表的结构
双向链表的每个节点都有以下三个部分:
- 数据部分:存储节点中的实际数据。
- 前向指针 (
prev
):指向当前节点的前一个节点,头节点的prev
为nullptr
。 - 后向指针 (
next
):指向当前节点的下一个节点,尾节点的next
为nullptr
。
这种双指针的结构允许我们高效地在链表中进行插入、删除等操作。
双向链表的操作
- 插入操作:在双向链表中插入一个新节点时,需要更新前后两个节点的指针,因此插入操作比单向链表略复杂,但仍然能在 O(1) 时间内完成(假设已经找到插入点)。
- 删除操作:删除一个节点时,需要修改前后节点的指针,也需要处理边界条件,如删除头节点或尾节点。
- 遍历操作:可以从任意节点开始,向前或向后遍历链表。
C++ 实现
下面是一个简单的 C++ 双向链表实现,包含插入、删除、遍历等常用操作。
#include <iostream>struct Node {int data;Node* prev;Node* next;// 构造函数Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};class DoublyLinkedList {
private:Node* head;public:// 构造函数初始化空链表DoublyLinkedList() : head(nullptr) {}// 在链表头插入新节点void insertAtHead(int value) {Node* newNode = new Node(value);if (head != nullptr) {newNode->next = head;head->prev = newNode;}head = newNode;}// 在链表尾插入新节点void insertAtTail(int value) {Node* newNode = new Node(value);if (head == nullptr) {head = newNode;return;}Node* temp = head;while (temp->next != nullptr) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;}// 删除指定值的节点void deleteNode(int value) {Node* temp = head;while (temp != nullptr && temp->data != value) {temp = temp->next;}if (temp == nullptr) {std::cout << "Node with value " << value << " not found.\n";return;}if (temp->prev != nullptr) {temp->prev->next = temp->next;} else {head = temp->next;}if (temp->next != nullptr) {temp->next->prev = temp->prev;}delete temp;}// 正向遍历链表void traverseForward() {Node* temp = head;while (temp != nullptr) {std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl;}// 反向遍历链表void traverseBackward() {if (head == nullptr) return;Node* temp = head;while (temp->next != nullptr) {temp = temp->next;}while (temp != nullptr) {std::cout << temp->data << " ";temp = temp->prev;}std::cout << std::endl;}// 析构函数:释放内存~DoublyLinkedList() {Node* temp = head;while (temp != nullptr) {Node* next = temp->next;delete temp;temp = next;}}
};int main() {DoublyLinkedList dll;dll.insertAtHead(10);dll.insertAtHead(20);dll.insertAtTail(30);dll.insertAtTail(40);std::cout << "Forward traversal: ";dll.traverseForward(); // 输出: 20 10 30 40std::cout << "Backward traversal: ";dll.traverseBackward(); // 输出: 40 30 10 20dll.deleteNode(10);std::cout << "After deleting 10, forward traversal: ";dll.traverseForward(); // 输出: 20 30 40return 0;
}
代码说明
Node
结构体:每个节点包含data
、prev
和next
三个成员变量,用于存储节点的数据和链表的双向连接。DoublyLinkedList
类:insertAtHead
:在链表头插入节点,注意要更新新头节点和原头节点的指针。insertAtTail
:遍历链表到末尾,然后在尾部插入节点。deleteNode
:找到目标节点,修改前后节点的指针,使链表跳过该节点。traverseForward
和traverseBackward
:分别用于正向和反向遍历链表。
- 内存管理:链表析构函数会遍历链表并释放所有节点,避免内存泄漏。
应用场景
双向链表广泛应用于需要双向遍历或频繁插入、删除操作的场景,比如:
- 浏览器历史记录:允许用户前进和后退浏览网页。
- 音乐播放列表:可以向前或向后切换歌曲。
- 内存管理:操作系统的内存块分配常常使用双向链表进行管理。
通过使用双向链表,可以提高程序处理数据的灵活性和效率。在 C++ 中实现双向链表,既考验了对指针操作的掌握,也有助于理解动态数据结构的原理。