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");
        }
    }
}

Output

============================================
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

Happy coding 😉

About Pankaj

Pankaj Prakash is the founder, editor and blogger at Codeforwin. He loves to learn new techs and write programming articles especially for beginners. He works at Vasudhaika Software Sols as a Software Design Engineer and manages Codeforwin. In short Pankaj is Web developer, Blogger, Learner, Tech and Music lover.

Follow on: Facebook | Twitter | Google | or

Comments and discussion
Have a doubt, write here. I will help my best.
Before commenting you must escape your source code before commenting. Paste your source code inside
<pre><code> ----Your Source Code---- </code></pre>