Insertion in Linked List | Linked List Operations

30 min read

Insertion in Linked List can happen at various places in a Linked List. A few cases are:

  • At the beginning of the linked list.
  • At the middle of the linked list.
  • At the end of the linked list.
  • At a given position in the linked list.

Now let us look at a program for each of these cases.

 

Insertion at the beginning of the Linked List

insertion-beginning-linked-list

  • Let us assume a newNode as shown above. The newNode with data=5 has to be inserted at the beginning of the linked list.
  • For this to happen, the address part of the newNode should point to the address of the head node. Once it points to the head node, then the newNode is made as the head node as shown above.

 

Program to insert a node at the beginning of the Linked List

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

// Creating node with data and a pointer

struct node {
int data;
struct node *next;
}*head;
void createList(int n);
void insert_at_beginning(int data);
void displayList();

int main()
{
int n, data;
printf("\nEnter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nThe List is \n");
displayList();
printf("\nEnter data to insert at beginning of the list: ");
scanf("%d", &data);
insert_at_beginning(data);
printf("\n\nThe List is \n");
displayList();
return 0;
}

/* A function to create a linked list with the specified number of nodes */

void createList(int n)
{
struct node *newNode, *temp;
int data, i;
head = (struct node *)malloc(sizeof(struct node));

// When the list is empty
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
}
}

/* Function for inserting data at the beginning of the list */

void insert_at_beginning(int data_value)
{
struct node* temp = (struct node*)malloc(sizeof(struct node)); // Allocating memory to the node
temp -> data = data_value; // Assigning the given data to the newNode
temp -> next = head; //newNode is added
head = temp; //newNode is made as the head node
}

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}

 

OUTPUT


insert-node-beginning

 

Insertion at the end of the linked list

insertion-end-linked-list

  • Now let us assume a newNode as shown above. The newNode with data = 5 has to be inserted at the end of the linked list.
  • Now, start traversing the list and continue traversing until the address part of the node is NULL.
  • Once the address part of a node is found to be NULL, then make the address part of that node to point to the address of the newNode and the address part of the newNode is referenced to NULL. Hence it becomes the last node.

 

Program to insert a node at the end of the Linked List

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

//Creating node with data and a pointer

struct node {
int data;
struct node *next;
}*head;
void createList(int n);
void insert_node_end(int data);
void displayList();

int main()
{
int n, data;
printf("\nEnter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nThe List is \n");
displayList();
printf("\nEnter data to insert at end of the list: ");
scanf("%d", &data);
insert_node_end(data);
printf("\n\nThe List is \n");
displayList();
return 0;
}



/* A function to create a linked list with the specified number of nodes */

void createList(int n)
{
struct node *newNode, *temp;
int data, i;
head = (struct node *)malloc(sizeof(struct node));
// When the list is empty
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
}
}

/* Function for inserting data at the end of the list */

void insert_node_end(int data)
{
struct node *newNode, *temp;
newNode = (struct node*)malloc(sizeof(struct node)); //Allocating memory to the node
if(newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->data = data; // Assigning data to the newNode
newNode->next = NULL;
temp = head;
// Traverse to the end of the list
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode; // newNode is made as the last node
}
}

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
//Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}

 

OUTPUT

insert-node-end

 

Insertion at a given position in the linked list

insertion-given-position-linked-list

  • Now let us assume that a newNode with data = 25 has to be inserted at the 2nd position in the linked list.
  • Start traversing the list from the head and move up to the position - 1. In this case, since we want to insert at 2nd position, you need to traverse till (2-1) = 1.
  • Once you reach the position-1 node, the address part of the newNode is set to the address contained by the position – 1 node.
  • Now, the address part of the position – 1 node is made to point to the newNode.

 

Program to insert a node at a given position in the Linked List

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

// Creating node with data and a pointer
struct node {
int data;
struct node *next;
}*head;
void createList(int n);
void insert_at_given_position(int data, int position);
void displayList();

int main()
{
int n, data, pos;
printf("\nEnter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nThe List is \n");
displayList();
printf("\nEnter the position : ");
scanf("%d",&pos);
printf("\nEnter data to insert at position %d of the list: ",pos);
scanf("%d", &data);
insert_at_given_position(data, pos);
printf("\n\nThe List is \n");
displayList();
return 0;
}



/* A function to create a linked list with the specified number of nodes */


void createList(int n)
{
struct node *newNode, *temp;
int data, i;
head = (struct node *)malloc(sizeof(struct node));
// When the list is empty
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}}}}



/* Function for inserting data at given position in the list */


void insert_at_given_position(int data, int position)
{
int count = 0;
struct node *newNode, *temp;
newNode = (struct node*)malloc(sizeof(struct node)); // Allocate memory for the node
if(newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
temp = head;
// Traverse to the given position in the list
while(temp->next != NULL and ((position - 1) != count))
{
temp = temp->next;
count = count + 1;
}
//Insert the element at the position
if( (position - 1) == count)
{
newNode->data = data;
newNode->next = temp->next; //Link the inserted node with the next node 
temp->next = newNode; // Link the previous node and the inserted node
}
}
}

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
//Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}


OUTPUT

insert-node-given-pos

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error