CODEWITHSUNDEEP
javaqueuenodesdeque
user2272227
user2272227

Reputation: 125

Nodes, Queues, De-queues

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++;

    }
  }

Upvotes: 3

Views: 6640

Answers (5)

DeltaLima
DeltaLima

Reputation: 5944

You could have your Node have a reference to the previous Node as well. This would create a doubly linked list.

public class Node<T> {

    T info;
    Node<T> next;
    Node<T> prev;

    public Node(T element) {
        info = element;
        next = null;
        prev = 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;
    }

    public void setPrev(Node<T> prev) {
        this.prev = prev;
    }

    public Node<T> getPrev() {
        return prev;
    }
}

Then in the Deque class change your removeFront and removeLast methods to account for prev 

public T removeFront() {
    if (isEmpty()) {
       throw new NoSuchElementException();
    }
    T element = front.getInfo();
    front = front.getNext();
    front.setPrev(null); //<<<--------------------------
    size--;
    return element;
}

@Override
public T removeLast() {
    if (isEmpty()) {
       throw new NoSuchElementException();
     }
    T element = rear.getInfo();
    rear.getPrev().setNext(null) //<<<--------------
    rear=rear.getPrev(); //<<<--------------

    size--;
    return element;
 }

And of course the addFirst and addLast methods have to be updated as well

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

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

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

    if (newNode == null) {
        front = rear;
    }else{
        newNode.setNext(rear);
    } 
    size++;
}

If you would not be allowed to change the code of Node and only can change the removeLast() method then you could do it like this:

@Override
public T removeLast() {
    if (isEmpty()) {
       throw new NoSuchElementException();
     }
    T element = rear.getInfo();
    if(rear==first){
        rear=null;
        first=null;
    }else{
        Node<T> prev = first;
        while(prev.getNext()!=rear){
            prev=prev.getNext();
        }
        rear=prev;
        prev.setNext(null);
   }
    size--;
    return element;
 }

But this would be rather inefficient as it requires iterating through the whole list from the beginning.

Upvotes: 1

Devin Lynch
Devin Lynch

Reputation: 289

The easiest way to go about doing this is to implement a doubly linked list as opposed to a linked list. So your node class will need to keep track of the previous element. You will need to update your add functions to support this. Once completed, your remove last function will look like this:

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

Upvotes: 0

comingstorm
comingstorm

Reputation: 26117

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:

Upvotes: 2

digitaljoel
digitaljoel

Reputation: 26574

You can make your list doubly linked (extra management and opportunity for bugs), or you can iterate through the list every time you removeLast and set rear to the new last (much worse performance when removing from last especially on large lists.)

Upvotes: 0

JB Nizet
JB Nizet

Reputation: 691775

Each node should have a pointer to the next node and to the previous node.

Upvotes: 0

Related Questions