Home » Data Structure

Single linked list insertion

In this article, we are going to learn how to insert a node in single linked list using C program in Data Structure?
Submitted by Radib Kar, on October 23, 2018

All possible cases:

1. Inserting at beginning
2. Inserting at the ending
3. Inserting at given position

Algorithms:

1) Inserting at the beginning

In this case, a new node is to be inserted before the current head node, i.e. , every time the node that got inserted is being updated to the head node. Such insertion can be done using following steps.

1. Update next pointer of the new node (node to be inserted) to point to the current node.
2. Update new node as head node.

2) Inserting at the ending

In such case the new node is going to be the last node, i.e. , the next pointer of the new node is going to be NULL. The steps are:

1. Set the next pointer of the new node to be NULL.
2. Last node of the existing node is linked with the new node, i.e. , the last node's(existing) next pointer points to the new node.

3) Inserting at given position

Such case can be handles using following steps:

1. Move the current pointer upto the position where node to be inserted.
2. Store current next pointer address to tmp_node next.
3. Store tmp_node address to current next.
   See the below given program...

Insertion is done.

C implementation of inserting a new node to a link list

//
//  main.c
//  linkedlist_insert_element_code
//
//  Created by Anshuman Singh on 22/06/19.
//  Copyright © 2019 Anshuman Singh. All rights reserved.
//

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

typedef struct node {
    int data;
    struct node* next;
} node;

void insert_node(node** head, int val, int position);

void insert_node(node** head, int val, int position)
{
    struct node *curr = *head, *tmp_node = NULL;
    int count = 1;

    tmp_node = (node*)malloc(sizeof(node));

    if (tmp_node == NULL) {
        printf("Memory allocation is failed:");
        return;
    }
    tmp_node->data = val;
    tmp_node->next = NULL;

    if (*head == NULL) {
        // List is empty, assigning head pointer to tmp_node
        *head = tmp_node;
        return;
    }
    if (position == 1) {
        // Inserting node at the beginning of the list
        tmp_node->next = *head;
        *head = tmp_node;
        return;
    }
    while (curr && count < position - 1) {
        curr = curr->next;
        count++;
    }
    if (position > (count + 1)) {
        printf("\n position doesn't exists in the list ");
        return;
    }
    if (count + 1 == position && curr->next == NULL) {
        // Inseting node at the end of the list
        curr->next = tmp_node;
        return;
    }
    // Inserting node in the list at given position
    tmp_node->next = curr->next;
    curr->next = tmp_node;
}

void print_list(node* head)
{
    printf("\nList elements:\n");
    while (head) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
    return;
}

int main()
{
    int num_nodes, value, index, position;
    node* head = NULL;

    printf("Enter the no. of nodes to create list: ");
    scanf("%d", &num_nodes);

    for (index = 1; index <= num_nodes; index++) {
        printf("Enter node data for position %d in the list:  ", index);
        scanf("%d", &value);
        insert_node(&head, value, index);
    }
    print_list(head);

    printf("\nInsert the element at 1st position:  ");
    scanf("%d", &value);
    insert_node(&head, value, 1);
    // We have inserted one more element, hence num_nodes get increased by 1
    num_nodes += 1;
    print_list(head);

    printf("\nInsert the element at last position:  ");
    scanf("%d", &value);
    insert_node(&head, value, num_nodes + 1);
    // We have inserted one more element, hence num_nodes will get increased by 1
    num_nodes += 1;
    print_list(head);

    printf("\nInsert the element at any position in the list\n");
    printf("Enter the position: ");
    scanf("%d", &position);
    printf("Enter the element value: ");
    scanf("%d", &value);
    insert_node(&head, value, position);
    // We have inserted one more element, hence num_nodes will get increased by 1
    num_nodes += 1;
    print_list(head);

    return 0;
}

Output

Enter the no. of nodes to create list: 5 
Enter node data for position 1 in the list:  11  
Enter node data for position 2 in the list:  22  
Enter node data for position 3 in the list:  33  
Enter node data for position 4 in the list:  44  
Enter node data for position 5 in the list:  55  
 
List elements:   
11 22 33 44 55   
 
Insert the element at 1st position:  10  
 
List elements:   
10 11 22 33 44 55
 
Insert the element at last position:  20 
 
List elements:   
10 11 22 33 44 55 20 
 
Insert the element at any position in the list   
Enter the position: 4
Enter the element value: 40  
 
List elements:   
10 11 22 40 33 44 55 20