C Program to Insert a Node in a Linked List

Inserting a node is one of the the most fundamental linked list operations. We need to insert new nodes to create a linked list in the very first place. Here we’ll see how to write C program to insert a new node into a linked list at all four possible positions:

1. At the front of the list
2. At the end of the list
3. Before a specified node
4. After a specified node

Let’s start with the data structure that represents a linked list node.

struct node {
  int val;
  struct node *next;
}

It has two parts – a) data and b) link. The data part is simply an integer here but it can be arbitrarily complex. The next variable will be used as a link to the next node. It is basically a pointer that holds the pointer of the next node. The next pointer of the last node will always point to NULL.

Insert a New Node at the Front of a Linked List

Linked list head always points to the first node if there is any. It points to NULL for an empty list. So inserting a new node means the head will point to the newly inserted node. And the new node will point to where head was pointing before insertion.

Procedure to insert a node at the front of a linked list.

• Create the new node.
• Point the new node where head is currently pointing to.
• Point head to the new node.

Here is the insert_front() function.

void insert_front(struct node **head, int value)
{
    struct node * new_node = NULL;

    /*Allocating the new node... */
    new_node = (struct node *)malloc(sizeof(struct node));

    if (new_node == NULL)
    {
        printf("Failed to insert element. Out of memory");
        return;
    }

    new_node->val = value; /*Setting the value of the node*/
    new_node->next = *head; /*Pointing the new node where head is currently pointing to*/

    *head = new_node; /*Pointing head to new element*/
}

Notice that the head is passed as double pointer (pointer-to-pointer) to the insert function. Because this head pointer will be changed inside the function to point to the newly inserted node. To change a value of a pointer from inside a function, we need to pass the double pointer.

References:

• Change variable from inside a function.
• Change a pointer from inside a function.

For the same reason, head is passed as double-pointer in few other functions also in the following examples. 

Insert a Node at the End of a Linked List

The last node of linked list always points to NULL. To insert a new node at the end of the list, you have to make the current last node point to the new node. And the new node will point to NULL. So the newly inserted node will become the last node after insertion.

Procedure to insert a node at the end of a linked list.

• Create the new node.
• Point the new node to NULL. The new node will become the last node.
• If the node is empty, then
  • Point head to the new node
• Else:
  • Traverse to the last node and point the last node to the new node.

void insert_end(struct node **head, int value)
{
    struct node * new_node = NULL;
    struct node * last = NULL;

    /*Create the new node*/
    new_node = (struct node *)malloc(sizeof(struct node));

    if (new_node == NULL)
    {
        printf("Failed to insert element. Out of memory");
        return;
    }

    new_node->val = value;
    new_node->next = NULL;

    /*No element in the linked list. So point head to the new node*/
    if( *head == NULL)
    {
        *head = new_node;
        return;
    }

    /*Traverse to the last node*/
    last = *head;
    while(last->next) last = last->next;

    /*Point last node's link (next pointer) to the new node*/
    last->next = new_node;
}

Insert the New Node after a Specified Node

The newly inserted node will become the next node a specified node. The node will be specified by the value of the node here.

For example, the new node will be inserted after 91 as shown in the diagram above.

Procedure to insert a new node after a specified node.

• Traverse to the node whose value is equal to the specified value. If no such node is found, then the insertion process would be aborted.
• Create the new node.
• Point the new node where the found node is currently pointing to.
• Point the found node’s pointer (next) to the new node.

void insert_after(struct node *head, int value, int after)
{
    struct node * new_node = NULL;
    struct node *tmp = head;

    while(tmp) {

      if(tmp->val == after) {  /*found the node*/

        new_node = (struct node *)malloc(sizeof(struct node));

        if (new_node == NULL) {
          printf("Failed to insert element. Out of memory");
        }

        new_node->val = value;
        new_node->next = tmp->next;
        tmp->next = new_node;
        return;
      }

      tmp = tmp->next;
    }
}

Insert the New Node before a Specified Node

Inserting new element before a specified node is similar to the previous example. Here the specified node will become the next node of the new node.

You have to do the following things.

• Create the new node.
• If the value of the first node ((*head)->val) is equal to the specified value.
  • Point the new node where head is currently pointing to, in other words the new node will point to the first node of the list.
  • Point head to the new node.
• Otherwise,
  • Traverse to a node (tmp->next) whose value is equal to the specified value. Insert the new node after the previous node (tmp).
  • Point the new node to the found node (tmp->next).
  • Point the previous node (tmp) to the new node.

void insert_before(struct node **head, int value, int before)
{
    struct node * new_node = NULL;
    struct node * tmp = *head;

    new_node = (struct node *)malloc(sizeof(struct node));

    if (new_node == NULL)
    {
        printf("Failed to insert element. Out of memory");
        return;
    }

    new_node->val = value;

    if((*head)->val == before)
    {
        new_node->next = *head;
        *head = new_node;
        return;
    }

    while(tmp && tmp->next) {

      if(tmp->next->val == before) {
        new_node->next = tmp->next;
        tmp->next = new_node;
        return;
      }

      tmp = tmp->next;
    }

    /*Before node not found*/
    free(new_node);
}

Putting Everything Together

Here is the complete program that inserts elements in a linked list in all 4 positions mentioned above. You can compile this program and run.

/*
File name: test.c
Compile: cc test.c
*/
#include <stdio.h>
#include <stdlib.h>

struct node{
    int val;
    struct node *next;
};

void print_list(struct node *head)
{
    printf("H->");

    while(head)
    {
        printf("%d->", head->val);
        head = head->next;
    }

    printf("|||\n\n");
}

void insert_front(struct node **head, int value)
{
    struct node * new_node = NULL;

    new_node = (struct node *)malloc(sizeof(struct node));

    if (new_node == NULL)
    {
        printf("Failed to insert element. Out of memory");
    }

    new_node->val = value;
    new_node->next = *head;

    *head = new_node;
}

void insert_end(struct node **head, int value)
{
    struct node * new_node = NULL;
    struct node * last = NULL;

    new_node = (struct node *)malloc(sizeof(struct node));

    if (new_node == NULL)
    {
        printf("Failed to insert element. Out of memory");
    }

    new_node->val = value;
    new_node->next = NULL;

    if( *head == NULL)
    {
        *head = new_node;
        return;
    }

    last = *head;
    while(last->next) last = last->next;

    last->next = new_node;
}

void insert_after(struct node *head, int value, int after)
{
    struct node * new_node = NULL;
    struct node *tmp = head;

    while(tmp) {

      if(tmp->val == after) {  /*found the node*/

        new_node = (struct node *)malloc(sizeof(struct node));

        if (new_node == NULL) {
          printf("Failed to insert element. Out of memory");
        }

        new_node->val = value;
        new_node->next = tmp->next;
        tmp->next = new_node;
        return;
      }

      tmp = tmp->next;
    }
}

void insert_before(struct node **head, int value, int before)
{
    struct node * new_node = NULL;
    struct node * tmp = *head;

    new_node = (struct node *)malloc(sizeof(struct node));

    if (new_node == NULL)
    {
        printf("Failed to insert element. Out of memory");
        return;
    }

    new_node->val = value;

    if((*head)->val == before)
    {
        new_node->next = *head;
        *head = new_node;
        return;
    }

    while(tmp && tmp->next) {

      if(tmp->next->val == before) {
        new_node->next = tmp->next;
        tmp->next = new_node;
        return;
      }

      tmp = tmp->next;
    }

    /*Before node not found*/
    free(new_node);
}

void main()
{
    int count = 0, i, val, after, before;
    struct node * head = NULL;

    printf("Enter number of elements: ");
    scanf("%d", &count);

    for (i = 0; i < count; i++)
    {
        printf("Enter %dth element: ", i);
        scanf("%d", &val);
        insert_front(&head, val);
    }

    printf("Initial List: ");
    print_list(head);

    printf("Enter a value to enter at the front of the list: ");
    scanf("%d", &val);
    insert_front(&head, val);

    printf("List after insertion: ");
    print_list(head);

    printf("Enter a value to enter at the end of the list: ");
    scanf("%d", &val);
    insert_end(&head, val);

    printf("List after insertion: ");
    print_list(head);

    printf("Enter a value to insert in the list: ");
    scanf("%d", &val);

    printf("Insert after: ");
    scanf("%d", &after);

    insert_after(head, val, after);

    printf("List after insertion: ");
    print_list(head);

    printf("Enter a value to insert in the list: ");
    scanf("%d", &val);

    printf("Insert before: ");
    scanf("%d", &before);

    insert_before(&head, val, before);

    printf("List after insertion: ");
    print_list(head);
}

Enter number of elements: 3
Enter 0th element: 55
Enter 1th element: 77
Enter 2th element: 66
Initial List: H->66->77->55->|||
Enter a value to enter at the front of the list: 10
List after insertion: H->10->66->77->55->|||
Enter a value to enter at the end of the list: 100
List after insertion: H->10->66->77->55->100->|||
Enter a value to insert in the list: 11
Insert after: 77
List after insertion: H->10->66->77->11->55->100->|||
Enter a value to insert in the list: 222
Insert before: 77
List after insertion: H->10->66->222->77->11->55->100->|||

Note: All the programming examples above are tested on Linux (Fedora) environment using cc compiler. If you have any problem in trying these examples on other systems, let us know by commenting, we’ll try to solve.

Read also: How to insert element in sorted link list.

If you also want to contribute, click here.