Singly linked list implementation in c++ (Data Structure)

Question

I just finished writing an implementation of the "singly linked list data structure",and i wanna know if there are some bugs or memory leaks or any bad code to make the code better! i'm so sorry because there is no comment(But the code is simple , you can understand it)

#include <iostream>

template<typename T>
struct Node
{
    T Data;
    Node* NextPtr = nullptr;
    Node() {
        NextPtr = nullptr;
    }
    Node(T Filler, Node* NextPtrAr) {
        Data = Filler;
        NextPtr = NextPtrAr;
    }
    void operator =(Node NAr) {
        Data = NAr.Data;
        NextPtr = NAr.NextPtr;
    }
};

template<typename T>
class LinkedList
{
protected:
    unsigned int Size = 0;
    void SetSize(unsigned int SizeAr);
public:
    Node<T> Head;
    Node<T> Tail;

    LinkedList();
    LinkedList(T Filler, unsigned int NbrOfElem = 1);
    LinkedList(std::initializer_list<T> List);

    unsigned int GetSize();
    void Push(T Filler, unsigned int Index = Size);
    void Pop(unsigned int Index = 0);

    void operator=(LinkedList<T> List);
    void operator=(std::initializer_list<T> List);
    Node<T>& operator[](unsigned int Index);
    Node<T>& NodeAt(unsigned int Index);
};

template<typename T>
void LinkedList<T>::SetSize(unsigned int SizeAr) {
    Size = SizeAr;
}

template<typename T>
unsigned int LinkedList<T>::GetSize() {
    return Size;
}

template<typename T>
LinkedList<T>::LinkedList() {

}

template<typename T>
LinkedList<T>::LinkedList(T Filler, unsigned int NbrOfElem) {
    if (NbrOfElem==1)
    {
        Head.Data = Filler;
        SetSize(1);
    }
    else if(NbrOfElem==2)
    {
        Head.Data = Filler;
        Tail.Data = Filler;
        Head.NextPtr = &Tail;
        SetSize(2);
    }
    else
    {
        Node<T>* TempNextPtr=new Node<T>;
        Head.Data = Filler;
        Head.NextPtr = TempNextPtr;
        for (int i = 0; i < NbrOfElem - 1; i++)
        {
            Node<T>* NewNode = TempNextPtr;
            TempNextPtr = new Node<T>;
            NewNode->Data = Filler;
            NewNode->NextPtr = TempNextPtr;
        }
        Tail.Data = Filler;
        SetSize(NbrOfElem);
    }
}

template<typename T>
Node<T>& LinkedList<T>::operator[](unsigned int Index) {
    if (Index >= Size - 1)
    {
        return Tail;
    }
    Node<T>* ReturnNode = &Head;
    for (int i=0;i<Index;i++)
    {
        ReturnNode = ReturnNode->NextPtr;
    }
    return *ReturnNode;
}

template<typename T>
void LinkedList<T>::operator=(LinkedList<T> List) {
    //Clear
    for (int i=1;i<Size-1;i++)
    {
        delete& NodeAt(i);
    }
    //Fill
    Head.Data = List.Head.Data;
    Head.NextPtr = new Node<T>;
    Tail.Data = List.Tail.Data;
    for (int i = 1; i < List.GetSize() - 1; i++)
    {
        Node<T>* NewNode = NodeAt(i - 1).NextPtr;
        NewNode->Data = List[i].Data;
        NewNode->NextPtr = new Node<T>;
    }
    SetSize(List.GetSize());
}

template<typename T>
void LinkedList<T>::operator=(std::initializer_list<T> List) {
    //Clear
    for (int i = 1; i < Size - 1; i++)
    {
        delete& NodeAt(i);
    }
    //Fill
    Head.Data = *List.begin();
    Head.NextPtr = new Node<T>;
    Tail.Data = *(List.end()-1);
    for (int i = 1; i < List.size() - 1; i++)
    {
        Node<T>* NewNode = NodeAt(i - 1).NextPtr;
        NewNode->Data = *(List.begin()+i);
        NewNode->NextPtr = new Node<T>;
    }
    SetSize(List.size());
}

template<typename T>
LinkedList<T>::LinkedList(std::initializer_list<T> List) {
    Head.Data =*List.begin() ;
    Head.NextPtr = new Node<T>;
    Tail.Data = *(List.end()-1);
    Tail.NextPtr = nullptr;
    for (int i=1;i<List.size()-1;i++)
    {
        Node<T>* NewNode = NodeAt(i-1).NextPtr;
        NewNode->Data = *(List.begin()+i);
        NewNode->NextPtr = new Node<T>;
    }
    SetSize(List.size());
}

template<typename T>
Node<T>& LinkedList<T>::NodeAt(unsigned int Index) {
    if (Index>=Size-1)
    {
        return Tail;
    }
    Node<T>* ReturnNode = &Head;
    for (int i = 0; i < Index; i++)
    {
        ReturnNode = ReturnNode->NextPtr;
    }
    return *ReturnNode;
}

template<typename T>
void LinkedList<T>::Push(T Filler, unsigned int Index) {
    Node<T>* NewNode = new Node<T>;
    if (Index==0)
    {
        NewNode->Data = Head.Data;
        NewNode->NextPtr = Head.NextPtr;
        Head.Data = Filler;
        Head.NextPtr = NewNode;
    }
    else if(Index>=Size) {
        NewNode->Data = Tail.Data;
        NewNode->NextPtr = &Tail;
        NodeAt(Size - 2).NextPtr = NewNode;
        Tail.Data = Filler;
    }
    else
    {
        NewNode->Data = Filler;
        NewNode->NextPtr = NodeAt(Index - 1).NextPtr;
        NodeAt(Index - 1).NextPtr = NewNode;
    }
    SetSize(Size + 1);
}

template<typename T>
void LinkedList<T>::Pop(unsigned int Index) {
    if (Size < 2)
    {
        *Head.Data = nullptr;
        Head.NextPtr = nullptr;
        SetSize(0);
        break;
    }
    if (Index==0)
    {
        Head = NodeAt(1);
        delete& NodeAt(1);
    }
    else if(Index>=Size-1)
    {
        Tail.Data = NodeAt(Size - 2).Data;
        NodeAt(Size - 3).NextPtr = &Tail;
        delete& NodeAt(Size-2);
    }
    else
    {
        NodeAt(Index - 1).NextPtr = &NodeAt(Index + 1);
        delete& NodeAt(Index);
    }
    SetSize(Index - 1);
}

int main()
{
    LinkedList <int> L1 = { 10, 20, 30 };
    LinkedList<int>L2(175, 100);
    L2 = L1;
    std::cout << L2[99].Data;
}

Answer 1

Firstly, the code is not compiling:

:36:46: error: invalid use of non-static data member 'Size' void Push(T Filler, unsigned int Index = Size); ^~~~

=> Size is a member variable of the class, you cannot have it as a default argument. If you want to have Push with only one method, you'd have to create a separate overload for that one:

void Push(T Filler) { Push(Filler,Size); // now possible, since we are in class-scope. }

:206:9: error: 'break' statement not in loop or switch statement break;

=> change break to return, since I guess you want to exit the method.

---

Ignoring that and before digging in to the code, I would like to say something about naming.

I will take Node as an example:

template<typename T>
struct Node
{
    T Data;
    Node* NextPtr = nullptr;
    Node() {
        NextPtr = nullptr;
    }
    Node(T Filler, Node* NextPtrAr) {
        Data = Filler;
        NextPtr = NextPtrAr;
    }
    void operator =(Node NAr) {
        Data = NAr.Data;
        NextPtr = NAr.NextPtr;
    }
};

The type Node has the same naming convention as NodePtr, a variable. Thus, reading code without context, I would not know whether, for example, Data is a type or a variable. It's good practice to separate them. You can, for example, have CamelCase for types, and camelCase for variables. It's usually also good to note private variables with some notation, this can be prefixing with m_ or suffixing with _.

Updated naming gives:

template<typename T>
struct Node
{
    T data;
    Node* nextPtr = nullptr;
    Node() {
        nextPtr = nullptr;
    }
    Node(T filler, Node* nextPtrAr) {
        data = filler;
        nextPtr = nextPtrAr;
    }
    void operator =(Node nAr) {
        Data = nAr.data;
        nextPtr = NAr.nextPtr;
    }
};

Look how even the syntax highlighter works better - now not everything has the color of a type.

---

Since we already are looking at Node, we can tweak the constructors a bit. nextPtr is already (correctly) default member initialized to nullptr, so we do not need an explicit default constructor doing the same. Actually, you do not need any of your constructors in this case - the compiler will create all of them for you.

template<typename T>
struct Node
{
    T data;
    Node* nextPtr = nullptr;
}

is thus fine.

Letting the compiler do it's job is usually better. Now we don't have to deal with operator= having wrong return type (it should return Node& and not void), and construction should be done in the initializer list to avoid double initialization. Node(T filler, Node* nextPtrAr) : data(filler), nextPtr(nextPtrAr) {}, for example. The problem is that once you are in the body of the constructor, the object is already constructed - so changing the variables there reinitializes them.

---

Now to the singly linked list.

There is already a singly linked list in the STL: https://de.cppreference.com/w/cpp/container/forward_list

Not to put you off writing your own, but it can be instructive to read the API. Interestingly, the list only has one access operator front, that gives you the first element. If you want to get the rest of the element, you have to iterate over them (by using the std::forward_list::iterator). Linked lists are usually used for the cases, where we only want to know the head (priority queues, stacks) or iterate over them blindly.

The LinkedList, as you have it, has a random access operator Node<T>& operator[](unsigned int Index);. But a random access operator is usually provided to containers that actually support random access. If I used operator[], I would assume that it has a constant complexity (O(1)), but for a linked list, it is linear (O(N)), since we have to iterate through the list to get the element. NodeAt is a better name for the method, although even better would be to provide an iterator. => remove operator[].

You are using NodeAt yourself in a for-loop:

for (int i = 1; i < Size - 1; i++)
{
    delete& NodeAt(i);
}

This essentially gives you a complexity of O(N^2), which is unnecessary. And actually, I have to admit I do not understand why it is working. When you delete the Node, how you you in the next iteration iterate to the node that the destructed object was pointing to? Better would probably be to pop and delete until list is empty.

I will stop with the review here. Hopefully you have some points you can take with you.

Answer 2

Overview

Your code definitely leaks nodes. You should fix this in the destructor of LinkedList.

You don't implement move semantics. Which means that you can only copy and this will be less efficient in most cases.

You return access to your internal structures of your class. This means you have not protected the structure from external interference and thus have not protected your class (why are you using C++ may as well use PERL).

You have a copy assignment operator but not a copy constructor. Sure this is possible but normally these are symmetric operations.

You are creating a singly linked list. It is not that much harder to crate a doubly linked list. Also using a doubly linked list makes inserting and removal of items from the list much easier to write.

Code Review

The struct Node is part of the LinkedList class. There is no need to expose it (this exposes users to implementation details they don't need to know).

You add a constructor and assignment operator. But these operations don't do anything special and the default versions do exactly the same. So you may as well not explicitly write them.

Example:

    template<typename T>
    struct LokiNode
    {
          Node* next;
          Node* prev;
          int   value;
    };

    LokiNode x{nullptr, nullptr, 10}; // Works as expected.
    LokiNode y{x};                    // Works as expected.
    LokiNode z;                       // Uninitialized value.
    z = y;                            // Works as expected;

---

I don't like this:

    Node() {
        NextPtr = nullptr;
    }

It allows you to create a Node that can be partially initialized. This means that you can potentially fall into UB if code reads the Data value.

---

Naming: It is traditional in C++. That object/method names begin with a lowercase letter and user defined types begin with an uppercase letter.

T     Data;                  // I would make this data
Node* NextPtr = nullptr;     // I would make this next (I would drop Ptr)

This allows you to quickly and easily deferential types from objects which in C++ is an important distiction.

---

Prefer to use the initializer list:

    Node(T Filler, Node* NextPtrAr) {
        Data = Filler;
        NextPtr = NextPtrAr;
    }

In this case it makes no different. But if you do it like this all the time you may get into this bad habbit. This will cause issues if one of the members is expensive to initialize and re-initialization may double that code.

    Node(T Filler, Node* NextPtrAr)
        : Data{Filler}
        , NextPtr{NextPtrAr}
    {}

---

It is traditional for the assignment operator to return a reference to self.

    void operator =(Node NAr) {
    }

    Node& operator=(Node n)
    {
         // STUFF
         return *this;
    }

Not essential but people will wonder why you are doing it funny. By returning a reference to self you allow assignment chaining which makes the usage to similar to built in types (and thus easier to use).

---

Protected is a terrible thing stop using it.

protected:
    unsigned int Size = 0;
    void SetSize(unsigned int SizeAr);

Member variables should definitely be private (unless you have a very good and documentable reason not to make it private).

Member methods can by protected, but simply subverts the protection mechanism. This is only really useful where this is a non concreate base class where other people would never use it. i.e. this class provides some basic functionality but is not the final class. A derived class may inherit from this and provides the real class that a user would have.

---

This look like a bug.

    Node<T> Head;
    Node<T> Tail;

This means your list always has two members (a head and tail that are different). Your list is never empty? What I think you want are two pointers to the head and tail of the list.

    Node<T>* Head;
    Node<T>* Tail;

Now a head and tail can be nullptr to represent the empty list.

---

Fine set of constructors:

    LinkedList();
    LinkedList(T Filler, unsigned int NbrOfElem = 1);
    LinkedList(std::initializer_list<T> List);

But I don't see a destructor. This is a bug. In a list you must dynamically allocate the elements in the list. I don't see a destructor in the Node so this destructor must do some work to tidy up that dynamic allocation.

---

Const correctness:

This function does not change the state of the object.

    unsigned int GetSize();

As a result you should probably mark it as const so it can be called from a const context (ie passed by const reference to a method). Also size type functions we usually specify this in terms of std::size_t to indicate this is a size. This also applies to index operations.

    std::size_t GetSize() const;

---

That's interesting:

    void operator=(std::initializer_list<T> List);

Sure. You can do this. But can you not achieve the same affect by using constructor and assignment operator:

    LinkedList<int>    x;

    x = {1,2,3,4};   // This calls your assignment operator.

But if you did not have this assignment operator what would it do?

    x = {1,2,3,4};   // Different types in assignment.
                     // but there is a one parameter constructor that will
                     // convert an initializer list into a LinkedList. So
                     // the compiler will call this constructor to convert
                     // the initializer list into a LinkedList<int> type.
                     //
                     // We can then apply the normal assignment operator to 
                     // copy (or move) the new object to the original `x`.
                     //
                     // Note: Because of copy elision optimization
                     //       We can optimize away the copy if needed or
                     //       simply use the move assignment operator.

---

Sure I don't mind the use of NodeAt(). Though if you look in the standard library functions like this are simply called at()

    Node<T>& operator[](unsigned int Index);
    Node<T>& NodeAt(unsigned int Index);

---

You can simply set the size!

template<typename T>
void LinkedList<T>::SetSize(unsigned int SizeAr) {
    Size = SizeAr;
}

I would expect you have to add the appropriate number of elements into the list.

---

This is overly complex because you are not using pointers for head and tail.

template<typename T>
LinkedList<T>::LinkedList(T Filler, unsigned int NbrOfElem) {
    if (NbrOfElem==1)
    {
        Head.Data = Filler;
        SetSize(1);
    }
    else if(NbrOfElem==2)
    {
        Head.Data = Filler;
        Tail.Data = Filler;
        Head.NextPtr = &Tail;
        SetSize(2);
    }
    else
    {
        Node<T>* TempNextPtr=new Node<T>;
        Head.Data = Filler;
        Head.NextPtr = TempNextPtr;
        for (int i = 0; i < NbrOfElem - 1; i++)
        {
            Node<T>* NewNode = TempNextPtr;
            TempNextPtr = new Node<T>;
            NewNode->Data = Filler;
            NewNode->NextPtr = TempNextPtr;
        }
        Tail.Data = Filler;
        SetSize(NbrOfElem);
    }
}

I would simply write this (assuming head/tail are pointers).

template<typename T>
LinkedList<T>::LinkedList(T Filler, unsigned int NbrOfElem)
    : Head(nullptr)
    , Tail(nullptr)
{
    for(int loop = 0; loop < NbrOfElem; ++loop) {
        Head = new Node<T>{Filler, Head};
        if (Tail == nullptr) {
            Tail = Head;
        }
    }
}

---

Normally in C++ operator[] is unchecked accesses into the container. While at() is the checked accesses into the container. You use them both as checked. Personally I would not bother but you can.

If you want both to be checked then one of these two should call the other.

template<typename T>
Node<T>& LinkedList<T>::operator[](unsigned int Index) {
    if (Index >= Size - 1)
    {
        return Tail;
    }

---

Why are you returning a Node!!!

template<typename T>
Node<T>& LinkedList<T>::operator[](unsigned int Index) {

You are giving people access to the internal types of your class. This will allow them (actually encourage) them to modify your internal structures. You should be returning the element stored at that location.

template<typename T>
T&       LinkedList<T>::operator[](unsigned int Index);
template<typename T>
T const& LinkedList<T>::operator[](unsigned int Index) const;

---

You have marked this as a functionality

    //Clear
    for (int i=1;i<Size-1;i++)
    {
        delete& NodeAt(i);
    }

Why not make that explicit and make it a new method?

---

You have marked this as a functionality

    //Fill
    Head.Data = List.Head.Data;
    Head.NextPtr = new Node<T>;
    Tail.Data = List.Tail.Data;
    for (int i = 1; i < List.GetSize() - 1; i++)
    {
        Node<T>* NewNode = NodeAt(i - 1).NextPtr;
        NewNode->Data = List[i].Data;
        NewNode->NextPtr = new Node<T>;
    }

Why not make that explicit and make it a new method?

---

In this question My first implementation of a linked list in C++ I have provided a review of another linked list. Scroll to the bottom of my answer and there is a reference implementation. Please have a look.

Simplified List

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

    Node*       head;
    Node*       tail;
    std::size_t length;

    public:
        LinkedList()            // Default Constructor
            : head(nullptr)
            , tail(nullptr)
            , length(0)
        {}
        // Have to release all the nodes in a destructor
        ~LinkedList()
        {
            for (Node* loop = head; loop != nullptr;) {
                Node* old = loop;
                loop = loop->next;
                delete old;
            }
        }
        // Copy Constructor and Assignment.
        LinkedList(LinkedList const& copy)
            : head(nullptr)
            , tail(nullptr)
            , length(0)
        {
            // Loop over the other list.
            // Simply push each element into this list.
            for (Node* loop = copy.head; loop != nullptr; loop = loop->next) {
                push_back(loop->data);
            }
        }
        LinkedList& operator=(LinkedList const& rhs)
        {
            // Use the copy and swap idiom to do assignment.

            // 1. Copy the list using the copy constructor.
            LinkedList  copy(rhs);

            // 2. Swap the copy with the current object.
            swap(copy);

            // 3. When we go out of scope the `copy` object is
            //    destroyed. This releases the old object list
            return *this;
        }
        // Move Constructor and Assignment
        // For now we delete these. But we will␣
        // come back to this later.
        LinkedList(LinkedList&&) noexcept            = delete;
        LinkedList& operator=(LinkedList&&) noexcept = delete;

        // Swap
        // We want to swap two objects of type Linked List.
        void swap(LinkedList const& rhs) noexcept
        {
            std::swap(head, rhs.head);
            std::swap(tail, rhs.tail);
        }
        void push_back(T const& value)
        {
            if (tail) {
                // If the list is not empty add it to the back.
                // Simply create the node linked to the tail and
                // then move the tail to the new tail node.
                tail->next = new Node{value, tail, nullptr};
                tail = tail->next;
            }
            else {
                // If the list is empty.
                // Then the new node is both the head and tail
                head = tail = new Node{value, nullptr, nullptr};
            }
            ++length;
        }
        void pop_back()
        {
            if (tail) {
                // Keep track of the old value.
                Node* old = tail;

                // Remove the last element from the list
                tail = tail->prev;
                tail->next = nullptr;
                --length;

                // Tidy up. Delete the old element.
                delete old;
            }
        }
        std::size_t size() const    {return length;}
        T const& back() const       {return tail->data;}
        T&       back()             {return tail->data;}

        // I leave the following easy to implement methods for you.

        // Front version equivalent of the back methods.
        void push_front(T&);
        void pop_front();
        T const& front() const;
        T&       front();

        // Unchecked accesses.
        T const& operator[](std::size_t index) const;
        T&       operator[](std::size_t index);

        // Checked accesses.
        T const& at(std::size_t index) const;
        T&       at(std::size_t index);
};

int main()
{
    LinkedList<int>     list;
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_back(4);
    list.push_back(5);

    LinkedList<int>     second(list);
    std::cout << second.back();
    second.pop_back();
    second.pop_back();
    std::cout << second.back();
}