Trying to create a singly linked list in C++

Question

I am new to C++ and only know Java.

I am trying to create a singly linked list in C++ that will allow me to store integer numbers within the nodes. I want also to have the IntNode class and IntLinkedList class in separate files from the main file.

However, it's not working, I think it has something to do with my add() method for my IntLinkedList class.

This is the main.cpp file:

#include <iostream>
#include "IntNode.hpp"
#include "IntLinkedList.hpp"

int main(int argc, const char * argv[])
{
    //Initializing Variables
    IntLinkedList myList;
    
    myList.add(5);
    
    std::cout << "-------Done.------";
    
    return 0;
}

This is the IntNode.cpp file:

#include <stdio.h>
#include "IntNode.hpp"

IntNode::IntNode(int newData, IntNode *newLink)
{
    data = newData;
    link = newLink;
}

int IntNode::getData()
{
    return data;
}

IntNode IntNode::getLink()
{
    return *link;
}

void IntNode::setData(int newData)
{
    data = newData;
}
void IntNode::setLink(IntNode *newLink)
{
    link = newLink;
}

This is the IntNode.hpp header file:

#ifndef IntNode_h
#define IntNode_h

class IntNode
{
private:
    int data;
    IntNode *link;
public:
    IntNode(int newData, IntNode *newLink);
    int getData();
    IntNode getLink();
    void setData(int newData);
    void setLink(IntNode *newLink);
};

#endif /* IntNode_h */

This is the IntLinkedList.cpp file:

#include<iostream>
#include "IntLinkedList.hpp"
#include "IntNode.hpp"

IntLinkedList::IntLinkedList()
{
    head = nullptr;
    tail = nullptr;
    numElements = 0;
}

void IntLinkedList::add(int newElement)
{
    if(!(tail))
    {
        *head = IntNode(newElement, nullptr);
        tail = head;
    }
    else
    {
        *tail = IntNode(newElement, nullptr);
        tail->getLink() = *tail;
    }
    numElements++;
}

This is the IntLinkedList.hpp header file:

#ifndef IntLinkedList_hpp
#define IntLinkedList_hpp

#include <stdio.h>
#include "IntNode.hpp"

class IntLinkedList
{
private:
    IntNode *head;
    IntNode *tail;
    int numElements;
public:
    IntLinkedList();
    void add(int newElement);
};

#endif /* IntLinkedList_hpp */

When I run the code, it gave me this:

Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)

and highlights this piece of code, which is part of the IntLinkedList::add() method:

*head = IntNode(newElement, nullptr);

Answer 1

First and foremost - C++ already has a native single-linked list class: std::forward_list. And a native double-linked list class: std::list. You really should use these classes instead of creating your own.

That being said, if you must create your own classes (ie, for a school assignment), then know that your classes are not using pointers correctly:

• in IntNode::getLink(), you are dereferencing the link pointer when it should be returned as-is. This will fail if getLink() is called on the tail node of IntLinkedList since link will be nullptr in that case.

• in IntLinkedList::add(), you are dereferencing the head pointer when it is nullptr, which is why you get the runtime error.

• in IntLinkedList::add(), you are also using getLink() incorrectly. You are assigning a new IntNode object to the current tail object, thus changing its data and link. And then you are calling getLink() on the current tail object, which will fail for the reason mentioned further above - its link is nullptr. You should be linking the new IntNode object to the current tail object, not replacing the current tail object.

You need to dynamically allocate the IntNode objects via the new expression (just like in Java), otherwise the objects will get destroyed as soon as they go out of scope.

You also need to implement the Rule of 3/5/0 in the IntLinkedList class to manage the IntNode objects correctly when an IntLinkedList object is copied, moved, assigned to, destroyed, etc.

Your code should look more like the following:

IntNode.hpp:

#ifndef IntNode_hpp
#define IntNode_hpp

class IntNode
{
private:
    int data;
    IntNode *link;
public:
    IntNode(int newData, IntNode *newLink = nullptr);
    int getData();
    IntNode* getLink();
    void setData(int newData);
    void setLink(IntNode *newLink);
};

#endif /* IntNode_hpp */

IntNode.cpp:

#include "IntNode.hpp"

IntNode::IntNode(int newData, IntNode *newLink)
    : data(newData), link(newLink)
{
}

int IntNode::getData()
{
    return data;
}

IntNode* IntNode::getLink()
{
    return link;
}

void IntNode::setData(int newData)
{
    data = newData;
}

void IntNode::setLink(IntNode *newLink)
{
    link = newLink;
}

IntLinkedList.hpp:

#ifndef IntLinkedList_hpp
#define IntLinkedList_hpp

#include "IntNode.hpp"

class IntLinkedList
{
private:
    IntNode *head = nullptr;
    IntNode *tail = nullptr;
    int numElements = 0;
public:
    IntLinkedList() = default;
    IntLinkedList(const IntLinkedList &src);
    IntLinkedList(IntLinkedList &&src);
    ~IntLinkedList();

    IntLinkedList& operator=(IntLinkedList src);

    void add(int newElement);
};

#endif /* IntLinkedList_hpp */

IntLinkedList.cpp:

#include "IntLinkedList.hpp"
#include <utility>

IntLinkedList::IntLinkedList(const IntLinkedList &src)
    : head(nullptr), tail(nullptr), numElements(0)
{
    IntNode *node = src.head;
    while (node)
    {
        add(node->getData());
        node = node->getLink();
    }
}

IntLinkedList::IntLinkedList(IntLinkedList &&src)
    : head(src.head), tail(src.tail), numElements(src.numElements)
{
    src.head = nullptr;
    src.tail = nullptr;
    src.numElements = 0;
}

IntLinkedList::~IntLinkedList()
{
    IntNode *node = head;
    while (node)
    {
        IntNode *link = node->getLink();
        delete node;
        node = link;
    }
}

IntLinkedList& IntLinkedList::operator=(IntLinkedList src)
{
    std::swap(head, src.head);
    std::swap(tail, src.tail);
    std::swap(numElements, src.numElements);
    return *this;
}

void IntLinkedList::add(int newElement)
{
    IntNode *node = new IntNode(newElement);
    if (!head)
    {
        head = node;
    }
    else
    {
        tail->setLink(node);
    }
    tail = node;
    ++numElements;
}

Answer 2

*head = IntNode(newElement, nullptr);

This says to create a (temporary) IntNode object, then copy that object to the object to which head points. However, the only value that has been assigned to head is nullptr, so there is no object to which head points. Copying to a non-existent object is a valid reason for crashing.

What you want is to create a new IntNode object (not a temporary), then have head point to that object. Change head not *head.

head = new IntNode(newElement, nullptr);

Don't forget to delete the object later. This means having a destructor, which leads to The Rule of Three.

Note: This is not the only bug in your code, just the one currently showing symptoms. I'll leave the rest for other questions or answers.