C++ 中如何实现双向链表的遍历？

作者

在 C++ 中实现双向链表的遍历相对简单，但需要注意指针的正确使用以及遍历顺序。下面给出一个完整的示例代码，并逐步解释关键步骤。

#include <iostream>

// 双向链表节点结构体
template<typename T>
struct Node {
    T data;
    Node* prev; // 指向前一个节点
    Node* next; // 指向下一个节点

    Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};

// 双向链表类
template<typename T>
class DoublyLinkedList {
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), sz(0) {}

    // 插入到尾部
    void push_back(const T& val) {
        Node <T>* newNode = new Node<T>(val);
        if (!head) {  // 空链表
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        ++sz;
    }

    // 前向遍历
    void traverse_forward() const {
        std::cout << "Forward traversal: ";
        Node <T>* cur = head;
        while (cur) {
            std::cout << cur->data << ' ';
            cur = cur->next;
        }
        std::cout << '\n';
    }

    // 后向遍历
    void traverse_backward() const {
        std::cout << "Backward traversal: ";
        Node <T>* cur = tail;
        while (cur) {
            std::cout << cur->data << ' ';
            cur = cur->prev;
        }
        std::cout << '\n';
    }

    // 析构函数，释放内存
    ~DoublyLinkedList() {
        Node <T>* cur = head;
        while (cur) {
            Node <T>* tmp = cur->next;
            delete cur;
            cur = tmp;
        }
    }

private:
    Node <T>* head;
    Node <T>* tail;
    size_t sz;
};

int main() {
    DoublyLinkedList <int> list;
    for (int i = 1; i <= 5; ++i) {
        list.push_back(i * 10);   // 插入 10, 20, 30, 40, 50
    }

    list.traverse_forward();   // 前向遍历
    list.traverse_backward();  // 后向遍历

    return 0;
}

关键点说明

  1. 节点结构

    • 每个 Node 包含 data、prev 与 next。prev 指向前一个节点，next 指向后一个节点。

  2. 链表头尾维护

    • head 为链表第一个节点，tail 为链表最后一个节点。插入时要正确更新 next 与 prev，以及 head / tail 指针。

  3. 前向遍历

    • 从 head 开始，循环使用 next 指针，直到 nullptr。

  4. 后向遍历

    • 从 tail 开始，循环使用 prev 指针，直到 nullptr。

  5. 内存管理

    • 析构函数遍历整个链表并 delete 每个节点，防止内存泄漏。

  6. 模板化

    • 通过模板 T 让链表可以存储任意类型的数据。

扩展思路

  • 插入/删除：可以在任意位置插入或删除节点，只需调整相邻节点的 prev / next 指针即可。
  • 双向迭代器：实现 STL 兼容的双向迭代器，支持 ++、--、* 等运算符。
  • 异常安全：使用智能指针（std::unique_ptr）或 try-catch 结构，提升代码健壮性。

通过上述实现，你可以在 C++ 中轻松完成双向链表的前向和后向遍历，满足大多数基础数据结构需求。祝编码愉快！

发表评论