Trouble implementing a templated singly linked list

Question

I'm trying to implement a templated singly linked list and I'm fairly new to C++

#include <iostream>
#include <string>

#define NEWL "\n"
#define PRINT(s) std::cout << s
#define PRINTL(s) std::cout << s << NEWL
#define PRINTERR(e) std::cerr << e << NEWL

////// Class for a Node
template<class Data> class Node {
    Node<Data>*  next_ptr;
    Data         data;
public:
    Node(Node<Data>* nxt_ptr)           :next_ptr(nxt_ptr) {};
    Node(Data d, Node<Data>* nxt_ptr)   :data(d), next_ptr(nxt_ptr) {};

    Node<Data>* get_next() { return next_ptr; }
    Data&       get_data() { return data; }

    friend std::ostream& operator<<(std::ostream& out, const Node<Data>& node) {
        out << node.data;
        return out;
    };
};


////// Class for a SinglyLinkedList
template<class Data> class SLinkedList {
    Node<Data>* head_ptr;
    int         max_size;

public:
    SLinkedList() : head_ptr(nullptr) {};

    bool is_empty() {

        return head_ptr == nullptr;

    };
    bool is_full() {

        return get_size() == max_size;

    };
    int get_size() {

        if (is_empty()) {
            return 0;
        }
        int count = 0;
        for (Node<Data>* it_ptr = head_ptr; it_ptr != nullptr; it_ptr = it_ptr->get_next()) { 
            count++; 
        }
        return count;

    };
    void add(Data d) {
        if (is_full()) {
            throw std::exception("List is full!");
        }
        Node<Data> new_node(d, head_ptr);
        head_ptr = &new_node;
    };
    void print_content() {
        int count = 1;
        PRINTL("This list contains:");
        for (Node<Data>* it_ptr = head_ptr; it_ptr != nullptr; it_ptr = it_ptr->get_next()) {
            PRINTL("\t["<< count << "]" << " at " << it_ptr << " : "  << *it_ptr);
            count++;
        }
    }
};

////// Main function
int main()
{

    SLinkedList<int> sll;
    sll.add(42);
    sll.print_content();

}

I can't get this to work. Somehow iterating the list with for-loops does not work. It always results in an Reading Access Violation Exception about a pointer to 0xCCCCCCD0 and I have no idea how to fix this.

I would like to mention (even though there is already a good answer) that `0xCCCCCCD0` is close to a magic debug code. Looks like the Microsoft Debug Runtime is telling you that you are using uninitialized stack memory: http://stackoverflow.com/a/127404/487892 Recognizing these debug magic numbers can help you in the future. — drescherjm, Apr 27 '16 at 15:18

NathanOliver · Accepted Answer · 2016-04-27T15:04:07.173

Your add function is incorrect

Node<Data> new_node(d, head_ptr);

creates a new function local Node in add. You then set head to the address of that local variable. When the function ends all local variables are destroyed so now head points to an object that no longer exists.

To fix that you need to use the new keyword to create a dynamic object that will live on after the function ends.

Node<Data>* new_node = new Node(d, head_ptr);
head_ptr = new_node;

The down side with this is you need to remember to call delete on all of the nodes you created in the list destructor.

You also have some other bugs in your code. You never set max_size in your constructor so using it at all except to give it a value is undefined behavior as we have no idea what the value of it is going to be. You also never increase the size of the list when you add nodes into the list.

Trouble implementing a templated singly linked list

1 Answers1