Insertion of a Node

Insertion of a Node in a Linked List Data Structure

Creating a linked list using C structures and traversing through them while printing the values at each node. Today, we’ll learn how to insert a node at a specific position and how that is more efficient than inserting an element in an array.

Inserting in an array has already been covered, and the following remarks were made:

A void must be created to insert an element.
Creating a void causes the rest of the elements to shift to their adjacent right.
Time complexity: O(no. of elements shifted)

Inserting in a linked list: Consider the following Linked List,

Insertion in this list can be divided into the following categories:

Case 1: Insert at the beginning

Case 2: Insert in between

Case 3: Insert at the end

Case 4: Insert after the node

For insertion following any of the above-mentioned cases, we first need to create that extra node. Then, we overwrite the current connection and make new connections. That is how we insert a new node at our desired place.

Syntax for creating a node:

struct Node *ptr = (struct Node*) malloc (sizeof (struct Node))

The above syntax will create a node, and the next thing one would need to do is set the data for this node.

ptr -> data = 9

This will set the data.

Now, let's begin with each of these cases of insertion.

Case 1: Insert at the beginning

In order to insert the new node at the beginning, we would need to have the head pointer pointing to this new node and the new node’s pointer to the current head.

Case 2: Insert in between:

Assuming index starts from 0, we can insert an element at index i>0 as follows:

Bring a temporary pointer p pointing to the node before the element you want to insert in the linked list.
Since we want to insert between 8 and 2, we bring pointer p to 8.

Case 3: Insert at the end:

In order to insert an element at the end of the linked list, we bring a temporary pointer to the last element.

Case 4: Insert after a node:

Similar to the other cases, ptr can be inserted after a node as follows:

ptr->next = prevNode-> next;

prevNode-> next = ptr;

Summarizing, inserting at the beginning has a time complexity of O(1), while inserting at a specific node in between has a time complexity of O(n) since we have to traverse the list to reach that particular node. Inserting at the end also has a time complexity of O(n), similar to inserting in between. However, if we have the pointer to the previous node where we want to insert the new node, it would take a constant time of O(1).

Insertion in a Linked List in C Language

Now, The various cases for inserting a new node into a linked list, let’s break them down step by step and understand how to implement each case in C language.

Recap of Insertion Cases

Inserting at the Beginning
- Time Complexity: O(1)
Inserting in Between
- Time Complexity: O(n)
Inserting at the End
- Time Complexity: O(n)
Inserting After a Given Node
- Time Complexity: O(1)

Understanding the Insertion at the Beginning

Function Definition:
Create a function called insertAtFirst, which will return a pointer to the new head of the linked list.
Parameters:
This function will take two parameters: the current head pointer and the data you want to insert at the beginning.
Creating a New Node:
Inside the function, declare a pointer ptr of type struct Node* and allocate memory for it using malloc. This creates a new node in memory.
Updating Pointers:
Set the next member of the new node (ptr) to point to the current head. Then, assign the new data to the data member of ptr.
Return New Head:
Finally, return ptr as the new head of the linked list.

// Case 1
struct Node * insertAtFirst(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
 
    ptr->next = head;
    return ptr; 
}

Code Snippet 1: Implementing insertAtFirst.

Insertion in Between

Function Definition:
Create a function named insertAtIndex that will return a pointer to the head of the linked list.
Parameters:
This function will take three parameters: the current head pointer, the data to be inserted, and the index where the new node will be inserted.
Creating a New Node:
Inside the function, declare a pointer ptr of type struct Node* and allocate memory for it using malloc. This creates a new node in memory.
Traversing to the Insertion Point:
Create another pointer, also of type struct Node*, pointing to the head. Use a loop to traverse the linked list until this pointer reaches the index where the new node will be inserted.
Updating Pointers:
Set the next member of the new node (ptr) to the node currently following the pointer (p), using ptr->next = p->next. Then, assign the given data to the data member of ptr.
Breaking and Re-linking:
Update the link by breaking the connection between p and the node that follows it, and then point p->next to the new node (ptr), effectively inserting it into the list.
Return Head:
Finally, return the original head pointer, as the structure of the list remains unchanged at the top level.

// Case 2
struct Node * insertAtIndex(struct Node *head, int data, int index){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    struct Node * p = head;
    int i = 0;
 
    while (i!=index-1)
    {
        p = p->next;
        i++;
    }
    ptr->data = data;
    ptr->next = p->next;
    p->next = ptr;
    return head;
}

Code Snippet 2: Implementing insertAtIndex.

Insertion at the End

Function Definition:
Create a function named insertAtEnd that will return a pointer to the head of the linked list.
Traversing to the End:
Similar to inserting at an index, create a pointer of type struct Node* to traverse the linked list. This time, run a loop that continues until this pointer reaches the last node, which points to NULL.
Creating a New Node:
Inside the function, declare a pointer ptr of type struct Node* and allocate memory for it using malloc. This creates a new node in memory.
Assigning Values:
Set the next member of the new node (ptr) to NULL using ptr->next = NULL, indicating that it will be the last node. Then, assign the given data to the data member of ptr.
Updating the Last Node's Pointer:
Break the connection between the last node (p) and NULL by updating p->next to point to the new node (ptr), effectively inserting it at the end of the list.
Return Head:
Finally, return the original head pointer, as the structure of the list remains unchanged at the top level.

// Case 3
struct Node * insertAtEnd(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
    struct Node * p = head;
 
    while(p->next!=NULL){
        p = p->next;
    }
    p->next = ptr;
    ptr->next = NULL;
    return head;
}

Code Snippet 3: Implementing insertAtEnd.

Insertion After a Given Node

Function Definition:
Create a function named insertAfterNode that will return a pointer to the head of the linked list.
Function Parameters:
This function will accept three parameters: the head of the linked list, a pointer to the previous node (prevNode), and the data to be inserted.
Creating a New Node:
Inside the function, declare a pointer ptr of type struct Node* and allocate memory for it using malloc. This new node will be inserted after the specified node.
Using the Previous Node:
Since you already have the prevNode pointer passed as a parameter, you can directly use it as your reference point for insertion.
Assigning Values:
Set the next member of the new node (ptr) to point to the node that follows prevNode by using ptr->next = prevNode->next. Then, assign the given data to the data member of ptr.
Updating the Previous Node's Pointer:
Break the connection between prevNode and its next node by updating prevNode->next to point to the new node (ptr). This effectively inserts the new node right after prevNode.
Return Head:
Finally, return the original head pointer, as the structure of the list remains unchanged at the top level.

// Case 4
struct Node * insertAfterNode(struct Node *head, struct Node *prevNode, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
 
    ptr->next = prevNode->next;
    prevNode->next = ptr;
 
    return head;
}

Code Snippet 4: Implementing insertAfterNode.

So those were the cases we had in insertion. Below is the whole source code.

#include<stdio.h>
#include<stdlib.h>

struct Node{
    int data;
    struct Node * next;
};

void linkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

// Case 1
struct Node * insertAtFirst(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;

    ptr->next = head;
    return ptr; 
}

// Case 2
struct Node * insertAtIndex(struct Node *head, int data, int index){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    struct Node * p = head;
    int i = 0;

    while (i!=index-1)
    {
        p = p->next;
        i++;
    }
    ptr->data = data;
    ptr->next = p->next;
    p->next = ptr;
    return head;
}

// Case 3
struct Node * insertAtEnd(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
    struct Node * p = head;

    while(p->next!=NULL){
        p = p->next;
    }
    p->next = ptr;
    ptr->next = NULL;
    return head;
}

// Case 4
struct Node * insertAfterNode(struct Node *head, struct Node *prevNode, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;

    ptr->next = prevNode->next;
    prevNode->next = ptr;

    
    return head;
}


int main(){
    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;

    // Allocate memory for nodes in the linked list in Heap
    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    // Link first and second nodes
    head->data = 7;
    head->next = second;

    // Link second and third nodes
    second->data = 11;
    second->next = third;

    // Link third and fourth nodes
    third->data = 41;
    third->next = fourth;

    // Terminate the list at the third node
    fourth->data = 66;
    fourth->next = NULL;

    printf("Linked list before insertion\n");
    linkedListTraversal(head);
    // head = insertAtFirst(head, 56);
    // head = insertAtIndex(head, 56, 1);
    // head = insertAtEnd(head, 56);
    head = insertAfterNode(head, third, 45);
    printf("\nLinked list after insertion\n");
    linkedListTraversal(head);

    
    return 0;
}

Creation and Traversal

Deletion in a Linked ListTree

Insertion of a Node