【数据结构】双向链表(Doubly Linked List)
双向链表(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 40
std::cout << "Backward traversal: ";
dll.traverseBackward(); // 输出: 40 30 10 20
dll.deleteNode(10);
std::cout << "After deleting 10, forward traversal: ";
dll.traverseForward(); // 输出: 20 30 40
return 0;
}
代码说明
Node
结构体:每个节点包含data
、prev
和next
三个成员变量,用于存储节点的数据和链表的双向连接。DoublyLinkedList
类:insertAtHead
:在链表头插入节点,注意要更新新头节点和原头节点的指针。insertAtTail
:遍历链表到末尾,然后在尾部插入节点。deleteNode
:找到目标节点,修改前后节点的指针,使链表跳过该节点。traverseForward
和traverseBackward
:分别用于正向和反向遍历链表。
- 内存管理:链表析构函数会遍历链表并释放所有节点,避免内存泄漏。
应用场景
双向链表广泛应用于需要双向遍历或频繁插入、删除操作的场景,比如:
- 浏览器历史记录:允许用户前进和后退浏览网页。
- 音乐播放列表:可以向前或向后切换歌曲。
- 内存管理:操作系统的内存块分配常常使用双向链表进行管理。
通过使用双向链表,可以提高程序处理数据的灵活性和效率。在 C++ 中实现双向链表,既考验了对指针操作的掌握,也有助于理解动态数据结构的原理。