c++data-structureslinked-listdoubly-linked-listcircular-list

Why is there a trailing zero at the end of Doubly-Linked Circular Linked List in C++?


I have a Data Structure problem regarding a doubly-linked circular list in C++.

I've implemented a doubly linked circular list using class templates. When testing the circular nature of the list by iterating through more elements than the list contains, I'm encountering an unexpected behavior. Here's the code I'm working with:

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;
}

The issue occurs in the main function when testing the 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();
}

The expected output is

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

but the actual output is

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

As shown above, the list wraps around with an extra trailing zero at the end of the list. Is there something wrong with my data structure? If so, how can I fix it to wrap around from 5 to 1?

Edit: MRE supplied.


Solution

  • You are breaking the circular chain at each insertion. See added comments:

    // [...]
    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
    // [...]
    

    This leads later to UB as you somewhat dereference nullptr, which with your compiler and optimisation levels exhibit the unexpected behaviour you observe.

    Unrelated: your iterator should adhere to the idiomatic way to define iterators in C++ so one can use iterator_traits.