Question

Language: Java

Topic: Deques

Using the following variables/class:

public class LinkedDeque<T> {

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

Q1: write a method called "public T removeFirst()" that does the following:

* Removes and returns the first element of the deque.

* Must be in O(1)

* @return the data formerly located at the front of the deque

* @throws java.util.NoSuchElementException if the deque is empty

Q2: write a method called "public T removeLast()" that does the following:

* Removes and returns the last element of the deque.

* Must be O(1).

* @return the data formerly located at the back of the deque

* @throws java.util.NoSuchElementException if the deque is empty

Answer 1

public T removeFirst()
{
   if(head==null)//if dequeue is empty
   throw new Exception("NoSuchElementException");
  
   //use getter and setter methods if next,prev declared as private
   head = head.next;//moving head to next node
   head.prev = null;
}
public T removeLast()
{
   if(tail==null)//if dequeue is empty
   throw new Exception("NoSuchElementException");

   tail=tail.prev;//moving tail to previous node
   tail.next=null;
}