0

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.

9
  • 4
    What is a debugger and how can it help me diagnose problems? Commented Jul 31, 2024 at 6:49
  • 1
    There is lots of irrelevant code in the post. Please try to reduce it to a minimal reproducible example Commented Jul 31, 2024 at 6:50
  • 1
    reducing your code to the minimum will make it much simpler for you to read the code and to debug it. And if you have reduced it to the bare minimum and still cannot spot the issue you have a nice mre to post here Commented Jul 31, 2024 at 6:52
  • 3
    adding ... is not making it a reproducible example. THe code that is now in the question does not compile, hence does not produce wrong output. Commented Jul 31, 2024 at 6:57
  • 1
    @benhpark If I had to guess I would say that your extra node is added when you create the list (i.e. in the list constructor). Your code appears to assume that head is never nullptr so what happens when a list is created? Commented Jul 31, 2024 at 7:11

2 Answers 2

4

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.

Sign up to request clarification or add additional context in comments.

1 Comment

-1

Your iterator code does not account for the head node.

4 Comments

Sorry, could you clarify what you meant by iterator code?
I'm surprised it seems I need to explicate DCListNode<Type>* DCListIterator<Type>::Next().
That's not an helpful attitude @greybeard. If you can't be bothered to explain, please do not answer questions.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.