Deletion In Doubly Linked List

The doubly linked list is an important data structure that allows for efficient insertion and deletion of elements from both ends. Unlike singly linked lists, doubly linked lists have two pointers: one pointing to the previous node and another to the next node. This article will explore how to perform deletion operations in a doubly linked list, complete with code examples and explanations.

A doubly linked list is a type of linked list in which each node contains three components:

• Data: The actual value stored in the node.
• Prev Pointer: A pointer to the previous node in the sequence.
• Next Pointer: A pointer to the next node in the sequence.

Deletion in a doubly linked list can occur in the following scenarios:

1. Deletion at the Beginning
2. Deletion at the End
3. Deletion at a Specific Position

Let’s dive into each type with step-by-step explanations and C code examples.

1. Deletion at the Beginning in doubly linked list

There are two main methods used to delete the node at the beginning of the doubly linked list

Method 01: Delete the first node By using some extra pointers

5 steps procedure will explain how to delete a node at the beginning of the doubly linked list

Step 01: Consider a doubly Linked List

• Explanation: In this example (i.e. 10 <-> 20 <-> 30 <-> 40 <-> NULL) 

Step 02: We take pointer “ptr” as Head pointer which help us to delete the first node

• Explanation: In the given code, the head pointer points to the first node of the list (node with value 10). We’ll refer to this node as the “first node”. The ptr variable can be used to navigate through the list, and in this case, it will be used to help delete the first node.

Step 03: Traverse “Head” to one position Right, so that first node to be deleted. We use the following code

Head =Head -> Next;

• Explanation: To delete the first node (node with value 10), we need to make the head pointer point to the next node (node with value 20), effectively moving “one position right” in the list.

Step 04: Delete Node by Using the following code,

free (ptr);

• Explanation: Now that the head pointer has been updated to point to the second node (node with value 20), we can delete the old first node (node with value 10).

Step 05: Must Update, so that the first node becomes inaccessible.

Head -> prev = Null

and optionally update pointer “ptr”

ptr = Null;

• Explanation: After deleting the node, we need to ensure that the new head node (node with value 20) correctly points to the previous node as NULL. This step ensures that the doubly linked list structure remains valid. Optionally, we can also set ptr to NULL to indicate that it no longer points to any node:

The following diagram will fully explain, how to delete the node at the beginning of doubly linked list

Code Example in C to delete first node using some extra pointers

#include <stdio.h> #include <stdlib.h>// Define the structure of a node for a doubly linked list struct Node { int data; struct Node* next; struct Node* prev; };// Function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (!newNode) { printf(“Memory allocation failed\n”); exit(1); } newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }// Function to delete a node at the beginning of the doubly linked list struct Node* deleteAtBeginning(struct Node* head) { // Step 1: Check if the list is empty if (head == NULL) { printf(“The list is already empty.\n”); return NULL; }// Step 2: Save the current head struct Node* temp = head;// Step 3: Update the head pointer head = head->next; // Step 4: Adjust the previous pointer of the new head if (head != NULL) { head->prev = NULL; } // Step 5: Free the old head printf(“Deleting node with value %d\n”, temp->data); free(temp); return head; } // Function to display the doubly linked list void displayList(struct Node* head) { struct Node* ptr = head; while (ptr != NULL) { printf(“%d <-> “, ptr->data); ptr = ptr->next; } printf(“NULL\n”); } // Main function int main() { // Manually creating the doubly linked list struct Node* head = createNode(10); head->next = createNode(20); head->next->prev = head; head->next->next = createNode(30); head->next->next->prev = head->next; head->next->next->next = createNode(40); head->next->next->next->prev = head->next->next; printf(“Initial doubly linked list: “); displayList(head); // Delete the node at the beginning printf(“\nDeleting the first node…\n”); head = deleteAtBeginning(head); printf(“Doubly linked list after deletion: “); displayList(head); return 0; }

Output:

Initial doubly linked list: 10 <-> 20 <-> 30 <-> 40 <-> NULL

Deleting the first node...
Deleting node with value 10
Doubly linked list after deletion: 20 <-> 30 <-> 40 <-> NULL

Method 02: Delete node at beginning without using any extra pointer

In this second method, move the head pointer one step forward, then use the “prev” pointer of the second node to access the first node for deletion in the doubly linked list, as illustrated in the diagram below.

Code Example in C to delete first node without using any extra pointer

#include <stdio.h> #include <stdlib.h>// Define the structure of a node for a doubly linked list struct Node { int data; struct Node* next; struct Node* prev; };// Function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (!newNode) { printf(“Memory allocation failed\n”); exit(1); } newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }// Function to delete a node at the beginning of the doubly linked list struct Node* deleteAtBeginning(struct Node* head) { // Step 1: Check if the list is empty if (head == NULL) { printf(“The list is already empty.\n”); return NULL; }// Step 2: Print the data of the node to be deleted printf(“Deleting node with value %d\n”, head->data);// Step 3: Update the head pointer head = head->next; // Step 4: If the new head exists, adjust its prev pointer if (head != NULL) { head->prev = NULL; } // Step 5: Free the old head node (without ternary operator) if (head != NULL) { free(head->prev); // Free the old head } else { free(head); // If the list becomes empty, free the old head } return head; } // Function to display the doubly linked list void displayList(struct Node* head) { while (head != NULL) { printf(“%d <-> “, head->data); head = head->next; } printf(“NULL\n”); } // Main function int main() { // Manually creating the doubly linked list struct Node* head = createNode(10); head->next = createNode(20); head->next->prev = head; head->next->next = createNode(30); head->next->next->prev = head->next; head->next->next->next = createNode(40); head->next->next->next->prev = head->next->next; printf(“Initial doubly linked list: “); displayList(head); // Delete the node at the beginning printf(“\nDeleting the first node…\n”); head = deleteAtBeginning(head); printf(“Doubly linked list after deletion: “); displayList(head); return 0; }

Output: 

Initial doubly linked list: 10 <-> 20 <-> 30 <-> 40 <-> NULL

Deleting the first node...
Deleting node with value 10
Doubly linked list after deletion: 20 <-> 30 <-> 40 <-> NULL

2. Deletion at the End

Method 01: Delete the last node by using some extra pointers

Step 01: Given Linked List

• Explanation: The code starts with a doubly linked list consisting of nodes, each containing a data value and two pointers: next (to the next node) and prev (to the previous node). The list is initialized with nodes having values 10, 20, 30, and 40.

Step 02: We take pointer “ptr” as Head pointer

• Explanation: In this step, a pointer ptr is initialized to point to the head of the list, which is the first node (with value 10). This pointer will help traverse the list.

Step 03: Traverse “ptr” to last Node by Using

while(ptr -> next != Null){ ptr = ptr -> next }

• Explanation: The loop while(ptr->next != NULL) moves the ptr pointer along the list, node by node, until it reaches the last node (where ptr->next is NULL).

Step 04: Use one more pointer “ptr2” which pointing to second last position by using

while(ptr -> next != Null){ ptr = ptr -> next } ptr2 = ptr -> prev

• Explanation: A second pointer ptr2 is introduced to point to the second last node. It is assigned the value ptr->prev after ptr reaches the last node, thus making ptr2 point to the second last node.

Step 05: Unlink the last node from the list by using

ptr2 – next = Null

• Explanation: To remove the last node from the list, the next pointer of ptr2 (the second last node) is set to NULL, effectively disconnecting the last node from the list.

Step 06: Optionally but good practice to do following

free (ptr); ptr = Null;

• Explanation: It’s good practice to free the memory allocated for the last node (free(ptr)) and set the ptr pointer to NULL to avoid any dangling pointers. This helps prevent memory leaks and ensures proper memory management.

The following diagram will fully explain, how to delete the last node at the of doubly linked list

Code Example in C to delete node at the end using some extra pointer

#include <stdio.h> #include <stdlib.h>// Define the structure of a node for a doubly linked list struct Node { int data; // Data part of the node struct Node* next; // Pointer to the next node struct Node* prev; // Pointer to the previous node };// Function to create a new node with the given data struct Node* createNode(int data) { // Allocate memory for the new node struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (!newNode) { // Handle memory allocation failure printf(“Memory allocation failed\n”); exit(1); } // Initialize the new node newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }// Function to delete the last node in a doubly linked list struct Node* deleteAtEnd(struct Node* head) { // Check if the list is empty if (head == NULL) { printf(“The list is already empty.\n”); return NULL; }// Initialize ptr2 to traverse the list to find the second last node struct Node* ptr2 = head;// Traverse until ptr2 points to the second last node while (ptr2->next != NULL && ptr2->next->next != NULL) { ptr2 = ptr2->next; // Move to the next node } // Handle the case where the list has only one node if (ptr2->next == NULL) { // Single-node case printf(“Deleting the only node with value %d\n”, ptr2->data); free(ptr2); // Free the single node return NULL; // The list is now empty } // At this point, ptr2 is the second last node struct Node* ptr = ptr2->next; // Pointer to the last node printf(“Deleting node with value %d\n”, ptr->data); // Update the second last node’s next pointer to NULL ptr2->next = NULL; // Free the memory of the last node free(ptr); return head; } // Function to display the contents of the doubly linked list void displayList(struct Node* head) { struct Node* ptr = head; // Pointer to traverse the list while (ptr != NULL) { printf(“%d <-> “, ptr->data); // Print the current node’s data ptr = ptr->next; // Move to the next node } printf(“NULL\n”); // Indicate the end of the list } // Main function int main() { // Create a sample doubly linked list struct Node* head = createNode(10); head->next = createNode(20); head->next->prev = head; head->next->next = createNode(30); head->next->next->prev = head->next; head->next->next->next = createNode(40); head->next->next->next->prev = head->next->next; // Display the initial list printf(“Initial doubly linked list: “); displayList(head); // Delete the last node from the list printf(“\nDeleting the last node…\n”); head = deleteAtEnd(head); // Display the list after deletion printf(“Doubly linked list after deletion: “); displayList(head); return 0; }

Output:

Initial doubly linked list: 10 <-> 20 <-> 30 <-> 40 <-> NULL

Deleting the last node...
Deleting node with value 40
Doubly linked list after deletion: 10 <-> 20 <-> 30 <-> NULL

Method 02: Delete a node without using any Extra pointer at end

it’s your assignment.

3. Deletion at a Specific Position in Doubly linked list

Step 01: Given Linked List

• Explanation: The code initializes a doubly linked list with nodes containing values 10, 20, 30, and 40. Each node contains pointers to the next and previous nodes.

Step 02: We take pointer “ptr” as Head pointer

• Explanation: The pointer ptr is initialized to point to the head of the list, which is the first node (value 10). This pointer will be used to traverse the list.

Step 03: Traverse “ptr” to node which need to delete, by using following Code

while(position > 1){ ptr = ptr -> next position — }

Position is a variable which hold some value i.e. 03

• Explanation: The loop while (position > 1) moves the ptr pointer to the node at the given position (in this case, position 3). The position variable holds the target position to delete (e.g., 3). For each iteration, the ptr pointer moves to the next node, and position is decremented.

Step 04: Use one more pointer “ptr2” which pointing to second last position by using following Code

while(position > 1){ ptr = ptr -> next position — }ptr2 = ptr -> prev

• Explanation: Once ptr reaches the target node, ptr2 is assigned the previous node (ptr->prev). This makes ptr2 point to the node just before the node to be deleted.

Step 05: Unlink the node (want to delete) from list by using

while(position > 1){ ptr = ptr -> next position — }ptr2 = ptr -> prev ptr2 – next = ptr->next

• Explanation: The ptr2->next = ptr->next operation removes the target node from the list. It links the previous node (ptr2) directly to the node after the target (ptr->next), effectively skipping the node to be deleted.

Step 06: Unlink the node (want to delete) from list by using

ptr -> next -> prev = ptr2

• Explanation: In addition, the code ensures the previous pointer of the next node is updated with ptr->next->prev = ptr2, ensuring the next node correctly points back to the second last node.

Step 07: (Optional but good practice) free the memory of deleted node by using

free(ptr);

• Explanation: The memory allocated to the node to be deleted is freed using free(ptr). This ensures that the memory is released and avoids memory leaks.

Step 08: (Optional but good practice) free the memory of deleted node by using

ptr = Null;

• Explanation: It is good practice to set ptr = NULL after deleting the node. This avoids potential use of a dangling pointer, ensuring safe memory management.

The following diagram will fully explain, how to delete the node at specific point of doubly linked list

Code Example in C to delete node at specific position using some extra pointer

#include <stdio.h> #include <stdlib.h>// Define the structure of a node for a doubly linked list struct Node { int data; // Data part of the node struct Node* next; // Pointer to the next node struct Node* prev; // Pointer to the previous node };// Function to create a new node with the given data struct Node* createNode(int data) { // Allocate memory for the new node struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (!newNode) { // Handle memory allocation failure printf(“Memory allocation failed\n”); exit(1); } // Initialize the new node newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }// Function to delete a node at a specific position in a doubly linked list struct Node* deleteAtPosition(struct Node* head, int position) { // Check if the list is empty if (head == NULL) { printf(“The list is already empty.\n”); return NULL; }// Initialize ptr and ptr2 to traverse the list struct Node* ptr = head; struct Node* ptr2 = NULL;// If the position is 1, delete the head node if (position == 1) { head = ptr->next; // Update head to the next node if (head != NULL) { head->prev = NULL; // Update the previous pointer of the new head } printf(“Deleting node with value %d\n”, ptr->data); free(ptr); // Free the memory of the old head node return head; } // Traverse to the node just before the node to be deleted for (int i = 1; ptr != NULL && i < position; i++) { ptr2 = ptr; // Move ptr2 to the current node ptr = ptr->next; // Move ptr to the next node } // If the position is greater than the number of nodes, print an error if (ptr == NULL) { printf(“Position out of range.\n”); return head; } // If the node to be deleted is not the last node if (ptr->next != NULL) { ptr->next->prev = ptr2; // Update the next node’s prev pointer } // If the node to be deleted is not the first node if (ptr2 != NULL) { ptr2->next = ptr->next; // Update the previous node’s next pointer } printf(“Deleting node with value %d\n”, ptr->data); free(ptr); // Free the memory of the deleted node return head; } // Function to display the contents of the doubly linked list void displayList(struct Node* head) { struct Node* ptr = head; // Pointer to traverse the list while (ptr != NULL) { printf(“%d <-> “, ptr->data); // Print the current node’s data ptr = ptr->next; // Move to the next node } printf(“NULL\n”); // Indicate the end of the list } // Main function int main() { // Create a sample doubly linked list struct Node* head = createNode(10); head->next = createNode(20); head->next->prev = head; head->next->next = createNode(30); head->next->next->prev = head->next; head->next->next->next = createNode(40); head->next->next->next->prev = head->next->next; // Display the initial list printf(“Initial doubly linked list: “); displayList(head); // Specify the position to delete int position = 3; // Example: Deleting the node at position 2 (value 30) // Delete the node at the specified position printf(“\nDeleting the node at position %d…\n”, position); head = deleteAtPosition(head, position); // Display the list after deletion printf(“Doubly linked list after deletion: “); displayList(head); return 0; }

Output:

Initial doubly linked list: 10 <-> 20 <-> 30 <-> 40 <-> NULL

Deleting the node at position 3...
Deleting node with value 30
Doubly linked list after deletion: 10 <-> 20 <-> 40 <-> NULL

Method 02: Delete a node without using any Extra pointer at specific point

it’s your assignment.

Deletion in a doubly linked list is straightforward due to the bidirectional pointers. Whether you need to remove a node from the beginning, end, or a specific position, the process involves updating the relevant pointers and freeing memory.