Generic Singly Linked List in C++

Question

I am currently working on implementing some data structures as a way to learn C++. I'm coming mostly from a Java background so I was hoping to get some feedback regarding this implementation of a singly linked list in C++ using templates. This singly linked list will only support insertions at the head and tail positions and deletions from the head position. The plan is to use this as a base to build further data structures. I would like to create a rather complete library of data structures, so I was hoping to make them as extensible and reusable as possible.

Below follows the class definition.

#ifndef LINKEDLISTS_SINGLYLINKEDLIST_H_
#define LINKEDLISTS_SINGLYLINKEDLIST_H_

#include <cstddef>
#include <iostream>

template <typename E>
class SinglyLinkedList {

private:

    /** BEGIN NESTED NODE CLASS **/
    class Node {

    private:
        E data; //Should this be a reference?
        Node* next;

    public:
        Node(Node* n, const E& d) : data(d), next(n) {};

        Node* getNext() const { return next; }

        E& getData() { return data; }

        void setNext(Node* n) { next = n; }

    }; /** END NESTED NODE CLASS **/

    /** Begin fields of SinglyLinkedList class **/
    Node* head;
    Node* tail;
    int listSize;
    /** End fields of SinglyLinkedList class **/

public:

    SinglyLinkedList();
    ~SinglyLinkedList();

    //Accessor methods
    bool isEmpty() const;
    int size() const;
    const E& first() const;
    const E& last() const;

    //Update methods
    void addFirst(const E&);
    void addLast(const E&);
    E* removeFirst();

    void print() const;

}; /** END SINGLYLINKEDLIST CLASS HEADER **/

#include "SinglyLinkedList.tpp" //Include implementations of template code.

#endif /* LINKEDLISTS_SINGLYLINKEDLIST_H_ */

The implementations of the functions follow below:

/*
 * SinglyLinkedList.tpp
 *
 *  Created on: Jan 5, 2020
 *      Author: dii
 */

/** Constructor **/
template<typename E>SinglyLinkedList<E>::SinglyLinkedList() : head(nullptr), tail(nullptr), listSize(0) {}

/** Destructor **/
template<typename E>SinglyLinkedList<E>::~SinglyLinkedList() {
    while(!isEmpty()) {
        delete removeFirst();
    }
}


/** Begin functions **/


template<typename E> bool SinglyLinkedList<E>::isEmpty() const { return listSize == 0; }

template<typename E> int SinglyLinkedList<E>::size() const { return listSize; }

template<typename E> const E& SinglyLinkedList<E>::first() const { return head->getData(); }

template<typename E> const E& SinglyLinkedList<E>::last() const { return tail->getData(); }

template<typename E> void SinglyLinkedList<E>::addFirst(const E& d) {

    Node* temp = new Node(head->getNext(), d); //Create a new node.
    head = temp; // Set the head pointer to point to this object.
    listSize++; // Increase size of list by 1.

}

template<typename E> void SinglyLinkedList<E>::addLast(const E& d) {

    Node* temp = new Node(nullptr, d);
    if(isEmpty()) {
        head = temp;
        tail = temp;
    } else {
        tail->setNext(temp);
        tail = temp;
    }

    listSize++;

}

template<typename E> E* SinglyLinkedList<E>::removeFirst() {

    if(isEmpty()) {
        return nullptr;
    }

    E* temp = &(head->getData());
    head = head->getNext();
    listSize--;

    return temp;

}

template<typename E> void SinglyLinkedList<E>::print() const {
    Node* walk = head;
    while(walk != nullptr) {
        std::cout << walk->getData() << std::endl;
        walk = walk->getNext();
    }
}

I have a feeling that the destructor is not implemented as well as it could be. I am also still not entirely sure about when to use references, e.g., should the data field of the Node class be of type E& or is just E ok?

Answer 1

Design

It's relatively simple to create a double linked list!

---

Some things you should think about some more:

1. Please put your code into a namespace. Do you think that SinglyLinkedList is a very unique name in the global scope?
2. You need to look into const correctness.
3. You need to look into move semantics.

---

Major Bug.

You have not implemented the rule of three (or five). When a class contains an owned pointer the compiler generated copy constructor, copy assignment operator and destructor are not going to work correctly.

Your SinglyLinkedList contains the owned pointer: head. An owned pointer is one that you have taken responsibility for the lifespan of (and are thus going to call delete on it when it the object is destroyed.

{
     SinglyLinkedList<int>    list1;
     list1.addFirst(1);

     SinglyLinkedList<int>    list2(list1);
}
// This code is broken as you have a double delete.

---

Upgrade you need to do.

The standard library defines things called concepts. A concept is a set of properties that a class has. One of the big concepts of the standard is the concept of a "Container" (of which a singly linked list is). Ao you should probably make your list "Container" compliant.

Code Review

I hate useless comments.

    /** BEGIN NESTED NODE CLASS **/
    class Node {

That counts as a useless comment.

---

OK good start.

        Node(Node* n, const E& d) : data(d), next(n) {}   ;
                 // Not Needed                           ^^^

But it does mean that you are required to copy the object into the list. Modern C++ has the concept of move semantics. So you should allow for moving the object into the list.

        Node(Node* n, E&& d) : data(std::move(d)), next(n) {}

Also you should allow the object to be constructed in place:

        template<typename... Args>
        Node(Node* n, Args&&... args)
            : data(std::forward<Args>(args)...)
            , next(n)
        {}

---

Here you get a reference to the object.
That's fine.

        E& getData() { return data; }

But what happens if your list has been passed by const reference to a function. Now you can no longer accesses the data as you can't get a const reference to the data.

        E const& getData() const {return data;}

Its a bit strange that you only return reference from the node. But you return only const references from the list?

    const E& first() const;
    const E& last() const;

---

I actually hate your get/set mentatility here. I see no need for it inside the node object itself.

        void setNext(Node* n) { next = n; }

---

That's fine.

    void print() const;

But two things to note.

1. There is more streams than the std::cout so allow this to be pramertized.

2. The normal way of streaming is via the output operator: operator<<()

   void print(std::ostream& stream = std::cout);
   friend std::ostream& operator<<(std::ostream& str, SinglyLinkedList const& data)
   {
       data.print(str);
       return str;
   }
   

---

Answer 2

forward_list exists, so I assume this is a learning exercise?

---

style nit: You're using nonstandard naming conventions compared to the STL; though many people don't like those anyway. addFirst may be surprising to readers who are more used to something like "push front" or "enqueue".

---

You're not deleting head here. std::unique_ptr could help here, but might not make sense if you're doing this as an exercise. Still, you should try to figure out a way to prevent memory leaks in a robust way.

template<typename E> E* SinglyLinkedList<E>::removeFirst() {

    if(isEmpty()) {
        return nullptr;
    }

    E* temp = &(head->getData());
    head = head->getNext();
    listSize--;

    return temp;

}

---

This interface only supports storing const values that are copy-constructable. This is a severe limitation -- you wouldn't be able to make a list of std::unique_ptrs for example, because those cannot be copied. Supporting non-copyable types would be a good exercise (see forward_list for reference).

Answer 3

I am also still not entirely sure about when to use references, e.g., should the data field of the Node class be of type E& or is just E ok?

It should not be stored as a reference. Using a reference would create ownership and lifetime issues, and can make the class harder to use (since you can't copy or move it).

addFirst will crash if the list is empty (when head is nullptr).

removeFirst should not return a pointer. Currently you leak the memory you allocated for the Node that holds the data, and return a pointer to that. When you fix the memory leak, you'll return a dangling pointer (or, worse, a pointer that the caller will have to delete). It would be better to return a copy of the item in the list. If the list is empty, either throw an exception or return a default constructed T object. You will then need to make some changes to your destructor.

Your while loop in print can be more concisely stated using a for loop.

template<typename E> void SinglyLinkedList<E>::print() const {
    for (Node* walk = head; walk != nullptr; walk = walk->getNext()) {
        std::cout << walk->getData() << '\n';
    }
}

I've also changed the std::endl to a '\n' character. Since endl flushes the output buffer, there can be performance issues when using it.

You can also look into using rvalue references (T &&) for things, which will let you move objects rather than having to copy them.