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

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.

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.