Deletion in Doubly Linked List from Beginning

Deletion in Doubly Linked List is an important operation. In this tutorial we will understand how can we delete a node in doubly linked list.  Questions based on doubly linked list are asked in University examination.

Doubly Linked List Deletion can be performed  in following cases.

(1) Deletion from beginning

(2) Deletion from End

(3) Deleting a node after a given node.

Here in this tutorial we have explained the deletion in doubly linked list from beginning.

Deletion in doubly Linked List from Beginning

To delete the first node of doubly linked list or to perform deletion at the beginning of doubly linked list we use the following steps.

Step 1 – At first we check whether linked list is empty ? Check Head==NULL

Step 2 – If Linked List is empty then display the message linked list is empty and deletion is not possible.

Step 3 – If linked list is not empty then do the following to delete a node from beginning of doubly linked list.

        3.1 – Declare a node pointer variable temp and initialize temp with head.                        Here head refer to the first node of doubly linked list.

        3.2 – Change the reference of head pointer by head = head->next

        3.3 – Set head -> prev = Null

Step 4 – Delete temp

Deletion of first node from doubly linked list is also shown in above figure.

Pseudo code or Function to delete a new node at the beginning of doubly Linked List is given here

void DeleteBeginning( )

{

    struct node * newNode ;

    if(head == NULL)

    {

        printf(“Error, List is Empty!\n”);

    }

    else

    {

        struct node *temp;

        temp=head;

        head=head->next;

        head->prev=NULL;

        free(temp);

        printf(“First Node Deleted SUCCESSFULLY AT THE BEGINNING OF THE LIST\n”);

    }

}

Explanation

• Since here we want to delete the first node of doubly linked list so at first we declare a temp pointer of node type and initialize it with first node it means node to be deleted.
• When the first node will be delete after that second node will become the first node of linked list so reference of head pointer will be change .
• When Second node will become the first node after deletion of currently first node the we have to set null in previous filed of that node which is currently second.

C Program for Deletion in Doubly Linked List from the Beginning

#include <stdio.h>

#include <stdlib.h>

/* Define structure of Node */

struct node

{

int data;

struct node * prev;

struct node * next;

};

struct node *firstnode;

struct node *lastnode;

struct node *head;

void createList(int n);

void displayList();

void DeleteBeginning();

int main()

{

int numnode;

int value;

printf(“enter the number of nodes in doubly linkedlist”);

scanf(“%d”,&numnode);

createList(numnode);

displayList() ;

DeleteBeginning();

displayList();

return 0;

}

// Function to create doubly linked list

void createList(int n)

{

int i, data;

struct node *newNode;

// Initially we Create and linked list only with one node (firstnode)

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

printf(“Enter data of 1 node: “);

scanf(“%d”, &data);

firstnode->data = data;

firstnode->prev = NULL;

firstnode->next = NULL;

lastnode = firstnode;

head=firstnode;

// To  Create remaining n-1 nodes of linked list we are using loop.

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;

// add newly creted node in the end of linkedlist

newNode->prev = lastnode; // Link new node with the previous node

newNode->next = NULL;

lastnode->next = newNode; // Link previous node with the new node

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

if(head == NULL)

{

printf(“List is empty.\n”);

}

else

{

temp = head;

printf(“Linked LIST Is:\n”);

while(temp != NULL)

{

printf(“%d\t”, temp->data);

n++;

/* Move the current pointer to next node */

temp = temp->next;

}

}

}

 void DeleteBeginning( )

{

    struct node * newNode ;

    if(head == NULL)

    {

        printf(“Error, List is Empty!\n”);

    }

    else

    {

        struct node *temp;

        temp=head;

        head=head->next;

        head->prev=NULL;

        free(temp);

        printf(“First Node Deleted SUCCESSFULLY AT THE BEGINNING OF THE LIST\n”);

    }

}

OUTPUT

enter the number of nodes in doubly linkedlist 4

Enter data of 1 node: 21

Enter data of 2 node: 22

Enter data of 3 node: 23

Enter data of 4 node: 24

DOUBLY LINKED LIST CREATED SUCCESSFULLY

Linked LIST Is:

21        22        23        24        First Node Deleted SUCCESSFULLY AT THE BEGINNING OF THE LIST

Linked LIST Is:

22        23        24

Conclusion and Summary

• In this tutorial we have discussed the deletion in doubly linked list from beginning.
• We have discussed the algorithm to perform doubly linked list deletion from beginning.
• C Program to delete the first node of doubly linked list is also explained.

Next Tutorial – Deletion in Doubly Linked List at the End