Generic single linked list

Question

I am a mathematician attempting to become proficient with C++. At the moment I am learning about data structures. I am tried writing a single linked list from scratch with some help from online tutorials. I wanted to see if there is anything that I could improve so that I can study and understand everything.

Here is my code:

#ifndef LinkedList_hpp
#define LinkedList_hpp

#include <iostream>

template<class T>
struct Node {
    T data;
    Node<T>* next;
};

template<class T>
class SingleLinkedList {
private:
    Node<T>* head;
    Node<T>* tail;

public:
    SingleLinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    ~SingleLinkedList(){
        std::cout << "Pointers deleted" << std::endl;
    }

    void createNode(const T& theData) {
        Node<T>* temp = new Node<T>;
        temp->data = theData;
        temp->next = nullptr;
        if(head == nullptr) {
            head = temp;
            tail = temp;
            temp = nullptr;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }

    void display() {
        Node<T>* temp = head;
        while(temp != nullptr) {
            std::cout << temp->data << "\t";
            temp = temp->next;
        }
    }

    void insert_start(const T& theData) {
        Node<T>* temp = new Node<T>;
        temp->data = theData;
        temp->next = head;
        head = temp;
    }

    void insert_position(int pos, const T& theData) {
        Node<T>* previous = new Node<T>;
        Node<T>* current = new Node<T>;
        Node<T>* temp = new Node<T>;
        current = head;
        for(int i  = 1; i < pos; i++) {
            previous = current;
            current = current->next;
        }
        temp->data = theData;
        previous->next = temp;
        temp->next = current;
    }

    void delete_first() {
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

    void delete_last() {
        Node<T>* previous = new Node<T>;
        Node<T>* current = new Node<T>;
        current = head;
        while(current->next != nullptr) {
            previous = current;
            current = current->next;
        }
        tail = previous;
        previous->next = nullptr;
        delete current;
    }

    void delete_position(int pos) {
        Node<T>* previous = new Node<T>;
        Node<T>* current = new Node<T>;
        current = head;
        for(int i = 1; i < pos; i++) {
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }

    bool search(const T& x) {
        struct Node<T>* current = head;  
        while (current != NULL) {
            if (current->data == x)
                return true;
            current = current->next;
        }
        return false;
    }
};

#endif /* LinkedList_hpp */

#include <iostream>
#include "LinkedList.hpp"


int main(int argc, const char * argv[]) {

    SingleLinkedList<int> obj;
    obj.createNode(2);
    obj.createNode(4);
    obj.createNode(6);
    obj.createNode(8);
    obj.createNode(10);
    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Displaying All nodes---------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.display();

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"-----------------Inserting At End-----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.createNode(55);
    obj.display();

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------Inserting At Start----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.insert_start(50);
    obj.display();

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"-------------Inserting At Particular--------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.insert_position(5,60);
    obj.display();

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------Deleting At Start-----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.delete_first();
    obj.display();

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"--------------Deleting At Particular--------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.delete_position(4);
    obj.display();
    std::cout << std::endl;

    obj.search(8) ? std::cout << "Yes" << std::endl : std::cout << "No" << std::endl;;



    return 0;
}

Answer 1

Design

You should look into the concept of "Sentinels". This is a fake node in your list (it has no data of its own). But by using a sentinel you never have an empty list and thus you never have to deal with nullptr this makes the code simpler to write (once you have given it some thought).

For every call to new there should be a call to delete. You don't do this. You need to be very explicit about these calls. In modern code we do away with new/delete by using smart pointers to manage memory.

In my opinion smart pointers solve 99.9% of the problems with pointers and you should not use pointers unless you are building a "Smart Pointer" or a "Container". Now a "Liked List" is a container so you are going to have to handle them. But remember the standard library already contains liked list so in normal code you don't need to to build containers or smart pointers that has already been done for you.

You need to learn some basic C++ idioms. Here is some basics you should probably go and read about. I will cover most of this below at a very basic level. Then you should go and read about it.

1. Rule of 3
   This is the basics around which all C++ is built. It is the most important thing to learn in C++ and basically makes the language the power house that it is.
2. Rule of 0
   The rule of three is there to make sure that when you do resource management it is done correctly. But if you correctly contain all your resources then the rule of 3 makes writing anything else easy as the Rule of zero applies.
3. Rule of 5
   With modern move semantics we have given the developer more power to help the compiler optimizing. The move semantics simply allow us to remove some copies that made C++ inefficient. Learning the rule of 5 helps with this.
4. Copy and Swap
   This is an idiom that helps you implement the rule of three.

Code Review

Include Guard

Good start.

#ifndef LinkedList_hpp
#define LinkedList_hpp

But that may not be very unique. You should include your namespace name as part of the guard to give you a better chance of it being unique. Also the name of the class is SingleLinkedList so your guard should reflect that for when you add a DoubleLinkedList.

Note. It is also traditional the macros are all uppercase. I don't mind this but others may complain about it. Personally I make mine all uppercase to be consistent with other standards.

Namespace

You don't use a namespace! Start practicing using your own namespace for your code. It will save you a lot of headaches one day.

#ifndef SNORRLAXXX_SINGLE_LINKED_LIST_HPP
#define SNORRLAXXX_SINGLE_LINKED_LIST_HPP

namespace Snorrlaxxx {
   // STUFF
}
#endif

Encapsulation

You don't need to expose this:

template<class T>
struct Node {
    T data;
    Node<T>* next;
};

This is an internal part of the linked list. Just declare it as a private member. Then you will not need to support it when it changes in the future (private parts of the code are implementation details that others can not use).

Initializer List

Always prefer to use the initializer list.

    SingleLinkedList() {
        head = nullptr;
        tail = nullptr;
    }

When you have members that are initialized they will initially be initialized by the initializer list. The code in the constructor then overrides this and can cause extra work.

    SingleLinkedList()
        : head(nullptr)
        , tail(nullptr)
    {}

Destructor

You really need to do the work here. Not just print something.

    ~SingleLinkedList(){
        // TODO delete all the elements from head.
    }

DRY

Don't repeat yourself. A lot of your code involves creating a node and initializing it. You may want to have a specific private member function do this for you.

I see this bit of code a couple of times.

        Node<T>* temp = new Node<T>;
        temp->data = theData;
        temp->next = nullptr;

You code add the code to the constructor of Node or just a private method on SingleLinkedList,

If we also a assume a sentinal (so there is always one node in the list even when empty) we rewrite your three insert methods:

    void createNode(const T& theData) {
        tail->next = new Node<T>(theData, nullptr);
        tail = tail->next;
    }

    void insert_start(const T& theData) {
        head = new Node<T>(theData, head);
    }

    void insert_position(int pos, const T& theData) {

        head = insert_position(head, pos, theData);
    }
    private:
    void insert_position(Node<T>* current, int pos, const T& theData) 
    {
        if (pos == 0 || current == nullptr) {
            return new Node<T>(theData, current == nullptr ? nullptr : current->next); 
        }
        current->next = insert_position(current->next, pos - 1, theData);
        return current;
    }

Some Leaks

Yikes:

        Node<T>* previous = new Node<T>;
        Node<T>* current = new Node<T>;

These two nodes are immediately leaked by overwriting them. No need to assign them values here just make them nullptr. You will notice that for both these new there is no equivalent delete.

Here by display() you mean print to std::cout. The one thing I would note is that std::cout is not the only stream. So I would change this to take a stream as a parameter (you can default it to std::cout).

    void display() {
        Node<T>* temp = head;
        while(temp != nullptr) {
            std::cout << temp->data << "\t";
            temp = temp->next;
        }
    }

The second thing to note is that the normal way of printing things is to use operator<<.

   std::cout << 5 << " Is a number: " << 2 << " Is another number\n";

Would it not be nice to use the same technique for your object. Will you can you just need to define the operator<< for your class.

  void display(std::ostream& str = std::cout) {
      // As you defined it before.
      // just use `str` rather than `std::cout`
  }

  // Define this inside the class.
  // By making it a friend it is just easier to declare and you
  // don't need to worry about the template part.
  friend std::ostream& operator<<(std::ostream& str, SingleLinkedList const& data) {
      data.display(str);
      return str;
   }

Copy Semantics

You did not deal with the rule of three.

 {
     SingleLinkedList<int>   a;
     a.createNode(5);

     SingleLinkedList<int>   b(a);
 }

You did not define a copy constructor so you were not expecting one to part of your class. But if you don't define one (or delete it) then the compiler will define a default copy constructor for you. Most of the time this works perfectly. But if your class manages a resource (like memory (ie your class contains a RAW pointer)) then it will probably fail.

In the above case both a and b will end up pointing at the same storage. So when they go out of scope the destructor is supposed to delete the pointers. Because they both point at the same object they end up double deleting the memory.

The same rule applies to assignment.

 {
     SingleLinkedList<int>   a;
     a.createNode(5);

     SingleLinkedList<int>   b;
     b.createNode(6);

     a = b;  // What happens here?
 }

The same issue as the copy constructor. The compiler has generated an assignment operator for your class. First problem is that it leaked the original node the second problem is that you will get a double delete when the destructor is called.

Solution.

1. Delete the copy operations.

class SingleLinkedList
{
     public:
         SingleLinkedList(SingleLinkedList const&)            = delete;
         SingleLinkedList& operator=(SingleLinkedList const&) = delete;

};

2. Write your own copy operations.

class SingleLinkedList
{
     public:
         SingleLinkedList(SingleLinkedList const& value)
             head(nullptr)
             tail(nullptr)
         {
             for(Node<T>* loop = value->head; loop != nullptr; loop = loop->next) {
                 createNode(loop->data);
             }
         }
         // Implement assignment in terms of Copy constructor.
         // This is known as the copy and swap idiom.
         SingleLinkedList& operator=(SingleLinkedList const& rhs)
         {
             SingleLinkedList    copy(rhs);  // Use copy constructor to copy object.
             swap(copy);                     // swap the copy and this.
         } // Destructor of copy kicks in and deletes the original list.
         void swap(SingleLinkedList& other) noexcept
         {
             usign std::swap;
             swap(head, other.head);
             swap(tail, other.tail);
         }
};

Move Semantics

When you deal with simple lists (ie of integer) copying data into the list is cheap and simple. But you have a list of expensive to copy objects then your standard copy is not sufficient,.

Think of createNode() when used with RocketShip.

 SingleLinkedList<RocketShip>    fleet;

It takes 6 months to create a new RocketShip so we want to minimize copying. You have done a good job by passing by reference (no copy). But the last step when you add it to the node you need to make a copy.

void createNode(const T& theData) {
    Node<T>* temp = new Node<T>;
    temp->data = theData;          // Here you are copying a RocketShip

That's an expensive operation. To prevent this C++ has move semantics.

void createNode(const&& theData) {
    Node<T>* temp = new Node<T>;
    temp->data = std::move(theData); // Here you are moving a RocketShip

Notice the &&. This binds against objects that are being moved. A move operation moves the existing data out of an object and into another object (this is usually cheaper than copying).

Inside we are using std::move to tell the compiler to use the move assignment operator.

 temp->data = std::move(theData);
              // This make theData movable
              // It will use the move assignment operator.

If your class does not have a move assignment operator then it will copy (so worst case senario it is the same cost as a copy). So integers are always copied. But you can potentially move a RocketShip if the class has a move assignment operator.

  RocketShip& operator=(RocketShip&& rhs) noexpcept;

Answer 2

• As others have already stated in the comments your program leaks memory because you never delete your list on destruction. Destructors will not magically clean things up for you. If you want something done then you need to do it yourself.
  I suggest taking another look at the basics. Perhaps this FAQ can help you. Also take a look at the official guidelines concerning resource managment. Generally the use of raw pointers is discouraged.

• Node is an implementation detail and as such should be part of SingleLinkedList

• Use member initialization lists or direct initialization

• You are violating the rule of 3/5/0

• Prefer using \n over std::endl

• Prefer prefix over postfix

• return 0 can be dropped from the end of main as it's optional

• You are almost always using nullptr but then resort back to using NULL, why?

• Your use of space after flow control statements is inconsistent and while not wrong it's really annoying to read

• In your class the private keyword is redundant as everything in a class is private by default. Generally you should order your interface from public to private so people can read the public part first.

Answer 3

Sounds ambitious! Good luck to you.
FWIW, when I studied data structures there was loads of material before ever getting into pointers. You might do better to find a curriculum arranged in a good order for learning.

---

⧺C.149 — no naked new or delete.

Probably, Node::next and SingleLinkedList::head should be unique_ptr<T>, not raw pointers.

It goes deeper than not freeing nodes when you delete. You seem to be newing nodes all over where it makes no sense whatsoever.

~SingleLinkedList(){
    std::cout << "Pointers deleted" << std::endl;
}

No, they are not! You print the message, but never delete the pointers contained in the object. Or did you mean that this object is being deleted?

---

createNode seems like it is right, but could be written better.

    Node<T>* temp = new Node<T>;
    temp->data = theData;
    temp->next = nullptr;

Instead of naked new, you will use make_unique.
Rather than creating it and then assigning to the members in a separate step, make the Node initialize to the desired values. So it becomes:

    auto fresh = make_unique<Node>{std::move(theData);}

The move is for efficiency — this parameter is a “sink” value. Declare it to pass by value, not const ref, and then move it into place, with no extra copies being made anywhere along the way. The Node struct will have a constructor.

---

    if(head == nullptr) {

Don’t make explicit comparisons against nullptr. Use the contextual conversion to bool as a truth value. This will be more important with smart pointers! And temp should be a smart pointer, as noted earlier.

        temp = nullptr;

Why? And why only on one branch and not the other?

---

void display() {

Don’t make that a member. You will have a general purpose way for code using this list to go through it, right? A display function should be a stand-alone function that calls the public API.

---

void insert_start(const T& theData) {

A lot of this is duplicated from createNode so the same comments apply. You forgot the handle the case where the list was empty, so tail will be left as null.

Other than that, just how is this any different than createNode?

---

void insert_position(int pos, const T& theData) {

    Node<T>* previous = new Node<T>;
    Node<T>* current = new Node<T>;
    Node<T>* temp = new Node<T>;

    current = head;

    for(int i  = 1; i < pos; i++) {
        previous = current;
        current = current->next;
    }

    temp->data = theData;
    previous->next = temp;
    temp->next = current;
}

OK, you allocate memory and assign it to current, then assign head which leaks the node you just created. Likewise, previous is allocated, and then if the loop executes non-zero times you drop that on the floor, too.

---

void delete_first() {

what happens if the list is empty?

---

void delete_last() {

    Node<T>* previous = new Node<T>;
    Node<T>* current = new Node<T>;

    current = head;

    while(current->next != nullptr) {
        previous = current;
        current = current->next;
    }

    tail = previous;
    previous->next = nullptr;
    delete current;
}

What use do you have for allocating more nodes in the delete function? This looks like the earlier case, where you allocate memory and then drop it on the floor.

I wonder if you are misunderstanding how pointers work. The variable itself is a pointer; it does not need to be bound to an object which then gets assigned over.

---

void delete_position(int pos) {

ditto.

---

    while (current != NULL) {

Forget that the NULL macro ever existed. Don’t use it.