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.

Singly linked list

Required knowledge:

Basic C programming, 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 new node at the middle of singly linked list

  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 new node at the middle of a singly linked list

  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).



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 part
    struct node *next; //Address part
}*head;



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



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

    /*
     * Creates 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();

    /*
     * Inserts 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
    {
        /*
         * Reads data of node from the user
         */
        printf("Enter the data of node 1: ");
        scanf("%d", &data);

        head->data = data; //Links the data field with data
        head->next = NULL; //Links 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; //Links the data field of newNode with data
                newNode->next = NULL; //Links the address field of newNode with NULL

                temp->next = newNode; //Links 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; //Links the 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)
        {
            /* Links the address part of new node */
            newNode->next = temp->next; 

            /* Links the 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");
        }
    }
}



/*
 * Displays the 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); //Prints the data of current node
            temp = temp->next; //Advances the position of current 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 ;)


Any doubt or suggestion write here. I will try my best to help. Before posting your code you must escape it to view. To format your source code and use format highlighting, post your source code inside
< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).

No comments:

Post a Comment