removeLast / addFirst methods in Deque JAVA

Question

I need help to solve my removeLast and addFirst methods.

I cannot think of a way to add an element to the head of my queue and to point the head to that element, since I only have access to head.element / head.next.

Likewise I cannot find a way to reference the tail of the queue after removing the last object, because I am restricted to queue.element and queue.next

Any help would be appreciated!

public class DequeImpl implements Deque{

    private Node head;
    private Node tail;
    private int size;

    public DequeImpl(){
        head=null;
        tail=null;
        size=0;
    }

    //This is a toString
    public String toString(){
        String toSend = "";
        Node baladeur = head;
        while(baladeur != null) {
            toSend += " " + baladeur.element;
            baladeur = baladeur.next;
        }
        return toSend;
    }

    // renvoie true if empty
    public boolean isEmpty(){
        return size==0;
    }


    public int size(){
        return this.size;
    }

   //To complete ///////
    public void addFirst(Object element){
        Node element2 = new Node(element, head);
        if(isEmpty()){
            head=tail=element2;
        }
        else{

        }
        size++;
    }

    public void addLast(Object element){
        Node element3 = new Node(element, null);
        if(isEmpty()){
            head=tail=element3;
        }
        else{
            tail.next=element3;
            tail = tail.suivant;
        }
        size++;
    }

    public Object removeFirst() throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        Object element4 = head.element;
        if(size==1){
            head=tail=null;
        }
        else{
            head=head.next;
        }
            size--;
        return element4;
    }

   //To complete ///////

    public Object removeLast()throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        Object element5 = tail.element;
        if(size==1){
            head=tail=null;
        }
        else{
            tail.next=null;
        }
        return null;
    }

    public Object first()throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        return head.element;

    }

    public Object last()throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        return tail.element;
    }


    private class Node{
        private Object element;
        private Node next;

        private Node(Object element, Node next){
            this.element = element;
            this.next = next;
        }

    }
} 

Answer 1

Reassigning head is easy:

Node newHead = ... whatever you do here
newHead.next = head;
head = newHead;

I feel your pain with tail, though. If you don't have a back-pointer from tail, all you can do is iterate through the whole list, and:

if (tail.equals(thisNode.next)) {
  thisNode.next = null;
  tail = thisNode;
  break;
}

A little more context to show that you can iterate through the whole list:

Node thisNode = head;
while (thisNode != null) {
  if (tail.equals(thisNode.next)) {
    thisNode.next = null;
    tail = thisNode;
    break;
  }
  thisNode = thisNode.next;
}