# LinkedList DataStructure

> *Linked lists are a fundamental data structure in computer science, providing a flexible way to store and manage data.*
> 
> *Unlike arrays, linked lists do not require a contiguous block of memory, allowing for efficient insertion and deletion of elements. In this post, we will dive deep into building a linked list from scratch .*
> 
> *We will cover the basic operations such as insertion, deletion, and traversal, providing a clear understanding of how linked lists work under the hood. By the end of this tutorial, you will have a robust implementation of a linked list and a solid grasp of this essential data structure.*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1720257566451/49445ffa-2403-4c73-a17e-50552d1807c7.png align="center")

#### *Table of Content :*

1. Designing Node Class
    
2. Designing LinkedList Class
    
3. Designning Client Class\[Basically Main Class where we trigger linkedlist operations\]
    

**Designing Node Class**

> In order to build a linked list class, you'll typically define a structure or a class to represent the nodes of the linked list. Each node should contain two essential members:
> 
> 1. **Value**: The actual data or value that the node holds.
>     
> 2. **Address (Pointer to the Next Node)**: A reference or pointer to the next node in the linked list.
>     

```cpp
// Node class represents a single node in the linked list
class Node {
public:
    int data;    /*Data or value held by the node*/
    Node* next;  /*Reference to the next node in the linked list*/

    /* Constructor to initialize a node with a given value */
    Node(int data) {
        this->data = data;
        this->next = nullptr; /*By default, the next node is set to null*/
    }
};
```

2\. Designing LinkedList Class

> Develop a separate `LinkedList` class to manage the overall structure of the linked list.
> 
> It has all operations/methods : **Insertion, Deletion, Traversal** operations

The below one will be the overall template :

```cpp
class LinkedList {
  
private:
    Node* head;
    int length;

public:
    LinkedList() {
        head = nullptr;
        length = 0;
    }

    int size() 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    Node* getHead() 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void insertNodeAtBeginning(int data) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void insertNode(int data, int indexPosition) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void insertNodeAtMid(int data) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void insertNodeAtEnding(int data) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void insertNodeAtStart(int data) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void displayList() {
        /*...............................
                 Implementation 
        .................................*/
    }
    void deleteNode(int indexPosition) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void deleteNodeAtMid(Node* head) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void deleteNodeAtEnd(Node* head) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
    void deleteNodeAtStart(Node* head) 
    {
        /*...............................
                 Implementation 
        .................................*/
    }
};
```

#### Implementation for Insertion Operations

1. Insertion of newNode at start(head) position
    
2. Insertion of newNode at end(tail) position
    
3. Insertion of newNode at mid position
    

#### Insertion of newNode at Start(Head) Position

**Intuition :**

> * **Step 1**: Create a **newNode** with the given value/data.
>     
> * **Step 2**: Link the new node's `next` pointer to the current head
>     
> * **Step 3**: Update the **head** to point to the **newNode**.
>     
> * **Step 4**: Increment the length of the list (if the length is being tracked).
>     

**Psudo Code :**

```plaintext
insertNodeAtBeginning(head, data):
    Create a new node with the given data
    Set newNode's next to head
    Set head to newNode
    increment the length
```

Code Snippet :

```cpp
    void insertNodeAtBeginning(int data) 
    {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
        length++;
    }
```

**Intuition :**

> * **Step 1**: Create a **newNode** with the given value/data.
>     
> * **Step 2**: Check if the **head** node is null, and if it null then update the **head** to point to the **newNode**.
>     
> * **Step 3**: If **head** is not null then create a **temporaryHead** that points to head.
>     
> * **Step 4** : Iterate through the list, till you reached last element(not null).
>     
> * **Step 5** : Update the **lastNode’s** next points to **newNode**
>     
> * **Step 4**: Increment the length of the list (if the length is being tracked).
>     

**Psudo Code :**

```cpp
insertNodeAtEnding(head, data):
    Create a new node with the given data
    If head is null:
        Set head to new node
    Else:
        Create a temporary pointer temp that points to head
        While temp.next is not null:
            Move temp to temp.next
        Set temp.next to new node
    Increment the length
```

**Code Snippet :**

```cpp
    void insertNodeAtEnding(int data) 
    {
        if (head == nullptr) 
        {
            insertNodeAtBeginning(data);
            return;
        }

        Node* newNode = new Node(data);
        Node* tempNode = head;

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

        tempNode->next = newNode;
        length++;
    }
```

#### Insertion of newNode at mid Position

**Intuition :**

> * **Step 1**: Create a **newNode** with the given value/data.
>     
> * **Step 2**: **Calculate the middle position**:
>     
>     * If the length of the list is even, the middle position is `length/2`**.**
>         
>     * If the length of the list is odd, the middle position is `(length/2) + 1`.
>         
> * **Step 3**: **Traverse the list** to find the middle node:
>     
>     * Decrement the middle position counter (`mid`) as you move through the list.
>         
>     * When `mid` reaches 0, you have found the middle node.
>         
> * **Step 4** : **Insert the new node**:
>     
>     * Update the `next` pointer of the **middleNode** to point to the new node.
>         
>     * Update the `next` pointer of the **newNode** to point to the node that was originally after the **middleNode**.
>         
> * **Step 5**: Increment the length of the list (if the length is being tracked).
>     

**Psudo Code :**

```plaintext
insertNodeAtMid(head, data):
    Calculate mid position based on length:
        if length is even:
            mid = length / 2
        else:
            mid = (length / 2) + 1

    Create a new node with the given data

    Initialize middleNode to head

    Traverse the list to find the middle position:
        while middleNode is not null:
            Decrement mid by 1
            if mid equals 0:
                break
            Move middleNode to the next node

    Insert the new node:
        Set newNode's next to middleNode's next
        Set middleNode's next to newNode

    Increment the length of the list
```

**Code Snippet :**

```cpp
    void insertNodeAtMid(int data) 
    {
        int mid = (length % 2 == 0) ? length / 2 : (length / 2) + 1;
        Node* newNode = new Node(data);

        Node* middleNode = head;
        while (middleNode != nullptr) 
        {
            mid--;
            if (mid == 0) 
            {
                break;
            }
            middleNode = middleNode->next;
        }

        Node* nextNode = middleNode->next;
        middleNode->next = newNode;
        newNode->next = nextNode;
        length++;
    }
```

---

Full Code Snippet :

```cpp
#include <iostream>

class Node {
public:
    int data;
    Node* next;
    
    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class LinkedList {
  
private:
    Node* head;
    int length;

public:
    LinkedList() {
        head = nullptr;
        length = 0;
    }

    void insertNodeAtBeginning(int data) 
    {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
        length++;
    }

    void insertNodeAtMid(int data) 
    {
        int mid = (length % 2 == 0) ? length / 2 : (length / 2) + 1;
        Node* newNode = new Node(data);

        Node* middleNode = head;
        while (middleNode != nullptr) 
        {
            mid--;
            if (mid == 0) 
            {
                break;
            }
            middleNode = middleNode->next;
        }

        Node* nextNode = middleNode->next;
        middleNode->next = newNode;
        newNode->next = nextNode;
        length++;
    }

    void insertNodeAtEnding(int data) 
    {
        if (head == nullptr) 
        {
            insertNodeAtBeginning(data);
            return;
        }

        Node* newNode = new Node(data);
        Node* tempNode = head;

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

        tempNode->next = newNode;
        length++;
    }

    void displayList() 
    {
        Node* tempNode = head;
        while (tempNode != nullptr) 
        {
            std::cout << tempNode->data << "-->";
            tempNode = tempNode->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() 
{
    LinkedList* list = new LinkedList();  
    list->insertNodeAtBeginning(10);
    list->insertNodeAtBeginning(20);
    list->insertNodeAtBeginning(30);
    list->insertNodeAtEnding(40);
    list->insertNodeAtEnding(50);
    list->insertNodeAtMid(100);

    list->displayList();

    delete list;
    return 0;
}
```

---

*By mastering these insertion techniques, one can effectively manage and manipulate linked lists. Whether adding elements at the start, end, or middle, these operations are essential for efficient data handling and manipulation in linked lists.*

*In the next post, we will delve into deletion operations performed on linked lists.*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1720258240388/b8e2268a-cf94-4a7b-ae50-ac1a613b6567.png align="center")