C program to delete a node from doubly linked list

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

Doubly linked list deletion of a node

Required knowledge

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

Algorithm to delete node from beginning of a doubly linked list

Algorithm to delete node from beginning
%% Input: head {Pointer to first node of the linked list}
Begin:
    If (head == NULL) then
        write ('Can't delete from an empty list')
    End if
    Else then
        toDeletehead;
        headhead.next;
        head.prevNULL;
        unalloc (toDelete)
        write ('Successfully deleted first node from the list')
    End if
End

Algorithm to delete node from end of a doubly linked list

Algorithm to delete node from end
%% Input: last {Pointer to last node of the linked list}
Begin:
    If (last == NULL) then
        write ('Can't delete from an empty list')
    End if
    Else then
        toDeletelast;
        lastlast.prev;
        last.nextNULL;
        unalloc (toDelete)
        write ('Successfully deleted last node from the list')

    End if
End

Algorithm to delete node from any position of a doubly linked list

Algorithm to delete node from any position
%% Input : head {Pointer to the first node of the list}
         last {Pointer to the last node of the list}
         N {Position to be deleted from list}
Begin:
    currenthead;
    For i ← 1 to N and current != NULL do
        currentcurrent.next;
    End for
    If (N == 1) then
        deleteFromBeginning()
    End if
    Else if (current == last) then 
        deleteFromEnd()
    End if
    Else if (current != NULL) then
        current.prev.nextcurrent.next
        If (current.next != NULL) then
            current.next.prevcurrent.prev;
        End if
        unalloc (current)
        write ('Node deleted successfully from ', N, ' position')
    End if
    Else then
        write ('Invalid position')
    End if
End

Steps to delete node from any position of a doubly linked list

Let us suppose that we want to delete node from 2nd position.

  1. Traverse to Nth node of the linked list, lets say a pointer current points to Nth node in our case 2 node.
    Deletion of a node in doubly linked list step 1

  2. Link the node behind current node with the node ahead of current node, which means now the N-1th node will point to N+1th node of the list. Which can be implemented as current->prev->next = current->next.
    Deletion of a node from doubly linked list step 2

  3. If N+1th node is not NULL then link the N+1th node with N-1th node i.e. now the previous address field of N+1th node will point to N-1th node. Which can be implemented as current->next->prev = current->prev.
    Deletion of a node from doubly linked list step 3

  4. Finally delete the current node from memory and you are done.
    Deletion of a node from doubly linked list step 4

     

    Deletion of a node from doubly linked list step 5

Program to delete a node from doubly linked list

/**
 * C program to delete a node from 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 deleteFromBeginning();
void deleteFromEnd();
void deleteFromN(int position);


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

    head = NULL;
    last = NULL;

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

        scanf("%d", &choice);

        switch(choice)
        {
            case 1:
                printf("Enter the total number of nodes in list: ");
                scanf("%d", &n);
                createList(n);
                break;
            case 2:
                deleteFromBeginning();
                break;
            case 3:
                deleteFromEnd();
                break;
            case 4:
                printf("Enter the node position which you want to delete: ");
                scanf("%d", &n);
                deleteFromN(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;

        /*
         * 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 node
        }

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


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

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


/**
 * Delete or remove the first node of the doubly linked list
 */
void deleteFromBeginning()
{
    struct node * toDelete;

    if(head == NULL)
    {
        printf("Unable to delete. List is empty.\n");
    }
    else
    {
        toDelete = head;

        head = head->next; // Move head pointer to 2 node
        
        if (head != NULL)
            head->prev = NULL; // Remove the link to previous node

        free(toDelete); // Delete the first node from memory
        printf("SUCCESSFULLY DELETED NODE FROM BEGINNING OF THE LIST.\n");
    }
}


/**
 * Delete or remove the last node of the doubly linked list
 */
void deleteFromEnd()
{
    struct node * toDelete;

    if(last == NULL)
    {
        printf("Unable to delete. List is empty.\n");
    }
    else
    {
        toDelete = last;

        last = last->prev; // Move last pointer to 2nd last node
        
        if (last != NULL)
            last->next = NULL; // Remove link to of 2nd last node with last node

        free(toDelete);       // Delete the last node
        printf("SUCCESSFULLY DELETED NODE FROM END OF THE LIST.\n");
    }
}


/**
 * Delete node from any position in the doubly linked list
 */
void deleteFromN(int position)
{
    struct node *current;
    int i;

    current = head;
    for(i=1; i<position && current!=NULL; i++)
    {
        current = current->next;
    }

    if(position == 1)
    {
        deleteFromBeginning();
    }
    else if(current == last)
    {
        deleteFromEnd();
    }
    else if(current != NULL)
    {
        current->prev->next = current->next;
        current->next->prev = current->prev;

        free(current); // Delete the n node

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

============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from 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
DATA of 4 node = 40
DATA of 5 node = 50

============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 2
SUCCESSFULLY DELETED NODE FROM BEGINNING OF THE LIST.

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

============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice :
3
SUCCESSFULLY DELETED NODE FROM END OF THE LIST.

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

============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Delete node - from beginning
3. Delete node - from end
4. Delete node - from N
5. Display list
0. Exit
--------------------------------------------
Enter your choice : 4
Enter the node position which you want to delete: 2
SUCCESSFULLY DELETED NODE FROM 2 POSITION.

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

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