Delete a node in a Doubly Linked List
The problem at hand is about deleting a node with a given value from a Doubly Linked List. A Doubly Linked List is a linear data structure where each element (node) contains a value and two pointers, one pointing to the previous node and the other pointing to the next node. This bidirectional linkage allows efficient traversal in both directions.


Problem Statement
The task is to design a program that deletes a node with a specified value from a Doubly Linked List. If the value is found in the list, the corresponding node should be removed, and the pointers of the neighboring nodes should be updated accordingly.
Example
Consider the following scenario:
Original Doubly Linked List: 6 → 9 → 1 → 4 → 3 → 6 → 2
Delete node with value 4.
Expected Result: 6 → 9 → 1 → 3 → 6 → 2
Idea to Solve
To solve this problem, we need to traverse the Doubly Linked List while searching for the node with the given value. Once the node is found, we need to adjust the pointers of the neighboring nodes to bypass the node to be deleted.
Pseudocode
deleteNode(DoublyLinkedList *list, int value):
if list.head is NULL:
print "Empty linked list"
return
if list.head.data == value:
temp = list.head
list.head = list.head.next
if list.head is not NULL:
list.head.prev = NULL
else:
list.tail = NULL
free(temp)
else if list.tail.data == value:
temp = list.tail
list.tail = list.tail.prev
if list.tail is not NULL:
list.tail.next = NULL
else:
list.head = NULL
free(temp)
else:
temp = list.head
while temp is not NULL and temp.data != value:
temp = temp.next
if temp is NULL:
print "Deleted node not found"
else:
temp.prev.next = temp.next
if temp.next is not NULL:
temp.next.prev = temp.prev
free(temp)
Algorithm Explanation
- If the linked list is empty, print "Empty linked list" and return.
- If the value to be deleted is found in the head node:
- Update the head pointer to skip the current head node.
- If the list is not empty, update the prev pointer of the new head.
- If the list becomes empty, update the tail pointer as well.
- Free the memory of the deleted node.
- If the value to be deleted is found in the tail node:
- Update the tail pointer to skip the current tail node.
- If the list is not empty, update the next pointer of the new tail.
- If the list becomes empty, update the head pointer as well.
- Free the memory of the deleted node.
- If the value to be deleted is found in an intermediate node:
- Traverse the list until the node with the target value is found.
- Update the next pointer of the previous node to skip the node to be deleted.
- If the node to be deleted is not the last node, update the prev pointer of the next node.
- Free the memory of the deleted node.
Code Solution
-
1) Delete a node from doubly linked list in c
2) Delete a node from doubly linked list in c++
3) Delete a node from doubly linked list in java
4) Delete a node from doubly linked list in golang
5) Delete a node from doubly linked list in c#
6) Delete a node from doubly linked list in vb.net
7) Delete a node from doubly linked list in php
8) Delete a node from doubly linked list in node js
9) Delete a node from doubly linked list in typescript
10) Delete a node from doubly linked list in python
11) Delete a node from doubly linked list in ruby
12) Delete a node from doubly linked list in scala
13) Delete a node from doubly linked list in swift
14) Delete a node from doubly linked list in kotlin
Time Complexity
- For insertion, each insertion operation takes O(1) time as it simply involves updating the tail pointer and connecting the new node.
- For deletion, the worst-case time complexity is O(n), where n is the number of nodes in the linked list. This is because in the worst case, we might have to traverse the entire linked list to find the node with the given value.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment