So what is a LinkedList? It is basically a dynamic list which doesnot have a fixed size and can grow or shrink dynamically in runtime. If we create an array normally we have to define the size and after that we cannot shrink it. So if we need to store more number of elements than the array can hold we will be in a problem. And if we store less number of elements than we will be wasting memory which is allocated and not being used. A dynamic array solves that.

A clever approach 🤓

A clever approach will be initialize an array with some fixed size. When the number of elements increases, create a new array of twice the size and copy all the elements to it and delete the old array. Similarly for shrinking we can define a threshold after which we can shrink the array. For example say after number of elements drops to 1/4 th of the capacity or size of the array we can make a new array with half of the size and copy them to that array after which we will delete the old array. This approach works by quite inefficent. We cannot just keep on creating new arrays and them copying the whole previous array to there. IT IS TIME CONSUIMG!

THE LINKED LIST 😎

So in linked list we will have Nodes. Each node holds data and a pointer to the next node. The next Node can be Null or another node which can be created dynamically in the memory. Like that we will have a chain of nodes which can be traverse using the next pointer sitting inside each and every node.

Below is a simple implementation of Linkedlist in cpp.

    #include <stdexcept>
    
    template <typename T>
    class LinkedList{
    private:
        struct Node{
            T data;
            Node *next;
            Node(T d, Node *n = nullptr):data(d), next(n){}
        };
        Node *head;
        unsigned int _length;
      
    
    public:
        LinkedList();
        ~LinkedList();
    
        void insert(T data);
        void remove(unsigned int index);
    
        int length();
        T& operator[](unsigned int index);
    
    };
    
    template <typename T>
    LinkedList<T>::LinkedList(): head(nullptr), _length(0){};
    
    template <typename T>
    LinkedList<T>::~LinkedList(){
        if(this->head == nullptr) return;
    
        while(this->head != nullptr){
            Node *temp = head;
            this->head = this->head->next;
            delete temp;
        }
    }
    
    
	
template <typename T>
void LinkedList<T>::insert(T data){
    if(this->head == nullptr){
        Node *newNode = new Node(data, nullptr);
        this->head = newNode;
        this->_length++;
        return;
    }

    Node *current = head;
    while(current->next != nullptr){
        current = current->next;
    }

    Node *newNode = new Node(data, nullptr);
    current->next = newNode;
    this->_length++;
}    
    
    template<typename T>
    void LinkedList<T>::remove(unsigned int index){
        if(index >= this->_length){
            throw std::out_of_range("List index out of range");
        }
        Node *current = this->head;
    
        if(index == 0){
            // remove the head
            Node *to_be_deleted = head;
            this->head = to_be_deleted->next;
            delete to_be_deleted;
            this->_length--;
            return;
        }
    
        while(index != 1){
            current = current->next;
            index--;
        }
        // current->next node to be deleted
    
        Node *to_be_deleted = current->next;
        Node *nextNode = to_be_deleted->next;
        current->next = nextNode;
        delete to_be_deleted;
        this->_length--;
    }
    
    
    template <typename T>
    int LinkedList<T>::length(){
        return this->_length;
    }
    
    
    template <typename T>
    T& LinkedList<T>::operator[](unsigned int index){
        if(index >= this->_length){
            throw std::out_of_range("List index out of range");
        }
        Node *current = this->head;
        while(index != 0){
            current = current->next;
            index--;
        }
        return current->data;
    }

Okay now but if you see here in the insert() method we are traversing the linked list everytime when we have to insert an element at the end. We can optmize this by keeping another pointer "tail" which will always point to the last node of the list so that we can directly jump to the last.

See bellow for the changes.

#include <stdexcept>

template <typename T>
class LinkedList{
private:
    //........
    Node *tail; // 👈🏼 We added this

//......

};


/**
*	This is the new insert method👇🏼
*/ 
template <typename T>
void LinkedList<T>::insert(T data){
    if(this->head == nullptr){
        Node *newNode = new Node(data, nullptr);
        this->head = newNode;
        this->tail = head;
        this->_length++;
        return;
    }
    Node *newNode = new Node(data, nullptr);
    this->tail->next = newNode;
    this->tail = this->tail->next;
    this->_length++;
}

template<typename T>
void LinkedList<T>::remove(unsigned int index){
    if(index >= this->_length){
        throw std::out_of_range("List index out of range");
    }
    Node *current = this->head;

    if(index == 0){
        // remove the head
        Node *to_be_deleted = head;
        this->head = to_be_deleted->next;
        delete to_be_deleted;
        this->_length--;
        return;
    }

    while(index != 1){
        current = current->next;
        index--;
    }
    // current->next node to be deleted

   
    Node *to_be_deleted = current->next;
    Node *nextNode = to_be_deleted->next;
    current->next = nextNode;
    
    if(to_be_deleted == this->tail){
        //last element, need to update the tail 👇🏼
        this->tail = current;
    }
    delete to_be_deleted;
    this->_length--;
}

Okay that's it. Now we can optmize the remove method as well. That's a little homework for you. You can comment the solution!