Question

Language: Java

Topic: Doubly Linked Lists

Write a method that removes and returns the last copy of the given data from the list. Do not return the same data that was passed in. Return the data that was stored in the list. Must be O(1) if data is in the tail and O(n) for all other cases.
  
* @param data the data to be removed from the list
* @return the data that was removed
* @throws java.lang.IllegalArgumentException if data is null
* @throws java.util.NoSuchElementException if data is not found

Header:

public T removeLastOccurrence(T data) {
  

}

NODE CLASS & VARIABLES:

public class DoublyLinkedList<T> {

// Do not add new instance variables or modify existing ones.
private DoublyLinkedListNode<T> head;
private DoublyLinkedListNode<T> tail;
private int size;

Answer 1

public T removeLastOccurrence(T data) {
        
        DoublyLinkedListNode<T> tmp = tail;
        
        // If the data is on last node O(1)
        if(tmp.data.equals(data)) {
                tail = tail.prev;
                tail.next = null;
                return tmp.data;
                
        // We need to traverse the list to find the node O(N)
        } else {
                tmp = tmp.prev;
                
                // Keep checking list, untill list is over or we get data node
                while(tmp != null && !tmp.data.equals(data)) {
                        tmp = tmp.prev;
                }       
                
                // if we found a node with desired data
                if(tmp != null) {
                        tmp.next.prev = tmp.prev;
                        tmp.prev.next = tmp.next;
                        return tmp.data;
                }
                
                // If no node found to delete
                return null;
        }
}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.