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

作者

双向链表（Doubly Linked List）是链表的一种变体，每个节点不仅包含指向后继节点的指针，还包含指向前驱节点的指针。相比单向链表，双向链表可以在 O(1) 时间内在任意方向上移动节点，极大地方便了插入、删除以及遍历等操作。本文将通过代码示例，介绍如何在 C++ 中实现双向链表，并展示前向遍历、后向遍历以及常见操作的实现方式。

1. 设计节点结构

struct Node {
    int data;          // 数据域
    Node* prev;        // 指向前驱节点
    Node* next;        // 指向后继节点

    // 构造函数
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

每个 Node 拥有 prev 与 next 两个指针，分别指向链表的前后节点。我们这里以整型数据为例。

2. 双向链表类的基本框架

class DoublyLinkedList {
private:
    Node* head;  // 指向链表头
    Node* tail;  // 指向链表尾
    size_t size; // 链表长度

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    ~DoublyLinkedList();

    void push_back(int val);   // 在尾部插入
    void push_front(int val);  // 在头部插入
    void pop_back();           // 删除尾部
    void pop_front();          // 删除头部

    void traverse_forward() const;  // 前向遍历
    void traverse_backward() const; // 后向遍历

    void print_debug() const; // 打印链表（前向）
};

3. 析构函数：清理内存

DoublyLinkedList::~DoublyLinkedList() {
    while (head) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

遍历 head，逐个 delete 节点，确保不出现内存泄漏。

4. 插入操作

4.1 在尾部插入

void DoublyLinkedList::push_back(int val) {
    Node* newNode = new Node(val);
    if (!tail) { // 空链表
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    ++size;
}

4.2 在头部插入

void DoublyLinkedList::push_front(int val) {
    Node* newNode = new Node(val);
    if (!head) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
    ++size;
}

5. 删除操作

5.1 删除尾部

void DoublyLinkedList::pop_back() {
    if (!tail) return;
    Node* temp = tail;
    if (head == tail) { // 只有一个节点
        head = tail = nullptr;
    } else {
        tail = tail->prev;
        tail->next = nullptr;
    }
    delete temp;
    --size;
}

5.2 删除头部

void DoublyLinkedList::pop_front() {
    if (!head) return;
    Node* temp = head;
    if (head == tail) {
        head = tail = nullptr;
    } else {
        head = head->next;
        head->prev = nullptr;
    }
    delete temp;
    --size;
}

6. 遍历操作

6.1 前向遍历

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

6.2 后向遍历

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

7. 调试打印（仅前向）

void DoublyLinkedList::print_debug() const {
    std::cout << "链表长度: " << size << '\n';
    Node* curr = head;
    while (curr) {
        std::cout << "[" << curr->data << "] <-> ";
        curr = curr->next;
    }
    std::cout << "NULL\n";
}

8. 示例程序

int main() {
    DoublyLinkedList dll;

    // 插入
    for (int i = 1; i <= 5; ++i) dll.push_back(i);  // 1 2 3 4 5
    dll.push_front(0);                               // 0 1 2 3 4 5

    dll.print_debug();

    // 前向遍历
    dll.traverse_forward();

    // 后向遍历
    dll.traverse_backward();

    // 删除
    dll.pop_front();   // 移除 0
    dll.pop_back();    // 移除 5

    dll.print_debug();
    dll.traverse_forward();

    return 0;
}

输出示例

链表长度: 6
[0] <-> [1] <-> [2] <-> [3] <-> [4] <-> [5] NULL
前向遍历: 0 1 2 3 4 5 
后向遍历: 5 4 3 2 1 0 
链表长度: 4
[1] <-> [2] <-> [3] <-> [4] NULL
前向遍历: 1 2 3 4

9. 小结

  1. 双向链表通过 prev 指针实现后向导航，兼顾前向和后向遍历的需求。
  2. 插入/删除时只需修改相邻节点的指针，时间复杂度为 O(1)。
  3. 需要注意边界情况：空链表、单节点链表、尾/头节点的插入/删除。
  4. 对链表的维护（如内存释放）最好在析构函数里完成，防止泄漏。

通过上述实现，你可以在自己的 C++ 项目中灵活使用双向链表，满足对双向遍历、快速插入删除等场景的需求。祝编码愉快！

发表评论