为什么C++中的双向循环链表末尾有一个尾随零？

Question

我有一个关于 C++ 中双向链接循环列表的数据结构问题。

我使用类模板实现了一个双向链接的循环列表。当通过迭代比列表包含的元素更多的元素来测试列表的循环性质时，我遇到了意外的行为。这是我正在使用的代码：

main.cpp

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

int main() {
    
    DCList<int> intList;

    // Insert elements
    std::cout << "Inserting elements 1 to 5 to the back of the list:\n";
    for (int i = 1; i <= 5; i++) {
        intList.InsertBack(i);
    }
    std::cout << "List: " << intList << std::endl;

    // Test circular nature
    std::cout << "\nTesting circular nature (printing 10 elements):\n";
    DCListIterator<int> circularIt(intList);
    for (int i = 0; i < 10; ++i) {
        std::cout << circularIt.getData() << " ";
        circularIt.Next();
    }
    std::cout << std::endl;

    return 0;
}

DCList.h

#ifndef DCLIST_H
#define DCLIST_H

#include <iostream>

//forward declarations
template <class Type> class DCList;
template <class Type> class DCListIterator;

template <class Type>
class DCListNode {
    friend class DCList<Type>;
    friend class DCListIterator<Type>;
    
    template <class T>
    friend std::ostream& operator<<(std::ostream& os, const DCList<T>& list);

  private:
    Type data;
    DCListNode *next;
    DCListNode *prev;

  public:
    DCListNode(Type element = Type(), DCListNode *n = nullptr, DCListNode *p = nullptr) 
        : data(element), next(n), prev(p) {}
};

template <class Type>
class DCList {
    friend class DCListIterator<Type>;
    
    template <class T>
    friend std::ostream& operator<<(std::ostream& os, const DCList<T>& list);

  public:
    DCList();

    void InsertFront(const Type &item);
    void InsertBack(const Type &item);
    void Insert(DCListNode<Type>* p, DCListNode<Type>* x);

  private:
    DCListNode<Type> *head;  // Head node
};

template <class Type>
class DCListIterator {
  public:
    DCListIterator(const DCList<Type> &l); //constructor
    Type getData() const;
    DCListNode<Type>* Next();
   
  private:
    const DCList<Type> &list;
    DCListNode<Type> *current;
};

// Declaration of the operator<< function
template <class Type>
std::ostream& operator<<(std::ostream& os, const DCList<Type>& list);

#include "DCList.tpp"

#endif // DCLIST_H

DCList.tpp

#include <stdexcept>

template <class Type>
DCList<Type>::DCList() {
    head = new DCListNode<Type>();
    head->next = head->prev = head;  // Circular structure
}

template <class Type>
void DCList<Type>::InsertBack(const Type &item) {
    DCListNode<Type>* newNode = new DCListNode<Type>(item);
    Insert(newNode, head);
}

template <class Type>
void DCList<Type>::Insert(DCListNode<Type>* p, DCListNode<Type>* x) {
    p->next = x;
    p->prev = x->prev;
    x->prev->next = p;
    x->prev = p;
}

// Definition of the operator<< function
template <class Type>
std::ostream& operator<<(std::ostream& os, const DCList<Type>& list) {
    DCListNode<Type>* current = list.head->next;
    if (current == list.head) {
        return os << "Empty List";
    }
    while (current != list.head) {
        os << current->data;
        if (current->next != list.head) {
            os << " <-> ";
        }
        current = current->next;
    }
    return os;
}

// DCListIterator implementations
template <class Type>
DCListIterator<Type>::DCListIterator(const DCList<Type> &l) : list(l), current(l.head->next) {}

template <class Type>
Type DCListIterator<Type>::getData() const {
    return current->data;
}

template <class Type>
DCListNode<Type>* DCListIterator<Type>::Next() {
    current = current->next;
    return current;
}

测试循环性质时，问题出现在主函数中：

std::cout << "\nTesting circular nature (printing 10 elements):\n";
DCListIterator<int> circularIt(intList);
for (int i = 0; i < 10; ++i) {
    std::cout << circularIt.getData() << " ";
    circularIt.Next();
}

预期输出是

Inserting elements 1 to 5 to the back of the list:
List: 1 <-> 2 <-> 3 <-> 4 <-> 5

Testing circular nature (printing 10 elements):
1 2 3 4 5 1 2 3 4 5

但实际输出是

Inserting elements 1 to 5 to the back of the list:
List: 1 <-> 2 <-> 3 <-> 4 <-> 5

Testing circular nature (printing 10 elements):
1 2 3 4 5 0 1 2 3 4

如上所示，列表环绕，列表末尾有一个额外的尾随零。我的数据结构有问题吗？如果是这样，我该如何修复它以从 5 环绕到 1？

编辑：MRE 提供。

Answer 1

每次插入都会破坏循环链。查看添加的评论：

// [...]
void DCList<Type>::InsertBack(const Type &item) {
    DCListNode<Type>* newNode = new DCListNode<Type>(item); // newNode prev and next are nullptr
    Insert(newNode, head);
}

template <class Type>
void DCList<Type>::Insert(DCListNode<Type>* p, DCListNode<Type>* x) {
    p->next = x;
    p->prev = x->prev; // x->prev is nullptr
    // p->prev is now nullptr, breaking the cycle
// [...]