C++双向循环链表迭代出现多余末尾零的问题及解决

问题根源分析 #

输出1 2 3 4 5 0 1 2 3 4说明遍历过程中意外访问到了值为0的无效节点，之后才回到正常循环逻辑。大概率是以下两种情况导致：

• 链表的闭环维护错误：最后一个节点的next未指向第一个有效节点，而是指向了某个未初始化（默认值为0）的节点；
• 若使用了哨兵节点，遍历逻辑错误地包含了未赋值的哨兵节点。

最常见的错误是插入操作完成后，未正确维护首尾节点的双向循环指向关系。

修复方案 #

1. 确保双向循环链表的首尾节点正确互指：
   • 插入第一个节点时，让节点的next和prev都指向自身，形成闭环；
   • 后续插入节点时，更新尾节点的next、新节点的prev/next、头节点的prev，始终保持链表的循环特性；
2. 避免使用未初始化的节点，所有节点均通过动态分配创建并明确赋值；
3. 遍历逻辑从第一个有效节点开始，循环时仅访问有效节点。

完整代码实现 #

DCList.h（类模板声明） #

#ifndef DCLIST_H
#define DCLIST_H

template <typename T>
struct Node {
    T data;
    Node* next;
    Node* prev;
    Node(const T& val) : data(val), next(nullptr), prev(nullptr) {}
};

template <typename T>
class DCList {
private:
    Node<T>* head;
    size_t size;

public:
    DCList();
    ~DCList();
    void push_back(const T& val);
    void print_cyclic(int count); // 循环输出指定数量的元素
};

// 引入模板实现文件
#include "DCList.tpp"

#endif

DCList.tpp（模板实现） #

#include "DCList.h"
#include <iostream>

template <typename T>
DCList<T>::DCList() : head(nullptr), size(0) {}

template <typename T>
DCList<T>::~DCList() {
    if (head == nullptr) return;
    Node<T>* current = head->next;
    // 遍历循环链表释放节点，直到回到头节点
    while (current != head) {
        Node<T>* temp = current;
        current = current->next;
        delete temp;
    }
    delete head;
}

template <typename T>
void DCList<T>::push_back(const T& val) {
    Node<T>* new_node = new Node<T>(val);
    if (size == 0) {
        // 第一个节点，自身形成闭环
        head = new_node;
        new_node->next = head;
        new_node->prev = head;
    } else {
        // 获取当前尾节点（头节点的prev）
        Node<T>* tail = head->prev;
        tail->next = new_node;
        new_node->prev = tail;
        new_node->next = head;
        head->prev = new_node;
    }
    size++;
}

template <typename T>
void DCList<T>::print_cyclic(int count) {
    if (head == nullptr) return;
    Node<T>* current = head;
    for (int i = 0; i < count; ++i) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

main.cpp（测试代码） #

#include "DCList.h"

int main() {
    DCList<int> dclist;
    // 插入1至5
    for (int i = 1; i <= 5; ++i) {
        dclist.push_back(i);
    }
    // 循环输出10个元素
    dclist.print_cyclic(10);
    return 0;
}

代码说明 #

• 未使用哨兵节点，所有节点均为有效数据节点，避免误访问哨兵默认值的问题；
• push_back方法严格维护循环链表的闭环：首节点的prev指向尾节点，尾节点的next指向首节点；
• print_cyclic从首节点开始遍历，每次移动到下一个有效节点，输出结果为1 2 3 4 5 1 2 3 4 5，符合预期；
• 析构函数正确遍历循环链表并释放所有节点，避免内存泄漏。

内容的提问来源于stack exchange，提问作者benhpark