C++ Linked List printing Crash

Question

I'm not new to programming, but learning C++. To do this, I'm implementing the "standard" data structures in the C++ language. I'm starting with Linked Lists. I understand how they work and all that. However, when I try to print out the list, it doesn't stop when it's supposed to. I set the last pointer to nullptr and all that and have researched this problem heavily on the internet, but I cannot find what I'm doing different from everyone else. Here's the code:

template<typename T>
void LinkedList<T>::print_list(){

    list_node<T> *pos = this->start;

    while(pos != nullptr){
       cout << "PRInting" <<pos->data<<endl <<pos->next;

        pos = pos->next;
    }
}

Here's the Full Code:

#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED

#include <iostream>

using std::cout;
using std::endl;
template <class T>
struct list_node{
    T data;
    list_node<T> *next;
};
template <class T>
class LinkedList{
private:
    list_node<T> *start;

public:
    LinkedList();
    LinkedList(T firstData);
    ~LinkedList();
    void insert_item(T item);
    void delete_item(T item);
    list_node<T>* search_list();
    void print_list();
};



//constructors and destructor
template <typename T>
LinkedList<T>::LinkedList(){
    this->start = nullptr;
}
template <typename T>
LinkedList<T>::LinkedList(T firstData){
    list_node<T> newNode = {
        firstData,
        nullptr
    };
    this->start = &newNode;
    cout <<"Constructor" <<this->start->data<<endl;
}
template <typename T>
LinkedList<T>::~LinkedList(){
    this->start = nullptr;
}

//Debugging print function
template<typename T>
void LinkedList<T>::print_list(){
    list_node<T> *pos = this->start;
    while(pos != nullptr){
        cout << "PRInting" <<pos->data<<endl <<pos->next;
        pos = pos->next;
    }
    //cout << pos->data;
}


//Operations on Linked Lists
template <typename T>
void LinkedList<T>::insert_item(T item){
    list_node<T> *insertNode;
    insertNode->data = item;
    insertNode->next = this->start;
    this->start = insertNode;
    cout << "After insert " <<this->start->data << '\n' << this->start->next->data<<endl;
}

#endif // LINKEDLIST_H_INCLUDED

_I set the last pointer to nullptr_ We cannot see that, from the example presented. Please provide [mcve]. — Algirdas Preidžius, Feb 01 '17 at 16:05
That function looks fine to me. The problem is definitely elsewhere. — R Sahu, Feb 01 '17 at 16:09
If your last outputed line before the crash isn't 0 then you don't have a null terminated list — user3853544, Feb 01 '17 at 16:11
Some of those cout statements are for my debugging purposes only. — SH7890, Feb 01 '17 at 16:30

score 4 · Accepted Answer · answered Feb 01 '17 at 16:41

You have 2 different problems regarding node insertion, that are present in your code.

In your constructor: You are creating a local variable newNode, and storing its memory address in this->start. However, newNode object will be destroyed upon leaving the scope of the constructor, and trying to dereference it will result in UB (undefined behavior). You should allocate the node dynamically, so it won't get destroyed once it leaves the scope:
```
LinkedList<T>::LinkedList(T firstData){
    this->start = new list_node<T>;
    this->start->data = firstData;
    this->start->next = nullptr;
    cout <<"Constructor" <<this->start->data<<endl;
}
```

In your insert_item procedure: You are dereferencing local pointer insertNode, even though, no actual memory was allocated for it, and dereferencing it results in UB, as well. Correct version would look like:

template <typename T>
void LinkedList<T>::insert_item(T item){
    list_node<T> *insertNode = new list_node<T>;
    insertNode->data = item;
    insertNode->next = this->start;
    this->start = insertNode;
    cout << "After insert " <<this->start->data << '\n' << this->start->next->data<<endl;
    }

And now, since we are doing dynamic memory allocation, we need to free it in the destructor (C++ has no garbage collection), so simply assigning start to nullptr won't be enough:

template <typename T>
    LinkedList<T>::~LinkedList(){
        list_node<T> *pos = this->start;
        while (pos != nullptr){
            list_node<T>* nextPos = pos->next;
            delete pos;
            pos = nextPos;
        }
    }

Better than my answer so I'm going to piggy-back with a comment: Rather than using a dummy node as the end of the linked list, consider instead setting the next member of the last node `null_ptr` and testing for that. Less storage used and one less `node->next` iteration. An easy way to start on this is to add a constructor to `list_node`: `list_node(T & data) : data(data), next(nullptr){}` Now every node created has data and starts off pointing to no next node and you can slap it on the end of the list or at the beginning or in the middle without worrying that you forgot to end the list. — user4581301, Feb 01 '17 at 16:52
That works. Thanks. And, if I may clarify for my own sakes. The 'new' keyword dynamically allocates the memory. If memory is not dynamically allocated for an object, it will be destroyed once it goes out of scope? — SH7890, Feb 01 '17 at 16:53
@Shadow1356 you got it. Just remember to `delete` what you `new`. [Smart pointers can help with this](http://stackoverflow.com/questions/106508/what-is-a-smart-pointer-and-when-should-i-use-one) — user4581301, Feb 01 '17 at 16:55

C++ Linked List printing Crash

1 Answers1