• Register
100 points
5 1

In this article,we will discuss four different types of insertion we can do in a linked list.In my previous article,  I have dicussed how to create linked list if you have not gone through yet then i request you to please go through that first.After that come to this blog for proper understanding.

These are following four different ways :

  1. Insert a node at a very begining.
  2. Insert a node at given index.
  3. Insert a node at end.
  4. Insert a node after some node.

Code Logic

  1. For node insertion at beginning, we need to point the node ptr(node to be inserted) to head and update the head to ptr.
  2. For 2nd case,bring the pointer p before the element you want to insert in linked list.
  3. For 3rd case, bring the pointer p last element.
  4. For 4th case,just like other cases ptr is inserted after a node in a linked list.

Code

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node *next; //self referencing node
};

void linkedListTransversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element:%d\n", ptr->data);
        ptr = ptr->next;
    }
}
//case 1
struct Node * insertionAtFirst(struct Node *head,int data){
    struct Node *ptr=(struct Node *)malloc(sizeof(struct Node));
    ptr->next=head;
    ptr->data=data;
    return ptr;
}
//case 2
struct Node * insertionAtIndex(struct Node *head,int data,int index){
    struct Node *ptr=(struct Node *)malloc(sizeof(struct Node));
    struct Node *p=head;//preserving head
    int i=0;
    while(i!=index){
        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));
    struct Node *p=head;//preserving head
    ptr->data=data;
    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));
    struct Node *p=head;//preserving head
    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;
    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));

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = fourth;

    fourth->data = 40;
    fourth->next = NULL;

    linkedListTransversal(head);
    printf("\n");
    head = insertionAtFirst(head,5);
    head = insertionAtIndex(head,5,2);
    head = insertAtEnd(head,5);
    head = insertAfterNode(head,second,5);
    linkedListTransversal(head);
    return 0;
}