Double Queue Implementation in Java

A queue is a collection of items which are kept in order. Adding an item to the queue adds it to the end of the queue, and removing an item removes the item at the front of the queue. Queues are used in many real life applications.

A double queue is a queue where items can not only be added to the end and removed from the front, but added to the front and removed from the end as well.

Here is an implementation of a double queue in Java.

MyDoubleQueue.java

public class MyDoubleQueue {

	// Reference to the first node in the list.
	private Node _first = null;

	// Reference to the last node in the list.
	private Node _last = null;

	/**
	 * Insert a Node at the front of the list.
	 *
	 * @param n
	 */
	public void insertFront(Node n)
	{
		// Make sure we have a valid node.
		if(n == null){
			return;
		}

		// If the list is already empty, set the node to be first.
		if(isEmpty()){
			_first = n;
			_last = n;
		} else {
			// The list is not empty, so we must set a proper connection.
			n.setNext(_first);
			_first.setPrev(n);
			_first = n;
		}
	}

	/**
	 * Insert a node at the end of the list.
	 *
	 * @param n
	 */
	public void insertRear(Node n)
	{
		// Make sure we have a valid node.
		if(n == null){
			return;
		}

		// If the list is empty, add at first spot.
		if(isEmpty()){
			_first = n;
			_last = n;
		} else {
			// Add the node at the end.
			_last.setNext(n);
			n.setPrev(_last);
			_last = n;
		}
	}

	/**
	 * Remove the node from the front of the list.
	 *
	 * @return
	 */
	public Node removeFront()
	{
		// If the list is empty, nothing should be removed.
		if(!isEmpty()){

			// If the length of the list is 1.
			if(getSize() == 1){
				_first = null;
				_last = null;
			} else {
				// We have 2 nodes or more.
				_first = _first.getNext();
				_first.setPrev(null);
			}

		}

		// Return the new first node.
		return _first;
	}

	/**
	 * Remove a node from the end of the list.
	 *
	 * @return
	 */
	public Node removeRear()
	{
		// If the list is empty, we have nothing to remove.
		if(!isEmpty()){
			// If the list has one element, we are removing both the front and last element.
			if(getSize() == 1){
				_first = null;
				_last = null;
			} else {
				// We have at least two elements.
				_last.getPrev().setNext(null);
				_last = _last.getPrev();
			}
		}

		// Return the new last node.
		return _last;
	}

	/**
	 * Check if the list is empty.
	 */
	public boolean isEmpty()
	{
		// By definition, if _first is null, we have an empty list.
		return _first == null;
	}

	/**
	 * Get the size of the list.
	 *
	 * @return
	 */
	public int getSize()
	{
		// If the list is empty, the size is 0.
		if(isEmpty()){
			return 0;
		} else if(_first.getNext() == null) {
			return 1; // We have a list of length one.
		} else {
			// Define the size.
			int size = 1;
			// We have at least two nodes. Go until the end of the list, counting each node.
			Node temp = _first;
			while(temp.getNext() != null){
				// Increase the size.
				size++;
				// Update the reference.
				temp = temp.getNext();
			}
			// Return the size.
			return size;
		}
	}

}

Node.java

This class is an abstraction of an actual class that you would want to use in a queue.

public class Node {

	private Node _prev = null; // Reference to the previous node.
	private Node _next = null; // Reference to the next node.

	/**
	 * Constructor.
	 */
	Node()
	{

	}

	public Node getPrev()
	{
		return _prev;
	}

	public void setPrev(Node n)
	{
		_prev = n;
	}

	public Node getNext()
	{
		return _next;
	}

	public void setNext(Node n)
	{
		_next = n;
	}

}