- C++
C++ 双向链表
- 2025-6-9 20:37:57 @
1. 双向链表基本概念
双向链表是一种数据结构,每个节点包含三个部分:
- 数据域:存储节点的值
- 前驱指针:指向前一个节点
- 后继指针:指向后一个节点
与单向链表相比,双向链表支持双向遍历(向前或向后),但需要更多内存存储指针。
2. 双向链表节点结构体定义
下面是双向链表节点的结构体定义,包含数据域和两个指针:
struct Node {
int data; // 存储节点的数据(这里使用 int 类型)
Node* prev; // 指向前驱节点的指针
Node* next; // 指向后继节点的指针
// 构造函数:方便创建节点时初始化数据
Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};
3. 双向链表的基本操作
3.1 创建双向链表
创建链表时,通常需要维护一个头指针(指向第一个节点)和尾指针(指向最后一个节点)。
class DoublyLinkedList {
private:
Node* head; // 头指针,指向链表第一个节点
Node* tail; // 尾指针,指向链表最后一个节点
int size; // 链表长度
public:
// 构造函数:初始化空链表
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
// 析构函数:释放链表内存,防止内存泄漏
~DoublyLinkedList() {
clear();
}
};
3.2 在链表尾部添加节点
在尾部添加节点时,需要更新尾指针和相关节点的指针:
// 在链表尾部添加新节点
void append(int value) {
Node* newNode = new Node(value); // 创建新节点
if (tail == nullptr) {
// 如果链表为空,新节点既是头节点也是尾节点
head = tail = newNode;
} else {
// 将新节点连接到链表尾部
newNode->prev = tail;
tail->next = newNode;
tail = newNode; // 更新尾指针
}
size++; // 链表长度加1
}
3.3 在链表头部插入节点
在头部插入节点时,需要更新头指针和相关节点的指针:
// 在链表头部插入新节点
void prepend(int value) {
Node* newNode = new Node(value); // 创建新节点
if (head == nullptr) {
// 如果链表为空,新节点既是头节点也是尾节点
head = tail = newNode;
} else {
// 将新节点连接到链表头部
newNode->next = head;
head->prev = newNode;
head = newNode; // 更新头指针
}
size++; // 链表长度加1
}
3.4 删除指定值的第一个节点
删除节点时,需要调整前驱和后继节点的指针,并释放内存:
// 删除第一个值为 target 的节点
bool remove(int target) {
Node* current = head;
while (current != nullptr) {
if (current->data == target) {
// 处理前驱节点的指针
if (current->prev != nullptr) {
current->prev->next = current->next;
} else {
// 如果删除的是头节点,更新头指针
head = current->next;
}
// 处理后继节点的指针
if (current->next != nullptr) {
current->next->prev = current->prev;
} else {
// 如果删除的是尾节点,更新尾指针
tail = current->prev;
}
delete current; // 释放节点内存
size--; // 链表长度减1
return true; // 删除成功
}
current = current->next; // 移动到下一个节点
}
return false; // 未找到目标值
}
3.5 遍历链表(正向和反向)
双向链表支持双向遍历,通过头指针或尾指针开始:
// 正向遍历链表并打印所有元素
void printForward() const {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
// 反向遍历链表并打印所有元素
void printBackward() const {
Node* current = tail;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}
3.6 清空链表
清空链表时,需要释放所有节点的内存,防止内存泄漏:
// 清空链表,释放所有节点内存
void clear() {
Node* current = head;
while (current != nullptr) {
Node* nextNode = current->next; // 保存下一个节点
delete current; // 释放当前节点
current = nextNode; // 移动到下一个节点
}
head = tail = nullptr; // 重置头指针和尾指针
size = 0; // 链表长度置为0
}
4. 使用示例
下面是一个使用双向链表的简单示例:
#include <iostream>
int main() {
DoublyLinkedList list;
// 在尾部添加节点
list.append(10);
list.append(20);
list.append(30);
// 在头部插入节点
list.prepend(5);
// 打印链表(正向和反向)
std::cout << "Forward traversal: ";
list.printForward(); // 输出: 5 10 20 30
std::cout << "Backward traversal: ";
list.printBackward(); // 输出: 30 20 10 5
// 删除节点
list.remove(20);
std::cout << "After removing 20: ";
list.printForward(); // 输出: 5 10 30
// 清空链表
list.clear();
std::cout << "After clearing: ";
list.printForward(); // 输出: (空)
return 0;
}
5. 总结
双向链表的优缺点:
- 优点:支持双向遍历,插入和删除操作效率高(如果已知节点位置)。
- 缺点:需要额外的内存存储前驱指针,实现复杂度较高。
双向链表适用于需要频繁双向访问数据的场景,如文本编辑器的撤销/重做功能、浏览器的历史记录等。
4 条评论
-
admin SU @ 2025-6-9 21:08:39
🧱 C++ 双向链表
一、什么是双向链表?
双向链表是一种线性数据结构,与单向链表不同的是:
- 每个节点都有两个指针:
prev
:指向前一个节点next
:指向后一个节点
这样设计的好处是:
- 可以从前往后遍历,也可以从后往前遍历
- 插入/删除操作更方便
二、基本结构定义
我们使用结构体来表示一个节点:
struct Node { int data; // 节点存储的数据 Node* prev; // 指向前一个节点的指针 Node* next; // 指向后一个节点的指针 };
三、初始化双向链表
我们通常用一个头指针指向链表的第一个节点。
Node* head = nullptr; // 头指针初始化为空
四、插入节点操作
我们将实现以下几种插入方式:
1. 在链表头部插入新节点
void insertAtHead(int value) { Node* newNode = new Node(); // 创建新节点 newNode->data = value; newNode->prev = nullptr; newNode->next = head; if (head != nullptr) { head->prev = newNode; // 原头节点的prev指向新节点 } head = newNode; // 更新头指针 }
2. 在链表尾部插入新节点
void insertAtTail(int value) { Node* newNode = new Node(); newNode->data = value; newNode->next = nullptr; if (head == nullptr) { // 如果链表为空,直接作为头节点 newNode->prev = nullptr; head = newNode; return; } Node* temp = head; while (temp->next != nullptr) { // 找到最后一个节点 temp = temp->next; } temp->next = newNode; newNode->prev = temp; }
3. 在指定值之后插入新节点
void insertAfter(int target, int value) { Node* temp = head; while (temp != nullptr && temp->data != target) { temp = temp->next; } if (temp == nullptr) { cout << "目标节点不存在!" << endl; return; } Node* newNode = new Node(); newNode->data = value; newNode->next = temp->next; newNode->prev = temp; if (temp->next != nullptr) { temp->next->prev = newNode; } temp->next = newNode; }
五、删除节点操作
删除指定值的节点
void deleteNode(int value) { Node* temp = head; while (temp != nullptr && temp->data != value) { temp = temp->next; } if (temp == nullptr) { cout << "未找到要删除的节点!" << endl; return; } if (temp->prev == nullptr) { // 删除的是头节点 head = temp->next; if (head != nullptr) { head->prev = nullptr; } } else { temp->prev->next = temp->next; if (temp->next != nullptr) { temp->next->prev = temp->prev; } } delete temp; // 释放内存 }
六、打印整个链表
正序打印
void printList() { Node* temp = head; while (temp != nullptr) { cout << temp->data << " <-> "; temp = temp->next; } cout << "NULL" << endl; }
逆序打印(从尾到头)
void printReverse() { Node* temp = head; if (temp == nullptr) return; while (temp->next != nullptr) { // 移动到尾节点 temp = temp->next; } while (temp != nullptr) { cout << temp->data << " <-> "; temp = temp->prev; } cout << "NULL" << endl; }
七、完整测试代码
#include <iostream> using namespace std; struct Node { int data; Node* prev; Node* next; }; Node* head = nullptr; // 插入到头部 void insertAtHead(int value) { Node* newNode = new Node(); newNode->data = value; newNode->prev = nullptr; newNode->next = head; if (head != nullptr) head->prev = newNode; head = newNode; } // 插入到尾部 void insertAtTail(int value) { Node* newNode = new Node(); newNode->data = value; newNode->next = nullptr; if (head == nullptr) { newNode->prev = nullptr; head = newNode; return; } Node* temp = head; while (temp->next != nullptr) temp = temp->next; temp->next = newNode; newNode->prev = temp; } // 在某个值后面插入 void insertAfter(int target, int value) { Node* temp = head; while (temp != nullptr && temp->data != target) temp = temp->next; if (temp == nullptr) { cout << "目标节点不存在!" << endl; return; } Node* newNode = new Node(); newNode->data = value; newNode->next = temp->next; newNode->prev = temp; if (temp->next != nullptr) temp->next->prev = newNode; temp->next = newNode; } // 删除某个值的节点 void deleteNode(int value) { Node* temp = head; while (temp != nullptr && temp->data != value) temp = temp->next; if (temp == nullptr) { cout << "未找到要删除的节点!" << endl; return; } if (temp->prev == nullptr) { head = temp->next; if (head != nullptr) head->prev = nullptr; } else { temp->prev->next = temp->next; if (temp->next != nullptr) temp->next->prev = temp->prev; } delete temp; } // 正序打印 void printList() { Node* temp = head; while (temp != nullptr) { cout << temp->data << " <-> "; temp = temp->next; } cout << "NULL" << endl; } // 逆序打印 void printReverse() { Node* temp = head; if (temp == nullptr) return; while (temp->next != nullptr) temp = temp->next; while (temp != nullptr) { cout << temp->data << " <-> "; temp = temp->prev; } cout << "NULL" << endl; } // 主函数测试 int main() { insertAtHead(10); // 10 insertAtTail(20); // 10 <-> 20 insertAtTail(30); // 10 <-> 20 <-> 30 insertAfter(20, 25); // 10 <-> 20 <-> 25 <-> 30 cout << "正序输出:" << endl; printList(); cout << "逆序输出:" << endl; printReverse(); deleteNode(25); // 删除25 cout << "删除25后输出:" << endl; printList(); return 0; }
八、运行结果示例
正序输出: 10 <-> 20 <-> 25 <-> 30 <-> NULL 逆序输出: 30 <-> 25 <-> 20 <-> 10 <-> NULL 删除25后输出: 10 <-> 20 <-> 30 <-> NULL
九、总结知识点
操作 时间复杂度 插入头部 O(1) 插入尾部 O(n) 插入中间 删除节点 查找节点 ⚠️ 提示:如果需要频繁在尾部操作,可以维护一个
tail
指针,提高效率!
✅ 学完你可以做什么?
- 实现 LRU 缓存机制
- 实现 文本编辑器中的撤销/重做功能
- 熟悉 C++ 中结构体和指针的操作
- 为后续学习 树、图等复杂结构 打下基础
继续讲解 带头节点的双向循环链表、STL中 list 的使用等内容。
欢迎随时告诉我 😊
祝你编程愉快,学有所成!🚀
- 每个节点都有两个指针:
-
2025-6-9 21:05:57@
在双向链表中实现插入操作时,需要同时调整前驱节点和后继节点的指针,确保链表的双向连接正确。
以下是几种常见插入场景的详细实现:
1. 在头部插入节点
插入新节点作为链表的头节点,时间复杂度为 O(1)。
void insertAtHead(int value) { Node* newNode = new Node(value); if (!head) { // 空链表:新节点既是头也是尾 head = tail = newNode; } else { // 1. 更新新节点的指针 newNode->next = head; head->prev = newNode; // 2. 更新头指针 head = newNode; } size++; }
2. 在尾部插入节点
插入新节点作为链表的尾节点,时间复杂度为 O(1)(若维护尾指针)。
void insertAtTail(int value) { Node* newNode = new Node(value); if (!tail) { // 空链表:新节点既是头也是尾 head = tail = newNode; } else { // 1. 更新新节点的指针 newNode->prev = tail; tail->next = newNode; // 2. 更新尾指针 tail = newNode; } size++; }
3. 在指定位置插入节点
在位置
pos
插入新节点(位置从 0 开始),时间复杂度为 O(n)(需先遍历到插入位置)。bool insertAtPosition(int pos, int value) { if (pos < 0 || pos > size) return false; // 检查位置有效性 if (pos == 0) { insertAtHead(value); // 头部插入 return true; } if (pos == size) { insertAtTail(value); // 尾部插入 return true; } // 找到插入位置的前驱节点 Node* current = head; for (int i = 0; i < pos - 1; i++) { current = current->next; } // 创建新节点并插入 Node* newNode = new Node(value); newNode->next = current->next; newNode->prev = current; current->next->prev = newNode; current->next = newNode; size++; return true; }
4. 关键步骤解析
插入操作的核心是调整四个指针:
- 新节点的前驱指针(
newNode->prev
) - 新节点的后继指针(
newNode->next
) - 前驱节点的后继指针(
prevNode->next
) - 后继节点的前驱指针(
nextNode->prev
)
示例:在节点 B 和 C 之间插入新节点 X
// 假设 B 和 C 已存在,需要插入 X Node* B = ...; Node* C = B->next; Node* X = new Node(value); // 1. 更新 X 的指针 X->prev = B; X->next = C; // 2. 更新 B 和 C 的指针(顺序不能颠倒) B->next = X; C->prev = X;
5. 插入操作的注意事项
- 处理空链表:插入首个节点时,需同时更新头指针和尾指针。
- 边界检查:插入位置必须有效(
0 ≤ pos ≤ size
)。 - 指针更新顺序:插入中间位置时,先更新新节点的指针,再更新相邻节点的指针。
- 维护尾指针:在尾部插入时,需更新尾指针。
6. 完整示例代码
以下是一个包含插入操作的双向链表实现:
#include <iostream> struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; class DoublyLinkedList { private: Node* head; Node* tail; int size; public: DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {} // 头部插入 void insertAtHead(int value) { Node* newNode = new Node(value); if (!head) { head = tail = newNode; } else { newNode->next = head; head->prev = newNode; head = newNode; } size++; } // 尾部插入 void insertAtTail(int value) { Node* newNode = new Node(value); if (!tail) { head = tail = newNode; } else { newNode->prev = tail; tail->next = newNode; tail = newNode; } size++; } // 指定位置插入 bool insertAtPosition(int pos, int value) { if (pos < 0 || pos > size) return false; if (pos == 0) { insertAtHead(value); return true; } if (pos == size) { insertAtTail(value); return true; } Node* current = head; for (int i = 0; i < pos - 1; i++) { current = current->next; } Node* newNode = new Node(value); newNode->next = current->next; newNode->prev = current; current->next->prev = newNode; current->next = newNode; size++; return true; } // 打印链表 void print() const { Node* current = head; while (current) { std::cout << current->data << " "; current = current->next; } std::cout << std::endl; } };
7. 使用示例
int main() { DoublyLinkedList list; list.insertAtHead(10); // 链表: 10 list.insertAtTail(30); // 链表: 10 <-> 30 list.insertAtPosition(1, 20); // 链表: 10 <-> 20 <-> 30 list.print(); // 输出: 10 20 30 return 0; }
总结
双向链表的插入操作需要同时维护前驱和后继指针,确保链表的连贯性。通过合理调整指针顺序和边界条件处理,可以高效实现插入功能。
- 新节点的前驱指针(
-
2025-6-9 21:05:00@
双向链表和单向链表是两种常见的链表结构,它们的主要区别在于节点的连接方式和功能特性。
以下是它们的核心差异:
1. 结构差异
单向链表
- 节点结构:每个节点包含 数据域 和 后继指针(next),指向下一个节点。
- 方向:只能从 头节点 开始,沿
next
指针单向遍历,无法反向访问。
// 单向链表节点示例 struct Node { int data; Node* next; };
双向链表
- 节点结构:每个节点包含 数据域、前驱指针(prev) 和 后继指针(next)。
- 方向:支持 双向遍历,既可以从头节点向后访问,也可以从尾节点向前访问。
// 双向链表节点示例 struct Node { int data; Node* prev; // 指向前驱节点 Node* next; // 指向后继节点 };
2. 核心操作对比
操作 单向链表 双向链表 插入/删除头部 时间复杂度 O(1),需修改 2 个指针 插入/删除尾部 时间复杂度 O(n)(需遍历到尾节点) 时间复杂度 O(1)(直接通过尾指针操作) 插入/删除中间节点 需先遍历找到前驱节点,时间复杂度 O(n) 若已知节点位置,时间复杂度 O(1) 反向遍历 不支持 支持(通过 prev
指针)3. 内存占用
- 单向链表:每个节点只需存储一个指针,内存占用少。
- 双向链表:每个节点需额外存储一个
prev
指针,内存开销更大。
4. 使用场景
- 单向链表:适用于只需单向遍历的场景,如栈、哈希表的冲突链。
- 双向链表:适用于需要双向遍历或频繁操作尾部的场景,如:
- 浏览器历史记录(前进/后退)
- 文本编辑器的撤销/重做功能
- 操作系统的任务调度队列
5. 示例对比:删除尾部节点
单向链表
// 单向链表删除尾节点(需遍历整个链表) void removeTail() { if (!head) return; if (!head->next) { // 只有一个节点 delete head; head = nullptr; return; } Node* current = head; while (current->next->next) { // 找到倒数第二个节点 current = current->next; } delete current->next; current->next = nullptr; }
双向链表
// 双向链表删除尾节点(直接通过 tail 指针操作) void removeTail() { if (!tail) return; Node* temp = tail; tail = tail->prev; if (tail) tail->next = nullptr; else head = nullptr; // 链表为空 delete temp; }
总结选择建议
- 选单向链表:若只需单向遍历,且内存紧张。
- 选双向链表:若需双向遍历或频繁操作尾部,且内存充足。
双向链表通过增加指针灵活性提升了操作效率,但牺牲了更多内存空间。
-
2025-6-9 21:04:09@
#include<iostream> using namespace std; struct Node { int data; // 存储节点的数据(这里使用 int 类型) Node* prev; // 指向前驱节点的指针 Node* next; // 指向后继节点的指针 // 构造函数:方便创建节点时初始化数据 Node(int value) : data(value), prev(nullptr), next(nullptr) {} }; struct DoublyLinkedList { private: Node* head; // 头指针,指向链表第一个节点 Node* tail; // 尾指针,指向链表最后一个节点 int size; // 链表长度 public: // 在链表尾部添加新节点 void append(int value) { Node* newNode = new Node(value); // 创建新节点 if (tail == nullptr) { // 如果链表为空,新节点既是头节点也是尾节点 head = tail = newNode; } else { // 将新节点连接到链表尾部 newNode->prev = tail; tail->next = newNode; tail = newNode; // 更新尾指针 } size++; // 链表长度加1 } // 在链表头部插入新节点 void prepend(int value) { Node* newNode = new Node(value); // 创建新节点 if (head == nullptr) { // 如果链表为空,新节点既是头节点也是尾节点 head = tail = newNode; } else { // 将新节点连接到链表头部 newNode->next = head; head->prev = newNode; head = newNode; // 更新头指针 } size++; // 链表长度加1 } // 删除第一个值为 target 的节点 bool remove(int target) { Node* current = head; while (current != nullptr) { if (current->data == target) { // 处理前驱节点的指针 if (current->prev != nullptr) { current->prev->next = current->next; } else { // 如果删除的是头节点,更新头指针 head = current->next; } // 处理后继节点的指针 if (current->next != nullptr) { current->next->prev = current->prev; } else { // 如果删除的是尾节点,更新尾指针 tail = current->prev; } delete current; // 释放节点内存 size--; // 链表长度减1 return true; // 删除成功 } current = current->next; // 移动到下一个节点 } return false; // 未找到目标值 } // 正向遍历链表并打印所有元素 void printForward() const { Node* current = head; while (current != nullptr) { cout << current->data << " "; current = current->next; } cout << endl; } // 反向遍历链表并打印所有元素 void printBackward() const { Node* current = tail; while (current != nullptr) { cout << current->data << " "; current = current->prev; } cout << std::endl; } // 清空链表,释放所有节点内存 void clear() { Node* current = head; while (current != nullptr) { Node* nextNode = current->next; // 保存下一个节点 delete current; // 释放当前节点 current = nextNode; // 移动到下一个节点 } head = tail = nullptr; // 重置头指针和尾指针 size = 0; // 链表长度置为0 } // 构造函数:初始化空链表 DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {} // 析构函数:释放链表内存,防止内存泄漏 ~DoublyLinkedList() { clear(); } }; int main() { DoublyLinkedList list; // 在尾部添加节点 list.append(10); list.append(20); list.append(30); list.append(20); // 在头部插入节点 list.prepend(5); // 打印链表(正向和反向) cout << "Forward traversal: "; list.printForward(); // 输出: 5 10 20 30 cout << "Backward traversal: "; list.printBackward(); // 输出: 30 20 10 5 // 删除节点 list.remove(20); cout << "After removing 20: "; list.printForward(); // 输出: 5 10 30 // 清空链表 list.clear(); cout << "After clearing: "; list.printForward(); // 输出: (空) return 0; }
- 1