C program to insert node in a Doubly linked list

Required knowledge

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.data ← data;
        newNode.prev ← NULL;
        newNode.next ← head;

        head.prev ← newNode;
        head ← newNode;
        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.data ← data;
        newNode.next ← NULL;
        newNode.prev ← last;
        
        last.next ← newNode;
        last ← newNode;
        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:
    temp ← head
    For i←1 to N-1 do
        If (temp == NULL) then
            break
        End if
        temp ← temp.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.data ← data;
        newNode.next ← temp.next
        newNode.prev ← temp
        If (temp.next != NULL) then
            temp.next.prev ← newNode;
        End if
        temp.next ← newNode;
        write('Node added successfully')
    End if
End

Steps to insert a new node in Doubly linked list

Traverse to N-1 node in the list. Where N is the position to insert. Say temp now points to N-1^th node.

Create a newNode that is to be inserted and assign some data to its data field.

Connect the next address field of newNode with the node pointed by next address field of temp node.

Connect the previous address field of newNode with the temp node.

Check if temp.next is not NULL then, connect the previous address field of node pointed by temp.next to newNode.

Connect the next address field of temp node to newNode i.e. temp.next will now point to newNode.

Final list

Program

/**
 * 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;



/*
 * Functions 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;

    /*
     * Runs 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);

        /*
         * Chooses 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)
    {
        /*
         * Creates and links 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;

        /*
         * Creates and links 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; //Links new node with the previous node
            newNode->next = NULL;

            last->next = newNode; //Links previous node with the new node
            last = newNode; //Makes new node as last/previous node
        }

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



/**
 * Displays the 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++;

            /* Moves 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; //Points to next node which is currently head
        newNode->prev = NULL; //Previous node of first node is NULL

        /* Links previous address field of head with newnode */
        head->prev = newNode;
        /* Makes 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; //Connects new node with n+1th node
            newNode->prev = temp; //Connects new node with n-1th node

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

            printf("NODE INSERTED SUCCESSFULLY AT %d POSITION\n", position);
        }
        else
        {
            printf("Error, Invalid position\n");
        }
    }
}