Insert node at middle of linked list in c

Linked list are useful data structure, If you are hold the reference of front and rear by pointer then possible to get that element directly. Otherwise there are not possible to get random position elements.

That reason there is most asking question are, how to insert node at middle of given linked list. Normally there are two solution of this problem.

First method : counting all linked list node using one traversal. So we are know about exectly, how many node are exist in this linked list. And in a second traversal start to head and iterative loop are (count/2) times and get middle node. And insert new node to that position (modifying of pointer position when inserted node).

That is basic method you can try this approach. This process time complexity is O(n). But note that in this approach every node at almost 2 times are have traversal. Next method are do this task in single traversal.

Method two: Use two pointer (temp,middle) both are assigning the value of head pointer reference. visited of temp pointer are (temp->next->next) two times when temp are not NULL and temp->next are not NULL and temp->next->next not NULL. Respective to visit middle pointer to (middle->next). When temp is NULL or temp->next==NULL and temp->next->next are NULL then terminated the loop. And help of middle pointer add new node to middle position.

Suppose we are inserted the following (1, 2, 3, 4, 5, 6, 7) node in a sequence. In this post are implement second approach.

insert linked list node in middle position
// C Program for
// Insert linked list node at middle of linked list
#include <stdio.h>

#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
    int data;
    struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
    struct LinkNode *head;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
    // Create new linked list
    struct SingleLL *sll = (struct SingleLL *)
    malloc(sizeof(struct SingleLL));
    if (sll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        sll->head = NULL;
    }
    return sll;
}
// Handles the request of adding new node at middle of linked list
void addNode(struct SingleLL *sll, int data)
{
    // Create dynamic node
    struct LinkNode *node = (struct LinkNode *)
    malloc(sizeof(struct LinkNode));
    if (node == NULL)
    {
        printf("Memory overflow to Create LinkNode\n");
        return;
    }
    else
    {
        // Set initial node value
        node->data = data;
        node->next = NULL;
    }
    if (sll->head == NULL)
    {
       // Add first node
        sll->head = node;
    }
    else
    {
        struct LinkNode *temp = sll->head;
        struct LinkNode *middle = sll->head;
        // Find middle node
        while (temp && temp->next != NULL && temp->next->next != NULL)
        {
            temp = temp->next->next;
            middle = middle->next;
        }
        // Insert node into the middle of the linked list
        node->next = middle->next;
        middle->next = node;
    }
}
// Display linked list element
void display(struct LinkNode *node)
{
    if (node == NULL)
    {
        return;
    }
    struct LinkNode *temp = node;
    // iterating linked list elements
    while (temp != NULL)
    {
        printf(" %d →", temp->data);
        // Visit to next node
        temp = temp->next;
    }
    printf(" NULL\n");
}
int main()
{
    struct SingleLL *sll = newLinkedList();
    // Insert element of linked list
    addNode(sll, 1);
    addNode(sll, 2);
    addNode(sll, 3);
    addNode(sll, 4);
    addNode(sll, 5);
    addNode(sll, 6);
    addNode(sll, 7);
    // Display all node
    display(sll->head);
    return 0;
}
 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved