Implementation of the linked list data structure in C++

Namespace

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

The term "linked list" is a common term. So I would expect somebody out there is already using the macro LINKEDLIST_H. When somebody uses that library and your library then you will get some funny interactions.

As a result I would make the include guards a little more unique. When I define header guards they include the full namespace and the the file name in the include guard.

Which brings me to namespace. All your work is in the global namespace. Which can lead to collision in names (Again LinkedList is a common type name). So creating a unique namespace for your code could be useful (I like the Java method of using your domain name).

#ifndef THORSANVIL_UTIL_LINKED_LIST_H
#define THORSANVIL_UTIL_LINKED_LIST_H

namespace ThorsAnvil
{
     namespace Util
     {

class LinkedList
{
};

     }
}
#endif

Containers Vs Smart Pointers

There are two common techniques for managing dynamic memory: Containers and Smart Pointers. Since the job of the container is to perform memory management so delegating this to Smart pointers is counter productive.

Secondly shared_ptr should not be your first choice of smart pointer. The shared pointer has significant overheads.

template <typename T> using ptr = std::shared_ptr<T>;

Given the choice I would prefer std::unique_ptr when you are expressing ownership, but simply use a normal RAW pointer inside function where no owner knowledge is needed.

Private Membership

template <typename V>
class LinkedList
{
private:
    class Node
    {

The class LinkedList::Node is exposed as public. Exposing this class exposes implementation details. Exposing implementation details makes your class much more brittle and harder to change.

Constructor

default constructor

    public:
        Node() : next{} {}

A default constructor. Do you need it. This can only be used when the object type V os default constructible. Conversely if the type V is not default constructible this constructor can not be used. Which would mean that certain portions of your class are unusable.

Construction

        Node(V _data) : next{}, data{_data} {}

This constructor passes _data by value. This means _data is copied into the function then it also copied again into the member. So you have multiple copies. Normally I would pass by const reference to avoid at least one copy.

Additionally in C++11 we introduced move semantics. This can thought of as an optimized copy. You should try and define your class to use move semantics so that you can remove the additional copy.

Also introduced in C++11 were variadic templates and perfect forwarding. This can be used to build objects in place using their own constructors very easily. This allows us to build the objects into the container with creating an external copy.

So if we put all three of these together I would write the Node class like this.

        struct Node
        {
            Node*   next;   // not owned.
            V       data;

            Node(V const& data)
                : next(nullptr)
                , data(data)
            {}
            Node(V&& data)
                : next(nullptr)
                , data(data)
            {}
            template<typename... Args>
            Node(Args&& args...)
                : next(nullptr)
                , data(std::forward<Args>(args)...)
            {}
        };

Head Tail Vs Sentinel

    ptr<Node> head;
    ptr<Node> tail;

Sure you can use a singly linked list and head and tail. Personally I prefer to use a doubly linked list and a sentinel (there are several other questions on code review where I explain this technique in detail).

Using a sentinel object allows you to write code without having to worry about nullptr this can considerably simplify the code.

The additional benefit (of the sentinel technique) is that you have a node in your chain that can be used by the end iterator (one past the end of the list).

Const member functions

    size_t size(){ return _size; }

    bool isEmpty(){
        if(head == nullptr) return true;
        else return false;
    }

Functions that do not mutate the state of the object should be marked const. Note: When passing around large objects to functions it is quite common to pass them by const reference. This means you can only call const methods on the object.

    size_t size() const { return _size; }

if test anti pattern

    bool isEmpty(){
        if(head == nullptr) return true;
        else return false;
    }

This is an anti pattern. There is no need to perform a test and return true/false. Simply return the value of the test.

    bool isEmpty() const
    {
        return (head == nullptr);
    }

Error

What happens when index is greater than size?

    V operator[](int index){
        int _c {};
        ptr<Node> tmp = head;
        while(tmp!=nullptr){
            if(_c == index){
                break;
            }
            tmp = tmp->getNext();
            _c++;
        }

        // I bet this de-reference a null ptr
        // Does it.
        return tmp->getData();
    }

Name your function appropriately

This may traverse the list. But that is not what it is actually doing. The traverse is just a side effect of the action you are taking.

    void traverseList(){
        {
            ptr<Node> tmp = head;
            while(tmp!=nullptr){
                std::cout << tmp->getData() << std::endl;
                tmp = tmp->getNext();
            }
        }

To me this looks like a print function name it as such. Also it always prints to std::cout. Why not pass the stream you want to print to (it can default to std::cout.

     void printList(std::ostream& str = std::cout)
     {
         // Code as before
     }
     // Then just for giggles we add a friend function to make
     // printing more C++ like.

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