How to correctly make a nested custom linked list in C++

Question

I'm trying to create a nested linked list like this (list<list<list<Object> > >) with a custom singly linked list for an assignment. the problem is that I tested it and the program returns a "memory could not be read error" and terminates. This is the code I used to test it

int main (){
    List<List<List<int> > > thirdLevelNumbers;
    for(int i = 0; i < 10; i++){
        List<List<int> > secondLevelNumbers;
        for(int j = 0; j < 10; j++){
            List<int> firstLevelNumbers;
            for(int n = 0; n < 10; n++){
                firstLevelNumbers.push_front(n);
            }
            secondLevelNumbers.push_front(firstLevelNumbers);
        }
        thirdLevelNumbers.push_front(secondLevelNumbers);
    }
    cout << "processed!" << endl;
    system("PAUSE");
    return 0;
}

Then I tried with the stl list and it worked!

So, I was wondering if anyone here could help me understand what part of the code causes the error and how to solve it.

I use eclipse with gcc (GCC) 4.5.2 and this is my linked list's code so far:

template <class T> class List;

template <class T>
class node
{
   T info;
   node<T>* next;
   friend class List<T>;
};

template <class T>
class List
{
private:
         node<T>* First;
public:
         List()
         {
              First=NULL;
         };

         ~List()
         {
           node<T> *p;
           while (!isEmpty())
            {
                 p=First->next;
                 delete First;
                 First=p;
            };
         };

         bool isEmpty()
         {
           return First == NULL;
         };

         bool isFull()
         {
           node<T> *p;
           p=new node<T>;
           if (p==NULL)
              return true;
           else
             {
               delete p;
               return false;
             }
         };

         bool push_front(const T &Valor)
         {
            node<T>* newNode;
           if (!isFull())
              {
              newNode=new node<T>;
              newNode->info=Valor;
              newNode->next=First;
               First=newNode;
               return true;
              }
           else
               return false;
         };
};

Unrelated: `NULL` is not declared when you do ` List() { First = NULL; };` - use `nullptr` everywhere where you now have `NULL`.- You are also missing `#include ` — Ted Lyngmo, Jul 12 '21 at 16:02
`newNode->next=First; First=newNode;` , so, circular graph? do you have some unit tests for `push_front`, `isEmpty`, access functions, assignment, copy, etc? — pptaszni, Jul 12 '21 at 16:07
You may want to read [the rule of 5](https://en.cppreference.com/w/cpp/language/rule_of_three) too — Ted Lyngmo, Jul 12 '21 at 16:08
First start of with a simple list, like `List`. Build with sanitizers (if your compiler supports them), use e.g. Valgrind or similar tools. And most importantly build with extra warnings enabled, and treat them as errors. Once you get that simple list to work without any problems anywhere, try a more complex nested list (like `List>`). — Some programmer dude, Jul 12 '21 at 16:09
And if/when you get crashes, use a *debugger* to catch them, and locate where in your code they happens and examine variables and their values at the time of the crash. — Some programmer dude, Jul 12 '21 at 16:10
In addition to the answer, your `isFull` function is dubious. If new fails, it will throw an exception, not return a null pointer. So allocating an object, checking its nullness, and deleting it is not a proper way to query if there is memory remaining. (There is no portably good way to do that anyway, without preallocation.) — Chris Uzdavinis, Jul 12 '21 at 18:46
Thank you Chris Uzdavinis for that observation! I didn't know about that as I'm pretty new to C++, then the way to go for `isFull` would be to try/catch the block of code and catch the thrown exception? — Kevin Cheng, Jul 13 '21 at 01:39

score 1 · Accepted Answer · answered Jul 12 '21 at 16:09

You copy the inner list by value when you push it into the outer list:

         bool push_front(const T &Valor)
         {
            // ...
              newNode=new node<T>;
              newNode->info=Valor;

but your List does not have a copy constructor.

That means it will use the default generated copy constructor, which leaves you with two List instances having the same value for First (eg. the local object firstLevelNumbers and the node in secondLevelNumbers).

They'll both delete it when they go out of scope.

First, follow the rule of three (or five). You need to do this anyway to have any chance of your List behaving correctly as a value object.

Then, if you still have problems, it's time to learn how to debug your code. Write tests for simple cases and confirm they work before doing more complex things. Learn how to use your debugger, the address sanitizer, valgrind - whatever tools are available.

Thank you very much for your answer, that was indeed the issue! after applying the rule of three, the custom linked list template I created works perfectly. — Kevin Cheng, Jul 12 '21 at 18:23

How to correctly make a nested custom linked list in C++

1 Answers1