Queue using linked lists - how should this work?

Question

I'm struggling to get my head around this data structure. In my course we use the following code to implement a Queue using linked lists:

class Queue
{
    private Item sentinel , tail;

    public Queue () {
        sentinel = new Item(0,null); 
        tail = sentinel;
    }

    public void enqueue(int value) {
        tail.next = new Item(value , null);
        tail = tail.next; 
    }

    public int dequeue ()
    {
        int value = sentinel.next.value;​
        sentinel.next = sentinel.next.next;
        return value; 
    } 
}

I don't see how this should work, when we call the constructor method we have sentinel[0|null] and then we let tail=sentinel, so tail[0|null]. By calling .enqueue(x), we get the following:

[0|pointer to tail],  tail[x|null]

If we now call .dequeue(), sentinel.next is null.

I asked my lecturer about this and I got the following reply, which doesn't really make it clearer for me: "When we call the constructor via Queue q = new Queue(); we will create the dummy item sentinel, whose value is zero and whose next pointer is null. At the same time we let tail point to sentinel. So clearly adding elements to the queue is not a problem."

I don't see where we let let tail point to the sentinel :/

Answer 1

Your intuition is, in fact, correct. This class does not work properly.

When you enqueue stuff, it works well - adds things at the tail, and everything works.

The trouble starts when you dequeue all the items. When you do that, sentinel.next will become null - you have removed everything from the queue - but tail will still be pointing to the last item you enqueued. So basically you have a tail that's disconnected from your sentinel.

You can enqueue stuff then, and it will be appended after the old tail, but it will no longer be reachable from sentinel. If you try to dequeue anything further, you'll get a NullPointerException.

To demonstrate this, I added the following method to your Queue class (and added the Item class since you didn't put it in your post):

@Override
public String toString() {
    StringBuilder sb = new StringBuilder("Queue: ");
    for ( Item item = sentinel.next; item != null; item = item.next ) {
        sb.append('[').append(item.value).append(']');
    }
    return sb.toString();
}

Now, with this main program:

public static void main(String[] args) {

    Queue queue = new Queue();
    queue.enqueue(5);
    queue.enqueue(10);
    System.out.println(queue);
    queue.dequeue();
    System.out.println(queue);
    queue.dequeue();
    System.out.println(queue);
    queue.enqueue(15);
    queue.enqueue(20);
    System.out.println(queue);
    queue.dequeue();
    System.out.println(queue);
}

You get:

Queue: [5][10]
Queue: [10]
Queue: 
Queue: 
Exception in thread "main" java.lang.NullPointerException
        at testing.Queue.dequeue(SimpleTest.java:48)
        at testing.SimpleTest.main(SimpleTest.java:27)

What you should have gotten was:

Queue: [5][10]
Queue: [10]
Queue: 
Queue: [15][20]
Queue: [20]

To achieve this, you have to correct the tail when you reach it when dequeuing.

public int dequeue ()
{
    int value = sentinel.next.value;
    if ( sentinel.next == tail ) {
        tail = sentinel;
    }
    sentinel.next = sentinel.next.next;
    return value; 
}

In truth, one should also protect the dequeue() method against being called when the queue is empty. Throwing a NullPointerException is not nice, a more sensible exception would be nicer. And in fact it helps create a more elegant dequeue(), where instead of correcting the tail, we simply change the sentinel - throw out the old sentinel and use the item we just dequeued as our new sentinel:

public int dequeue ()
{
    int value = sentinel.next.value;
    if ( sentinel.next == null ) {
        throw new IllegalStateException("No items to dequeue");
    }
    sentinel = sentinel.next;
    return value; 
}

If we didn't null-check, then sentinel would become null when we attempt to dequeue, and then we'd never be able to dequeue again. By null-checking, we make sure we have an item to dequeue, and it becomes the sentinel. If it also happens to be the last item in the queue, then we have tail and sentinel pointing to the same item, as they did in the beginning, so we know we can continue adding items and they will be reachable through sentinel.

Note that method for checking whether the queue was empty before attempting to dequeue would also come in handy.

Answer 2

If we now call .dequeue(), sentinel.next still points to null. This is not right. senitel only gets initialized in constructor and does not change any further.

So, After connstructor you get - (Senitel) -> null and here tail points to Senitel. You call enqueue and it becomes. (Senitel) -> (Element1) -> null. Here, tail points to Element1 and Senitel still points to (Senitel). You call dequeue and it becomes (Senitel) - > null.