C program to insert node in a Doubly linked list

Write a C program to create a doubly linked list and insert a new node in beginning, end or at any position in the list. How to insert a new node at beginning of a Doubly linked list. How to insert a new node at the end of a doubly linked list. How to insert a new node at any position of a doubly linked list in C. Algorithm to insert node in a doubly linked list.

Insertion of new node in a doubly linked list

Required knowledge

Basic C programming, Functions, Dynamic memory allocation, Doubly linked list

Algorithm to insert node at the beginning of a Doubly linked list

Algorithm to insert a node at the beginning of a Doubly linked list
%% Input : head {A pointer pointing to the first node of the list}
Begin:
    alloc (newNode)
    If (newNode == NULL) then
        write ('Unable to allocate memory')
    End if
    Else then
        read (data)
        newNode.datadata;
        newNode.prevNULL;
        newNode.nexthead;

        head.prevnewNode;
        headnewNode;
        write('Node added successfully at the beginning of List')
    End else
End

Algorithm to insert node at the end of a Doubly linked list

Algorithm to insert a node at the end of Doubly linked list
%% Input : last {Pointer to the last node of doubly linked list}
Begin:
    alloc (newNode)
    If (newNode == NULL) then
        write ('Unable to allocate memory')
    End if
    Else then
        read (data)
        newNode.datadata;
        newNode.nextNULL;
        newNode.prevlast;
        
        last.nextnewNode;
        lastnewNode;
        write ('Node added successfully at the end of List')
    End else
End

Algorithm to insert node at any position of a Doubly linked list

Algorithm to insert node at any position of doubly linked list
%% Input : head {Pointer to the first node of doubly linked list}
        : last {Pointer to the last node of doubly linked list}
        : N {Position where node is to be inserted}
Begin:
    temphead
    For i←1 to N-1 do
        If (temp == NULL) then
            break
        End if
        temptemp.next;
    End for
    If (N == 1) then
        insertAtBeginning()
    End if
    Else If (temp == last) then
        insertAtEnd()
    End if
    Else If (temp != NULL) then
        alloc (newNode)
        read (data)
        
        newNode.datadata;
        newNode.nexttemp.next
        newNode.prevtemp
        If (temp.next != NULL) then
            temp.next.prevnewNode;
        End if
        temp.nextnewNode;
        write('Node added successfully')
    End if
End

Steps to insert a new node in Doubly linked list

We have supposed that we want to insert a node at 3rd position.

  1. Traverse to N-1 node in the list. Where N is the position to insert. Say temp now points to N-1th node.
    Insertion of new node in doubly linked list step 1

  2. Create a newNode that is to be inserted and assign some data to its data field.
    Insertion of new node in doubly linked list step 2

  3. Connect the next address field of newNode with the node pointed by next address field of temp node.
    Insertion of new node in doubly linked list step 3

  4. Connect the previous address field of newNode with the temp node.
    Insertion of new node in doubly linked list step 4

  5. Check if temp->next is not NULL then, connect the previous address field of node pointed by temp.next to newNode.
    Insertion of new node in doubly linked list step 5

  6. Connect the next address field of temp node to newNode i.e. temp->next will now point to newNode.
    Insertion of new node in doubly linked list step 6

  7. Final list
    Insertion of new node in double linked list step 7

Program to insert a node in doubly linked list

/**
 * C program to insert a node in Doubly linked list
 */

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


/*
 * Basic structure of Node
 */
struct node {
    int data;
    struct node * prev;
    struct node * next;
}*head, *last;


/*
 * Function used in this program
 */
void createList(int n);
void displayList();
void insertAtBeginning(int data);
void insertAtEnd(int data);
void insertAtN(int data, int position);


int main()
{
    int n, data, choice=1;

    head = NULL;
    last = NULL;

    /*
     * Run forever until user chooses 0
     */
    while(choice != 0)
    {
        /*
         * Menu creation to use the program
         */
        printf("============================================\n");
        printf("DOUBLY LINKED LIST PROGRAM\n");
        printf("============================================\n");
        printf("1. Create List\n");
        printf("2. Insert node - at beginning\n");
        printf("3. Insert node - at end\n");
        printf("4. Insert node - at N\n");
        printf("5. Display list\n");
        printf("0. Exit\n");
        printf("--------------------------------------------\n");
        printf("Enter your choice : ");

        scanf("%d", &choice);

        /*
         * Choose from different menu operation
         */
        switch(choice)
        {
            case 1:
                printf("Enter the total number of nodes in list: ");
                scanf("%d", &n);

                createList(n);
                break;
            case 2:
                printf("Enter data of first node : ");
                scanf("%d", &data);

                insertAtBeginning(data);
                break;
            case 3:
                printf("Enter data of last node : ");
                scanf("%d", &data);

                insertAtEnd(data);
                break;
            case 4:
                printf("Enter the position where you want to insert new node: ");
                scanf("%d", &n);
                printf("Enter data of %d node : ", n);
                scanf("%d", &data);

                insertAtN(data, n);
                break;
            case 5:
                displayList();
                break;
            case 0:
                break;
            default:
                printf("Error! Invalid choice. Please choose between 0-5");
        }

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

    return 0;
}


/**
 * Creates a doubly linked list of n nodes.
 * @n Number of nodes to be created
 */
void createList(int n)
{
    int i, data;
    struct node *newNode;

    if(n >= 1)
    {
        /*
         * Create and link the head node
         */
        head = (struct node *)malloc(sizeof(struct node));

        printf("Enter data of 1 node: ");
        scanf("%d", &data);

        head->data = data;
        head->prev = NULL;
        head->next = NULL;

        last = head;

        /*
         * Create and link rest of the n-1 nodes
         */
        for(i=2; i<=n; i++)
        {
            newNode = (struct node *)malloc(sizeof(struct node));

            printf("Enter data of %d node: ", i);
            scanf("%d", &data);

            newNode->data = data;
            newNode->prev = last; // Link new node with the previous node
            newNode->next = NULL;

            last->next = newNode; // Link previous node with the new node
            last = newNode;          // Make new node as last/previous node
        }

        printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");
    }
}


/**
 * Display content of the list from beginning to end
 */
void displayList()
{
    struct node * temp;
    int n = 1;

    if(head == NULL)
    {
        printf("List is empty.\n");
    }
    else
    {
        temp = head;
        printf("DATA IN THE LIST:\n");

        while(temp != NULL)
        {
            printf("DATA of %d node = %d\n", n, temp->data);

            n++;

            /* Move the current pointer to next node */
            temp = temp->next;
        }
    }
}


/**
 * Inserts a new node at the beginning of the doubly linked list
 * @data Data of the first node i.e. data of the new node
 */
void insertAtBeginning(int data)
{
    struct node * newNode;

    if(head == NULL)
    {
        printf("Error, List is Empty!\n");
    }
    else
    {
        newNode = (struct node *)malloc(sizeof(struct node));

        newNode->data = data;
        newNode->next = head; // Point to next node which is currently head
        newNode->prev = NULL; // Previous node of first node is NULL

        /* Link previous address field of head with newnode */
        head->prev = newNode;

        /* Make the new node as head node */
        head = newNode;

        printf("NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST\n");
    }
}


/**
 * Inserts a new node at the end of the doubly linked list
 * @data Data of the last node i.e data of the new node
 */
void insertAtEnd(int data)
{
    struct node * newNode;

    if(last == NULL)
    {
        printf("Error, List is empty!\n");
    }
    else
    {
        newNode = (struct node *)malloc(sizeof(struct node));

        newNode->data = data;
        newNode->next = NULL;
        newNode->prev = last;

        last->next = newNode;
        last = newNode;

        printf("NODE INSERTED SUCCESSFULLY AT THE END OF LIST\n");
    }
}


/**
 * Inserts a node at any position in the doubly linked list
 * @data Data of the new node to be inserted
 * @position Position where to insert the new node
 */
void insertAtN(int data, int position)
{
    int i;
    struct node * newNode, *temp;

    if(head == NULL)
    {
        printf("Error, List is empty!\n");
    }
    else
    {
        temp = head;
        i=1;

        while(i<position-1 && temp!=NULL)
        {
            temp = temp->next;
            i++;
        }

        if(position == 1)
        {
            insertAtBeginning(data);
        }
        else if(temp == last)
        {
            insertAtEnd(data);
        }
        else if(temp!=NULL)
        {
            newNode = (struct node *)malloc(sizeof(struct node));

            newNode->data = data;
            newNode->next = temp->next; // Connect new node with n+1th node
            newNode->prev = temp;          // Connect new node with n-1th node

            if(temp->next != NULL)
            {
                /* Connect n+1th node with new node */
                temp->next->prev = newNode;
            }
            /* Connect n-1th node with new node */
            temp->next = newNode;

            printf("NODE INSERTED SUCCESSFULLY AT %d POSITION\n", position);
        }
        else
        {
            printf("Error, Invalid position\n");
        }
    }
}
============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 1
Enter the total number of nodes in list: 3
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30DOUBLY LINKED LIST CREATED SUCCESSFULLY




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 10
DATA of 2 node = 20
DATA of 3 node = 30




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 2
Enter data of first node : 1
NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 1
DATA of 2 node = 10
DATA of 3 node = 20
DATA of 4 node = 30




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 3
Enter data of last node : 40
NODE INSERTED SUCCESSFULLY AT THE END OF LIST




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 1
DATA of 2 node = 10
DATA of 3 node = 20
DATA of 4 node = 30
DATA of 5 node = 40




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 4
Enter the position where you want to insert new node: 3
Enter data of 3 node : 15
NODE INSERTED SUCCESSFULLY AT 3 POSITION




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 5
DATA IN THE LIST:
DATA of 1 node = 1
DATA of 2 node = 10
DATA of 3 node = 15
DATA of 4 node = 20
DATA of 5 node = 30
DATA of 6 node = 40




============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Insert node - at beginning
3. Insert node - at end
4. Insert node - at N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 0