Getting error while printing a link list in C++?

Question

I have written the following link list append, prepend and print methods for LinkedList:

class Node {
public:
    int data;
    Node *next;
    
    Node(int data) {
        this->data = data;
    }
};


class LinkedList {
private:
    Node *header;
    Node *tail;
    int size;
    
public:
    LinkedList() {
        header = NULL;
        tail = NULL;
        size = 0;
    }
    
    int getSize() {
        return size;
    }
    
    void append(int data) {
        Node *n = new Node(data);
        
        if (header == NULL) {
            header = n;
            tail = n;
        }
        else {
            tail->next = n;
            tail = n;
        }
        
        size++;
    }
    
    void prepend(int data) {
        Node *n = new Node(data);
        
        if (header == NULL) {
            header = n;
            tail = n;
        }
        else {
            Node *temp = header;
            header = n;
            n->next = temp;
        }
        
        size++;
    }
    
    void toString() {
        Node *temp = header;
        
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        
        cout << endl;
    }
};

int main()
{
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.toString();
    return 0;
}

But the program is giving bad access after reaching the last node while printing the list. What is the problem with this code? Can anyone please explain on this?

Answer 1

append() is not initializing the n->next member to NULL. You should do that initialization in Node's constructor, eg:

class Node {
public:
    int data;
    Node *next;
    
    Node(int data) {
        this->data = data;
        this->next = NULL; // <-- add this!
    }
};

Alternatively:

class Node {
public:
    int data;
    Node *next = nullptr;
    
    Node(int data) : data(data) {}
};

Or:

class Node {
public:
    int data;
    Node *next;
    
    Node(int data, Node *next = nullptr) : data(data), next(next) {}
};

---

That being said, your LinkedList is leaking nodes. You need to add a destructor to free the nodes. You should also add a copy constructor and a copy assignment operator, per the Rule of 3. And in C++11 and later, add a move constructor and a move assignment operator, per the Rule of 5.

Try this:

class Node {
public:
    int data;
    Node *next;
    
    Node(int data, Node *next = nullptr) : data(data), next(next) {}
};


class LinkedList {
private:
    Node *header = nullptr;
    Node *tail = nullptr;
    int size = 0;
    
public:
    LinkedList() = default;
    
    LinkedList(const LinkedList &src) : LinkedList() {
        Node *temp = src.header;
        while (temp) {
            append(temp->data);
            temp = temp->next;
        }
    }

    LinkedList(LinkedList &&src) : LinkedList() {
        std::swap(header, src.header);
        std::swap(tail, src.tail);
        std::swap(size, src.size);
    }

    ~LinkedList() {
        Node *temp = header;
        while (temp) {
            Node *n = temp->next;
            delete temp;
            temp = n;
        }
    }

    LinkedList& operator=(LinkedList src) {
        std::swap(header, src.header);
        std::swap(tail, src.tail);
        std::swap(size, src.size);
        return *this;
    }

    int getSize() const {
        return size;
    }
    
    void append(int data) {
        Node **temp = (tail) ? &(tail->next) : &header;
        *temp = new Node(data);
        tail = *temp;
        ++size;
    }
    
    void prepend(int data) {
        header = new Node(data, header);
        if (!tail) tail = header;
        ++size;
    }
    
    void toString() const {
        Node *temp = header;
        while (temp) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main()
{
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.toString();
    return 0;
}

Answer 2

You've forgotten to assign n->next in append(). I suggest that you add an argument to your Node constructor to not forget that:

class Node {
public:
    int data;
    Node *next;

    // make the constructor initialize both "data" and "next"
    Node(int data, Node* next) : 
        data(data), 
        next(next) 
    {}
};

With that, your append() and prepend() functions would have to supply the next node upon construction, making mistakes like this a little harder:

void append(int data) {
    Node *n = new Node(data, nullptr);
    
    if (header == nullptr) header = n;
    else                   tail->next = n;            
    
    tail = n;
    
    ++size;
}

void prepend(int data) {
    Node *n = new Node(data, header);
    
    if (header == nullptr) tail = n;
    header = n;
    
    ++size;
}

You also need to add a destructor to delete all the nodes to not leak memory.

Answer 3

You should always initialize the members of your class.

Node(int data)
: data(data)
, next(nullptr)
{
}