Deletion in doubly linked list | Operations on doubly linked list

20 min read

Deletion in a doubly linked list can happen at various places in the list. A few cases are:

  • At the beginning of the doubly linked list.
  • At the end of the doubly linked list.
  • At a given position in the doubly linked list.

 

Deletion at the beginning of the doubly linked list

deletion-beginning-doubly-linked-lists

  • Copy the head node in some temporary node.
  • Make the second node as the head node.
  • The prev pointer of the head node is referenced to NULL.
  • Delete the temporary node.

 

C program for deletion of a node at the beginning of a doubly linked list

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

//structure of Node with prev and next pointers
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;
void createList(int n);
void displayList();
void delete_beginning();

int main()
{
int n;
head = NULL;
last = NULL;
printf("\nEnter the total number of nodes in list : "); // Input the number of nodes
scanf("%d", &n);
createList(n);
printf("\n\nTHE DOUBLY LINKED LIST IS :\n\n");
displayList();
delete_beginning();
printf("\n\nAFTER DELETION, THE DOUBLY LINKED LIST IS :\n\n");
displayList();
return 0;
}

void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node 1 : ");
scanf("%d", &data);
head->data = data;
head->prev = NULL; // HEAD nodes's prev is set to NULL
head->next = NULL; // HEAD nodes's next is set to NULL
last = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node %d : ", 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
}
}
}
void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("\nList is empty.\n");
}
else
{
temp = head;
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
n++;
/* Move the current pointer to next node */
temp = temp->next;
}}}

/* Function to delete the node at the beginning of the list */
void delete_beginning()
{
struct node * temp;
temp = head;
head = head -> next; // Shift head node
head -> prev == NULL; // The prev pointer of the head node is NULL
free(temp); // Delete the first node
}



OUTPUT

delete-beginning-dll

 

Deletion at the end of the doubly linked list

doubly-linked-list-deletion-end

  • Copy the last node to a temporary node.
  • Shift the last node to the second last position.
  • Make the last node's next pointer as NULL.
  • Delete the temporary node.

 

C program for deletion of a node at the end of a doubly linked list

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

//structure of Node with prev and next pointers
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;
void createList(int n);
void displayList();
void delete_end();

int main()
{
int n;
head = NULL;
last = NULL;
printf("\nEnter the total number of nodes in list : "); // Input the number of nodes
scanf("%d", &n);
createList(n);
printf("\n\nTHE DOUBLY LINKED LIST IS :\n\n");
displayList();
delete_end();
printf("\n\nAFTER DELETION, THE DOUBLY LINKED LIST IS :\n\n");
displayList();
return 0;
}

void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node 1 : ");
scanf("%d", &data);
head->data = data;
head->prev = NULL; // HEAD nodes's prev is set to NULL
head->next = NULL; // HEAD nodes's next is set to NULL
last = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node %d : ", 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
}
}
}
void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("\nList is empty.\n");
}
else
{
temp = head;
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
n++;
/* Move the current pointer to next node */
temp = temp->next;
}}}

/* Function to delete the node at the end of the list */
void delete_end()
{
struct node * temp;
if(last == NULL)
{
printf("Unable to delete. List is empty.\n");
}
else
{
temp = last;
last = last->prev; // Move last pointer to 2nd last node
if (last != NULL)
last->next = NULL; // The next pointer of the last node is NULL
free(temp); // Delete the last node
}}

 

OUTPUT

delete-end-dll

 

Deletion at the given position in the doubly linked list

doubly-linked-list-deletion-given-position

  • Suppose you want to delete the second node from the list.
  • Start traversing the linked list from the head until the position = 2 of the node to be deleted.
  • Let the node at the position 2 of the list be temp.
  • Assign the next pointer of temp to temp's previous node's next pointer.
  • Assign the temp's prev pointer to temp's next node's prev pointer.
  • Delete the temp node.

 

C program to delete a node at any given position in the doubly linked list

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

//structure of Node with prev and next pointers
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;
void createList(int n);
void displayList();
void delete_given_position(int pos);

int main()
{
int n, pos;
head = NULL;
last = NULL;
printf("\nEnter the total number of nodes in list : "); // Input the number of nodes
scanf("%d", &n);
createList(n);
printf("\n\nTHE DOUBLY LINKED LIST IS :\n\n");
displayList();
printf("\n\nEnter the position : ");
scanf("%d",&pos);
delete_given_position(pos);
printf("\n\nAFTER DELETION, THE DOUBLY LINKED LIST IS :\n\n");
displayList();
return 0;
}
void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node 1 : ");
scanf("%d", &data);
head->data = data;
head->prev = NULL; // HEAD nodes's prev is set to NULL
head->next = NULL; // HEAD nodes's next is set to NULL
last = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("\nEnter data of node %d : ", 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
}}}
void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("\nList is empty.\n");
}
else
{
temp = head;
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
n++;
/* Move the current pointer to next node */
temp = temp->next;
}}}

/* Function to delete a node at the given position in the list */
void delete_given_position(int position)
{
struct node *temp;
int i;
temp = head;
for(i=0; i<position && current!=NULL; i++)
{
temp = temp->next;
}
if(temp != NULL)
{
temp->prev->next = temp->next; // Assign the next pointer of node to be deleted to its previous node's prev pointer
temp->next->prev = temp->prev; // Assign the prev pointer of the node to be deleted to its next node's next pointer
free(temp); // Delete the temp node
}
else
{
printf("Invalid position!\n");
}}



OUT PUT

delete-given-position

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error