Remove a node from the end of the doubly linked list
The problem involves removing a node from the end of a doubly linked list. In a doubly linked list, each node contains a data element and two pointers, one pointing to the next node and another pointing to the previous node. The task is to remove a specific node that matches a given value from the end of the list.

Problem Statement
Given a doubly linked list and a target value, the goal is to locate the last occurrence of the target value in the list and remove that node from the list.
Example
Consider the following doubly linked list:
1 <-> 2 <-> 9 <-> 4 <-> 5 <-> 2 <-> 7 <-> 9
If we want to remove the last occurrence of the value 2 from the end of the list, the resulting list should be:
1 <-> 2 <-> 9 <-> 4 <-> 5 <-> 7 <-> 9
Idea to Solve
To solve this problem, you need to traverse the doubly linked list from the end, searching for the last occurrence of the target value. Once found, you will manipulate the pointers of the previous and next nodes to bypass the node you want to remove.
Pseudocode
function deletionFromEnd(key):
if head is null:
return
auxiliary = null
temp = tail
while temp is not null and auxiliary is null:
if temp.data equals key:
auxiliary = temp
move temp to the previous node
if auxiliary is not null:
if auxiliary.prev is not null:
auxiliary.prev.next = auxiliary.next
if auxiliary.next is not null:
auxiliary.next.prev = auxiliary.prev
if head equals auxiliary:
head = head.next
if tail equals auxiliary:
tail = tail.prev
auxiliary = null
else:
print "Node not exist " + key
Algorithm Explanation
- Start by initializing
auxiliary
to null andtemp
to thetail
of the list. - Traverse the doubly linked list from the end using the
temp
pointer:- If the data value of the current node (
temp.data
) matches the target value (key
), setauxiliary
to the current node. - Move
temp
to the previous node.
- If the data value of the current node (
- After traversing, check if
auxiliary
is not null:- If it is not null, the target node exists in the list.
- Update the pointers of the previous and next nodes to bypass the
auxiliary
node. - If
auxiliary
is thehead
ortail
, updatehead
ortail
accordingly. - Set
auxiliary
to null. - If
auxiliary
is null, print a message indicating that the node does not exist.
Program List
-
1) Delete a node from the end of doubly linked list in java
2) Delete a node from the end of doubly linked list in c++
3) Delete a node from the end of doubly linked list in c
4) Delete a node from the end of doubly linked list in golang
5) Delete a node from the end of doubly linked list in c#
6) Delete a node from the end of doubly linked list in vb.net
7) Delete a node from the end of doubly linked list in php
8) Delete a node from the end of doubly linked list in node js
9) Delete a node from the end of doubly linked list in typescript
10) Delete a node from the end of doubly linked list in python
11) Delete a node from the end of doubly linked list in ruby
12) Delete a node from the end of doubly linked list in scala
13) Delete a node from the end of doubly linked list in swift
14) Delete a node from the end of doubly linked list in kotlin
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the doubly linked list. In the worst case, you might need to traverse the entire list to find and remove the last occurrence of the target 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