双向链表（Doubly Linked List）是一种常见的数据结构，它在每个节点中保存指向前驱节点和后继节点的指针，使得在任意方向上都可以高效地遍历。本文将通过一个完整的示例，演示如何在 C++ 中实现双向链表的遍历功能，并讨论不同遍历方式的实现细节。
1. 双向链表节点结构
template <typename T>
struct Node {
T data; // 存储的数据
Node* prev; // 指向前驱节点
Node* next; // 指向后继节点
Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};2. 双向链表类设计
template <typename T>
class DoublyLinkedList {
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), sz(0) {}
~DoublyLinkedList();
void push_back(const T& val);
void push_front(const T& val);
void pop_back();
void pop_front();
// 关键的遍历接口
void traverse_forward() const;
void traverse_backward() const;
void traverse_by_index() const; // 随机访问方式
size_t size() const { return sz; }
private:
Node <T>* head;
Node <T>* tail;
size_t sz;
};3. 基本操作实现
template <typename T>
DoublyLinkedList <T>::~DoublyLinkedList() {
Node <T>* cur = head;
while (cur) {
Node <T>* next = cur->next;
delete cur;
cur = next;
}
}
template <typename T>
void DoublyLinkedList <T>::push_back(const T& val) {
Node <T>* n = new Node<T>(val);
if (!tail) { // 空链表
head = tail = n;
} else {
tail->next = n;
n->prev = tail;
tail = n;
}
++sz;
}
template <typename T>
void DoublyLinkedList <T>::push_front(const T& val) {
Node <T>* n = new Node<T>(val);
if (!head) {
head = tail = n;
} else {
n->next = head;
head->prev = n;
head = n;
}
++sz;
}
template <typename T>
void DoublyLinkedList <T>::pop_back() {
if (!tail) return;
Node <T>* toDel = tail;
tail = tail->prev;
if (tail) tail->next = nullptr;
else head = nullptr; // 删完后链表为空
delete toDel;
--sz;
}
template <typename T>
void DoublyLinkedList <T>::pop_front() {
if (!head) return;
Node <T>* toDel = head;
head = head->next;
if (head) head->prev = nullptr;
else tail = nullptr;
delete toDel;
--sz;
}4. 遍历实现
4.1 顺序遍历（头到尾）
template <typename T>
void DoublyLinkedList <T>::traverse_forward() const {
std::cout << "Forward traversal: ";
for (Node <T>* cur = head; cur; cur = cur->next)
std::cout << cur->data << ' ';
std::cout << '\n';
}4.2 逆序遍历（尾到头）
template <typename T>
void DoublyLinkedList <T>::traverse_backward() const {
std::cout << "Backward traversal: ";
for (Node <T>* cur = tail; cur; cur = cur->prev)
std::cout << cur->data << ' ';
std::cout << '\n';
}4.3 通过索引访问遍历（示例：按偶数索引访问）
template <typename T>
void DoublyLinkedList <T>::traverse_by_index() const {
std::cout << "Index-based traversal (even indices): ";
Node <T>* cur = head;
size_t idx = 0;
while (cur) {
if (idx % 2 == 0)
std::cout << cur->data << ' ';
cur = cur->next;
++idx;
}
std::cout << '\n';
}说明
由于链表不是随机访问结构，traverse_by_index仅是演示如何在遍历时结合索引做筛选；若真正需要随机访问，可考虑将链表转为数组或向量。
5. 完整示例
int main() {
DoublyLinkedList <int> list;
for (int i = 1; i <= 10; ++i) list.push_back(i);
list.traverse_forward(); // 1 2 3 4 5 6 7 8 9 10
list.traverse_backward(); // 10 9 8 7 6 5 4 3 2 1
list.traverse_by_index(); // 1 3 5 7 9
list.pop_front(); // 删除头节点
list.traverse_forward(); // 2 3 4 5 6 7 8 9 10
list.pop_back(); // 删除尾节点
list.traverse_backward(); // 9 8 7 6 5 4 3 2
return 0;
}6. 性能与空间分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
push_back / push_front |
O(1) | O(1) |
pop_back / pop_front |
O(1) | O(1) |
| 顺序遍历 | O(n) | O(1) |
| 逆序遍历 | O(n) | O(1) |
| 通过索引筛选遍历 | O(n) | O(1) |
双向链表的优势在于 常数时间内插入与删除，但不支持 O(1) 随机访问。如果需要频繁随机访问，建议使用 std::vector 或 std::deque。
7. 进阶思考
-
双向链表与
std::list的区别
std::list在 STL 中实现了双向链表，已提供完备的迭代器、算法支持与异常安全。自定义实现可用于学习和特殊需求（如自定义内存池、非标准节点布局）。 -
使用智能指针
可以将Node的指针改为std::unique_ptr与std::weak_ptr，实现更安全的内存管理，避免手动delete。 -
支持插入、删除任意位置
通过维护节点指针，可在 O(1) 内完成插入/删除操作，前提是已知目标节点。 -
多线程访问
双向链表天然不是线程安全的。若在多线程环境下使用，可结合读写锁或采用std::mutex保护关键路径。
总结
通过以上代码示例，您已掌握在 C++ 中实现双向链表遍历的完整流程。了解遍历方式与时间空间复杂度后，您可以根据实际应用场景选择合适的数据结构，或者在此基础上进一步扩展功能。祝编码愉快！