Last Updated on July 27, 2023 by Mayank Dham
In this article, we will explore the process of deleting a node in a doubly linked list. We will delve into the fundamentals of doubly linked lists, understanding the structure of nodes and the connections that link them in both forward and backward directions. By providing step-by-step explanations and practical examples, readers will gain a comprehensive understanding of how to implement deletion in doubly linked list.
How does a Deletion in Doubly Linked List happen?
Here, is the procedure of deletion in doubly linked list .you will be understanding the statement with the example:
If the given doubly linked list is head ↔ 4 ↔ 5 ↔ 7 ↔ 6 ↔ 2 ↔ 1 ↔ 9 and the node to be deleted is head→next→next.
- According to the problem statement, we will have to delete the node head→next→next from the doubly linked list.
- In the above given linked list, the head→next→next is the node with value 7. So we will have to delete this node.
- So after a node deletion in doubly linked list, our doubly linked list will be head ↔ 4 ↔ 5 ↔ 6 ↔ 2 ↔ 1 ↔ 9.
While deletion in doubly linked list a node temp , we should take care about the links present between the nodes. the node temp which we want to delete, the immediate previous node to temp and the immediate next node of the temp by changing the next of the previous node of temp as the next of temp and the previous of the next node of temp as the previous of temp.
- temp→next→prev = temp→prev
- temp→prev→next = temp→next
- delete(temp)
In the above example, the node we intended to delete was somewhere in the middle of the linked list. But if we wish to delete a node that is either the head or the tail of the doubly linked list, we will delete it a little differently.
Approach for Deletion in Doubly Linked List.
There are 3 approaches for deletion in doubly linked list:
Case1: If the node to be deleted is the head node.
Case2: If the node to be deleted is somewhere in the middle of the linked list.
Case3: If the node to be deleted is the tail of the linked list.
Algorithm to Delete a Node in Doubly Linked List
Here is the algorithm to delete a node in doubly linked list. we need to perform the following steps:
- If the list is empty, then there is nothing to delete, return.
- If the node to be deleted is the head node, then update the head node to point to the next node.
- If the node to be deleted is the tail node, then update the tail node to point to the previous node.
- If the node to be deleted is not the head or tail node, then update the previous node’s next pointer to point to the next node, and update the next node’s previous pointer to point to the previous node.
- Free the memory allocated to the node to be deleted.
Dry Run for Deletion in Doubly Linked List
Now we will see the dry run for deletion in doubly linked list.
Below is the step by step by step dry run for deletion in doubly linked list.
Code Implementation for Deletion in Doubly Linked List
Below is the code implementation for deletion in doubly linked list in C++ and Java.
#includeusing namespace std; class DLLNode { public: int data; DLLNode* next; DLLNode* prev; }; void deleteNodefromList(DLLNode** head, DLLNode* temp) { if (*head == NULL || temp == NULL) return; if (*head == temp) *head = temp->next; if (temp->next != NULL) temp->next->prev = temp->prev; if (temp->prev != NULL) temp->prev->next = temp->next; free(temp); return; } void push(DLLNode** head, int new_data) { DLLNode* new_node = new DLLNode(); new_node->data = new_data; new_node->prev = NULL; new_node->next = (*head); if ((*head) != NULL) (*head)->prev = new_node; (*head) = new_node; } void printList(DLLNode* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } int main() { DLLNode* head = NULL; push(&head, 3); push(&head, 8); push(&head, 10); push(&head, 7); push(&head, 2); push(&head, 6); push(&head, 1); push(&head, 5); deleteNodefromList(&head, head->next); printList(head); return 0; }
public class Prepbytes {
public static class DLL {
Node head;
class Node {
int data;
Node prev;
Node next;
Node(int d) {
data = d;
}
}
public void push(int new_data) {
Node new_Node = new Node(new_data);
new_Node.next = head;
new_Node.prev = null;
if (head != null)
head.prev = new_Node;
head = new_Node;
}
public void printlist(Node node) {
Node last = null;
while (node.next != null) {
System.out.print(node.data + " ");
last = node;
node = node.next;
}
System.out.println(node.data);
}
void deleteNode(Node temp) {
if (head == null || temp == null) {
return;
}
if (head == temp) {
head = head.next;
}
if (temp.next != null) {
temp.next.prev = temp.prev;
}
if (temp.prev != null) {
temp.prev.next = temp.next;
}
return;
}
}
public static void main(String[] args) {
DLL dll = new DLL();
dll.push(3);
dll.push(8);
dll.push(10);
dll.push(7);
dll.push(2);
dll.push(6);
dll.push(1);
dll.push(5);
dll.deleteNode(dll.head.next);
dll.printlist(dll.head);
}
}
Output
5 6 2 7 10 8 3Time Complexity: O(1), as we do not need to do the traversal of the deletion in doubly linked list.
Conclusion
In conclusion, deletion in doubly linked list requires updating the pointers of adjacent nodes to avoid the node and releasing the allocated memory. The algorithm must handle cases like deleting head/tail nodes, empty lists, and edge cases. It is crucial to ensure that the algorithm works correctly in all possible scenarios to prevent unexpected errors in the program.
FAQs
1. Why is a doubly linked list called a two way list?
A doubly linked list has a pointer which points to the next node and the previous node as well. Which makes the linked list traverse in both directions, that’s why it is called a two way list.
2. What are the operations which can be performed on doubly linked list?
The operations performed on doubly linked list are:
- Insertion of a node at the beginning.
- Insertion of node in the middle.
- Insertion of node at the end.
- Deleting a node at the beginning.
- Deleting a node in the middle.
- Deleting a node at the end.
3. How do you delete the node at a specific position in doubly linked list?
The node deletion in doubly linked list:
- We have to find the previous node which has to be deleted.
- The next of the previous node has to be changed.
- The memory of the node which has to be deleted has to be freed.
4. In doubly linked list deletion do we have to correct only the next pointer?
No, we also have to correct the prev pointer along with next pointer in doubly linked list deletion.
5. What is the space complexity of deletion in doubly linked list?
The space complexity of deletion in doubly linked list will be o(1).
6.What is the purpose of a node deletion in doubly linked list?
A node deletion in doubly linked list allows for the removal of data from the list and the reorganization of the remaining nodes.