Nodes, Queues, De-queues

Question

I'm doing this small project of creating a queue and a de-queue in the same class along with using my own Node class and an interface.

The problem i'm facing is I've done all methods but can't get the method removeLast to work because i'm unable to let rear link to the node before it, after getting removed. Please help me with your suggestions? Thank you.

My node class.

public class Node<T> {

  T info;
  Node<T> next;

  public Node(T element) {
    info = element;
    next = null;
  }

  public void setInfo(T element) {
    info = element;
  }

  public T getInfo() {
    return info;
  }

  public void setNext(Node<T> next) {
    this.next = next;
  }

  public Node<T> getNext() {
    return next;
  }

}

My interface class

public interface DequeInterface<T> {

  void addFront(T element);

  void addLast(T element);

  T removeFront();

  T removeLast();

  boolean isEmpty();

  int getSize();
}

My deque class

import java.util.NoSuchElementException;

public class Deqeue<T> implements DequeInterface {

  public Node<T> front;
  public Node<T> rear;
  int size;

  public Deqeue() {
    front = null;
    rear = null;
    size = 0;
  }

  @Override
  public T removeFront() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    T element = front.getInfo();
    front = front.getNext();
    size--;
    return element;
  }

  @Override
  public T removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    T element = rear.getInfo();
    size--;
    return element;
  }

  @Override
  public int getSize() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return rear == null;
  }

  @Override
  public void addFront(Object element) {
    Node<T> newNode = front;

    if (newNode == null) {
      rear = front;
    }
      front = new Node(element);
      front.setNext(newNode);
      size++;
  }

  @Override
  public void addLast(Object element) {
    Node<T> newNode = rear;

    if (newNode == null) {
      front = rear;
    }
      rear = new Node(element);
      newNode.setNext(rear);
      size++;

    }
  }

Answer 1

The problem is that your list is singly-linked. Unfortunately, removing the last node of a singly-linked list requires traversing the entire list. Some alternatives:

• you can make your list doubly-linked
• you can use a random-access array instead of a linked list
• you could use Okasaki's "purely functional datastructures" deque