Implementation of the linked list data structure in C++

How is this designed so far?

```
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include
#include

template using ptr = std::shared_ptr;

template
class LinkedList
{
private:
class Node
{
private:
V data;
ptr next;
public:
Node() : next{} {}
Node(V _data) : next{}, data{_data} {}
ptr& getNext(){
return this->next;
}
V getData(){
return this->data;
}
};

ptr head;
ptr tail;
size_t _size;

public:

LinkedList() : head{}, tail {}, _size{} {}

void add(V _data){
auto _tmp = std::make_shared(_data);
if(isEmpty()){
head = _tmp;
tail = _tmp;
} else {
tail->getNext() = _tmp;
tail = _tmp;
}
_size++;
}

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

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

void addFirst(V _data){
auto _tmp = std::make_shared(_data);
if(isEmpty()){
_tmp->getNext() = head;
head = _tmp;
tail = _tmp;
} else {
_tmp->getNext() = head;
head = _tmp;
}
_size++;
}

template
void insertAfter(int index, V _data){

auto _tmp = std::make_shared(_data);
std::shared_ptr _curr;
std::shared_ptr _afterIndex;

if(index size()-1){std::cerr tmp = head;
while(tmp!=nullptr){
if(_c == index){
_curr = tmp;
_afterIndex = _curr->getNext();
break;
}
tmp = tmp->getNext();
_c++;
}

_curr->getNext(

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  using ptr = std::shared_ptr;

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 
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
            Node(Args&& args...)
                : next(nullptr)
                , data(std::forward(args)...)
            {}
        };

Head Tail Vs Sentinel

ptr head;
    ptr 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 tmp = head;
while(tmp!=nullptr){
if(_c == index){
break;
}
tmp = tmp->getNext();
_c++

StackExchange Code Review Q#140277, answer score: 12