C program to insert node at the middle of Singly Linked List

Write a C program to create a singly linked list of n nodes and insert a new node at the middle of the linked list at nth position. How to insert new node at the middle of a singly linked list in C. Algorithm to insert a new node in middle of a singly linked list. Steps to insert new node at any position in singly linked list.

Singly linked list

Required knowledge

Basic C programming, Functions, Singly linked list, Dynamic memory allocation

Algorithm to insert node at the middle of singly Linked List

Algorithm to insert node at the middle of Singly Linked List
%% Input : n position to insert data in the list
Begin:
    createSinglyLinkedList (head)
    alloc (newNode)
    If (newNode == NULL) then
        write ('Unable to allocate memory.')
    End if
    Else then
        read (data)
        newNode.datadata
        temphead
        For i ← 2 to n-1
            temptemp.next
            If (temp == NULL) then
                break
            End if
        End for
        If (temp != NULL) then
            newNode.nexttemp.next
            temp.nextnewNode
        End if
    End else
End

Steps to insert node at the middle of Singly Linked List

  1. Create a new node.

    Insertion of node at middle of singly linked list1

  2. Traverse to the n-1th position of the linked list and connect the new node with the n+1th node. Means the new node should also point to the same node that the n-1th node is pointing to. (newNode->next = temp->next where temp is the n-1th node).

    Insertion of node at middle of singly linked list2

  3. Now at last connect the n-1th node with the new node i.e. the n-1th node will now point to new node. (temp->next = newNode where temp is the n-1th node).

    Insertion of node at middle of singly linked list3

Program to insert node at the middle of Singly Linked List

/**
 * C program to insert new node at the middle of Singly Linked List
 */

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


/* Structure of a node */
struct node {
    int data;          // Data 
    struct node *next; // Address 
}*head;


void createList(int n);
void insertNodeAtMiddle(int data, int position);
void displayList();


int main()
{
    int n, data, position;

    /*
     * Create a singly linked list of n nodes
     */
    printf("Enter the total number of nodes: ");
    scanf("%d", &n);
    createList(n);

    printf("\nData in the list \n");
    displayList();

    /*
     * Insert data at middle of the singly linked list
     */
    printf("nEnter data to insert at middle of the list: ");
    scanf("%d", &data);
    printf("Enter the position to insert new node: " );
    scanf("%d", &position);
    insertNodeAtMiddle(data, position);

    printf("\nData in the list \n");
    displayList();

    return 0;
}



/*
 * Create a list of n nodes
 */
void createList(int n)
{
    struct node *newNode, *temp;
    int data, i;

    head = (struct node *)malloc(sizeof(struct node));

    /*
     * If unable to allocate memory for head node
     */
    if(head == NULL)
    {
        printf("Unable to allocate memory.");
    }
    else
    {
        /*
         * Input data of node from the user
         */
        printf("Enter the data of node 1: ");
        scanf("%d", &data);

        head->data = data; // Link the data field with data
        head->next = NULL; // Link the address field to NULL

        temp = head;

        /*
         * Creates n nodes and adds to linked list
         */
        for(i=2; i<=n; i++)
        {
            newNode = (struct node *)malloc(sizeof(struct node));

            /* If memory is not allocated for newNode */
            if(newNode == NULL)
            {
                printf("Unable to allocate memory.");
                break;
            }
            else
            {
                printf("Enter the data of node %d: ", i);
                scanf("%d", &data);

                newNode->data = data; // Link the data field of newNode with data
                newNode->next = NULL; // Link the address field of newNode with NULL

                temp->next = newNode; // Link previous node i.e. temp to the newNode
                temp = temp->next;
            }
        }

        printf("SINGLY LINKED LIST CREATED SUCCESSFULLY\n");
    }
}



/*
 * Creates a new node and inserts at middle of the linked list.
 */
void insertNodeAtMiddle(int data, int position)
{
    int i;
    struct node *newNode, *temp;

    newNode = (struct node*)malloc(sizeof(struct node));

    if(newNode == NULL)
    {
        printf("Unable to allocate memory.");
    }
    else
    {
        newNode->data = data; // Link data part
        newNode->next = NULL;

        temp = head;

        /* 
         * Traverse to the n-1 position 
         */
        for(i=2; i<=position-1; i++)
        {
            temp = temp->next;

            if(temp == NULL)
                break;
        }

        if(temp != NULL)
        {
            /* Link address part of new node */
            newNode->next = temp->next; 

            /* Link address part of n-1 node */
            temp->next = newNode;

            printf("DATA INSERTED SUCCESSFULLY\n");
        }
        else
        {
            printf("UNABLE TO INSERT DATA AT THE GIVEN POSITION\n");
        }
    }
}


/*
 * Display entire list
 */
void displayList()
{
    struct node *temp;

    /*
     * If the list is empty i.e. head = NULL
     */
    if(head == NULL)
    {
        printf("List is empty.");
    }
    else
    {
        temp = head;
        while(temp != NULL)
        {
            printf("Data = %d\n", temp->data); // Print data of current node
            temp = temp->next;                 // Move to next node
        }
    }
}

Output

Enter the total number of nodes: 4
Enter the data of node 1: 10
Enter the data of node 2: 20
Enter the data of node 3: 40
Enter the data of node 4: 50
SINGLY LINKED LIST CREATED SUCCESSFULLY

Data in the list
Data = 10
Data = 20
Data = 40
Data = 50

Enter data to insert at middle of the list: 30
Enter the position to insert new node: 3
DATA INSERTED SUCCESSFULLY

Data in the list
Data = 10
Data = 20
Data = 30
Data = 40
Data = 50

Happy coding 😉

About Pankaj

Pankaj Prakash is the founder, editor and blogger at Codeforwin. He loves to learn new techs and write programming articles especially for beginners. He works at Vasudhaika Software Sols as a Software Design Engineer and manages Codeforwin. In short Pankaj is Web developer, Blogger, Learner, Tech and Music lover.

Follow on: Facebook | Twitter | Google | or

Comments and discussion
Have a doubt, write here. I will help my best.
Before commenting you must escape your source code before commenting. Paste your source code inside
<pre><code> ----Your Source Code---- </code></pre>