Simple SingleLinkedList Implementation in C++

Question

Below I have a very simple LinkedList implementation. I was wondering if there are any memory leak problems with this and if I used the pointers correctly. I just started practicing with C++ and hoping to improve my use of pointers and memory leak management.

#include <iostream>

struct node{
    int data;
    node *next;

    node::node(){}

    node::node(const int & val, node* link)
            : data(val), next(link)
    {}
};

class LinkedList
{

    public:
        LinkedList();
        void addToEnd(int val);
        void printList();
        void deleteList(node *head);
        void deleteNode(node *toBeDeleted);
        node* get(int index);

    private:
        int size;
        node *head, *tail;

};

LinkedList::LinkedList(){
    head = NULL;
    tail = NULL;
}

node* LinkedList::get(int index){

    node* temp = head;
    int pointer = 0;

    while(pointer != index){
        temp = temp->next;
        pointer++;
    }

    return temp;

}

void LinkedList::addToEnd(int val){

    node *temp = new node(val, NULL);
    // temp->data = val;
    // temp->next = NULL;

    if(head==NULL){
        head = temp;
        tail = temp;
        temp = NULL;
    }
    else{
        tail->next = temp;
        tail = temp;
    }
}

void LinkedList::printList(){

    node *temp = head;
    //temp = head;
    while(temp){
        cout<<temp->data<<"\t";
        temp = temp->next;
    }
}

//Supposed to delete the nodes coming after the input node
void LinkedList::deleteList(node *start){
    if(start){
        deleteList(start->next);
        delete start;
    }
}

//deletes a single node
void LinkedList::deleteNode(node* toBeDeleted){

    node* temp = head;

    if(head == toBeDeleted){
        head = head->next;
        delete temp;
    }

    while(temp->next != toBeDeleted){
        temp = temp->next;
    }

    if(temp->next){
        temp->next = toBeDeleted->next;
        delete toBeDeleted;
    }

}

int main(){


    LinkedList list;

    for(int i=0;i<4;i++){
        list.addToEnd(i+1);
    }

    list.deleteList(list.get(2));
    //list.deleteNode(list.get(2));

    list.printList();

    return 0;
}

Currently, the main function doesn't run after deleteList. I am not necessarily asking about how to fix that part, I just wanted to learn tips about better pointer uses and memory leak possibilities.

Edit:

I have commented the use of deleteList and deleteNode and below I have added a destructor showing how I was planning to use deleteList.

LinkedList::~LinkedList(){
    deleteList(head);
}

Answer 1

1. Make node an aggregate. The only ctor you ever use is the one initializing all members, whose use can be replaced with aggregate initialization.
   On a similar node, its default-ctor probably doesn't do what you expect (it leaves all members uninitialized), but that's difficult to determine.

2. Be aware that passing small trivially-copyable types by reference, unless inlined and optimized out, is slightly inefficient due to extra-indirection and forces you and the compiler to worry about aliasing.

3. While you could inhibit copy- and move- ctor/assignment, that would be wasted effort as node is an implementation-detail.
   Which leads me to ask why it isn't a private member of LinkedList.

4. Prefer giving the next-pointer the first spot. It likely makes the compiled code marginally more efficient, and allows better source-code for deleteNode.

5. Your linked-list is only single-linked, with members to facilitate inserting at the end and getting the lists size. So consider using a name reflecting that limitation, like SingleLinkedList.

6. Avoid empty lines after opening or before closing a block. Also keep in mind that return 0; is implicit for main().

7. Mind the rule of 3 / 5: Your class manages a resource (the linked nodes), so it needs appropriate copy-ctor, assignment-operator and dtor. Move-variants and default-ctor are also appreciated.

8. Your default-ctor for LinkedList does not initialize size. No matter though, you never use that member for anything.

9. .get() doesn't check whether the argument is out-of-range.

10. Prefer nullptr to NULL, the latter might not be a pointer in anything but unambiguous pointer-context. Also, you can use !pointer instead of pointer == nullptr.

11. .printlist() should be able to write to a different output-stream. Use a default-argument so you only need one function:

    void printlist(std::ostream& stream = std::cout);
    

12. Define the friend-function swap(a, b). Aside from being useful in its own right, it's useful for implementing move-ctor, move-assignment and others using the copy-and-swap-idiom.

13. .deleteList() should delete all nodes and reset the members. It could be implemented as:

    void SingleLinkedList::deleteList() {
        swap(*this, LinkedList());
    }
    

14. You fail to update tail as needed in .deleteNode(). Actually, rewrite that whole function from scratch using double-indirection to merge special cases:

    void SingleLinkedList::deleteNode(node* toBeDeleted) {
        node** p = &head;
        while (*p != toBeDeleted)
            p = &(*p)->next;
        *p = (*p)->next;
        delete toBeDeleted;
        if (!*p)
            tail = &head == p ? nullptr : (node*)((char*)p - offsetof(node, next));
        // The above can be simplified if next is the first element of node
        //  tail = &head == p ? nullptr : (node*)p;
    }
    

Answer 2

You asked about pointer usage, so a topic which may interest you is:

Indirect Pointers

Indirect pointers fall into the "easy to use, difficult to think up" category, but are useful in many cases, so are worth understanding, and apply to a linked list.

In your implementation of deleting a node there are two cases, one where the head should be deleted, and one where somewhere else should be, and in both cases you do roughly the same thing. We can get rid of that duplicated code.

Instead of

node* temp = head;

we can take the pointer to head, like

node** indirect = &head;

and as we go along, we can move indirect to the pointer to this node's next pointer

indirect = &((*indirect)->next);

Put together, this results in a method which looks something like this:

void SingleLinkedList::deleteNode(node* toBeDeleted){ 
    node* prev = nullptr;
    node** indirect = &head;

    while(*indirect != toBeDeleted){
        prev = *indirect;
        indirect = &((*indirect)->next);
    }

    *indirect = toBeDeleted->next;
    delete toBeDeleted;

    if(!(*indirect)) tail = prev;
}

Notice that the special case can be totally removed because, in the first assignment to indirect, indirect contains a pointer to somewhere in the stack (where head is), and in future assignments it has a value in the heap (where the current node is)

Answer 3

At the moment, deleteList doesn't appear to be functional. I assume you want to remove an entry from the list by its index i, right? Then you will have to patch the next of entry i-1 to point to i+1 before deleting. Remember, this may even change the value of head (if index 0 is to be removed).

No memory leak, but a SEGFAULT: You will definitely need a copy constructor. Otherwise, if someone tries to create a copy of a LinkedList, their head pointers will be the same (as the compiler-generated default copy constructor creates a "verbatim copy" of LinkedList). It's impossible to change both objects independently, and even worse, destruction of one instance will doom the second one (the pointers will still be there, but the memory already deallocated). Wait for the second destructor being called, and: instant SEGFAULT.

Answer 4

Major Issues

Your code leaks.

You call new in your code.

node *temp = new node(val, NULL);

For every call to new there must be a corresponding call to delete. Which I see in deleteNode() (which should be plural as it deletes all the nodes).

    delete temp;

But when the object is destroyed currently you have to manually destroy the elements by calling deleteNode() otherwise you will leak these nodes. You should set up your destructor to call delete to make sure this happens automatically.

~LinkedList() {
    deleteList(head);
}

You have broken the rule of three/five.

Once you fix the destructor.
You have a rule of three/five violation. Look it up.

{
    LinkedList  list1;
    list1.addToEnd(5);

    LinkedList  list2(list);  // Copy list 1.
                              // But not in a good way.
                              // Both lists now point at the same element 5
}
// Here you get a double delete
// list2 is destroyed first its destructor will delete the element 5.
// list1 is destroyed seconds its destructor will also delete the element 5
// this is illegal, a dynamically created element can only be deleted once.
// This results in undefined behavior.

You get the same affect with assignment.

{
    LinkedList  list1;
    LinkedList  list2;

    list1.addToEnd(5);

    list2 = list1             // Copy list 1.
                              // But not in a good way.
                              // Both lists now point at the same element 5
}

This is caused because the compiler will auto generate the copy constructor and the copy assignment operator. This auto generated version usually works just fine. The only time there is an issue is when you have a RAW "owned" pointer.

node *head; // This is an owned pointer.
            // An owner is the person responsible for calling delete
            // on the pointer. You should be deleting this in
            // your destructor.

Design

You can make the list easier to write if you use a Sentinel object (look it up). There are plenty of examples here in code review.

Code Review

This works fine as long as your data type is simple (like int)

struct node{
    int data;
    node *next;

    node::node(){}

    node::node(const int & val, node* link)
            : data(val), next(link)
    {}
};

But when you generalize your linked list to hold other types. Then copying the data into the node may not be very efficient.

    node::node(const int & val, node* link)
        : data(val)  // This is a copy.
        , next(link)
    {}

You need to add constructors for moving the data object into the node (look up move semantics). Also building the data object in-place is another useful technique (but more advanced).

As I mentioned above:

        LinkedList();

You are missing a destructor and the copy semantics (Copy constructor copy assignment operator (look up the copy and swap idiom)).

If there is an addToEnd()

        void addToEnd(int val);

Should there not also be an addToFront() otherwise we could just call this add()?

Prefer nullptr over NULL

NULL is something from C. It is basically zero. And has a type that allows it to be assigned to numeric values. Use nullptr it is a pointer type that can be converted to any pointer (but not a numeric type).

LinkedList::LinkedList(){
    head = NULL;  // nullptr
    tail = NULL;
}

Check your range.

node* LinkedList::get(int index){

What happens if index is greater than size?

    while(pointer != index){ 
        temp = temp->next; // At some point temp can become nullptr
        pointer++;         // Then the last line will fail
    }

Use constructor arguments.

You are always passing nullptr to the second parameter.

    node *temp = new node(val, NULL);

Not sure you need that parameter then.

Printing is not only done to std::cout

void LinkedList::printList(){

yes the default may be std::cout but there are so many other places you want to print. So pass the stream as a parameter. You can default it to std::cout.

Also note that methods that do not mutate the object should be marked const. This allows them to be called from a const context (ie when you only have a const reference to the object).

   void printList(std::ostream& out = std::cout) const;

But also not the standard way of printing in C++ is the operator<<. You can write one that calls printList.

   friend std::ostream& operator<<(std::ostream& s, LinkedList const& data)
   {
        data.printList(s);
        return s;
   }

Bug(s) in deleting

//deletes a single node
void LinkedList::deleteNode(node* toBeDeleted){

You don't reset the next or head pointer to nullptr after you delete the node. Thus your list can point to a bunch of deleted nodes.

Main does not need a return value

    return 0;

Look at other reviews for a good explanation.