Bhagirath Bhardwaj Bhagirath Bhardwaj - 20 days ago 4x
Java Question

How does Enqueue and Dequeue work under Linked Implementation of Queue

How does Enqueue handles special case where chain starts out empty and the Dequeue process when the chain starts with one node.


The OpenJDK implementation uses two tricks:

  1. The queue contains a blind element which is always present, even in an empty queue. The blind element is always the first element in the queue, but not visible from outside the class.

  2. The queue is actually a ring. We know that we reached the last element when == blind.

The following image illustrates such a queue of length 0 (left) and a qeue of length 1 (right).

queue with tricks

The benefits of using these tricks are:

  • no null pointers
  • no if-else for adding/enqueuing elements

For remove/deque we still have to check whether the queue is empty.

Adding =;
newElement.prev = head; = newElement; = newElement;


if ( == head) {
    // ERROR, queue is empty
} else { = removedElement.prev; =;

Note that is is absolutely possible to implement a queue without these tricks, using just one additional if-else statement. The following image represents a naive implemented queue of length 0 (left) and length 1 (right).

naive queue


if (head == null) {
    // queue is empty
    head = newElement;
} else {
    // add to head


if (head == null) {
    // ERROR, queue is empty
} else {
    // remove from tail