Posted on by Kalkicode

# 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):
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 tail equals auxiliary:
tail = tail.prev
auxiliary = null
else:
print "Node not exist " + key``````

## Algorithm Explanation

1. Start by initializing `auxiliary` to null and `temp` to the `tail` of the list.
2. 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`), set `auxiliary` to the current node.
• Move `temp` to the previous node.
3. 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 the `head` or `tail`, update `head` or `tail` accordingly.
• Set `auxiliary` to null.
• If `auxiliary` is null, print a message indicating that the node does not exist.

## 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.

## Comment

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.

Categories
Relative Post