java - Queue using linked lists - how should this work? -

i'm struggling head around data structure. in course use following code implement 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 should work, when call constructor method have sentinel[0|null] , let tail=sentinel, tail[0|null]. calling .enqueue(x), following:

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

if call .dequeue(), sentinel.next null.

i asked lecturer , got following reply, doesn't make clearer me: "when call constructor via queue q = new queue(); create dummy item sentinel, value 0 , next pointer null. @ same time let tail point sentinel. adding elements queue not problem."

i don't see let let tail point sentinel :/

your intuition is, in fact, correct. class not work properly.

when enqueue stuff, works - adds things @ tail, , works.

the trouble starts when dequeue items. when that, sentinel.next become null - have removed queue - tail still pointing last item enqueued. have tail that's disconnected sentinel.

you can enqueue stuff then, , appended after old tail, no longer reachable sentinel. if try dequeue further, you'll nullpointerexception.

to demonstrate this, added following method queue class (and added item class since didn't put in post):

@override public string tostring() {     stringbuilder sb = new stringbuilder("queue: ");     ( item item = sentinel.next; item != null; item = item.next ) {         sb.append('[').append(item.value).append(']');     }     return sb.tostring(); } 

now, 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         @ testing.queue.dequeue(simpletest.java:48)         @ testing.simpletest.main(simpletest.java:27) 

what should have gotten was:

queue: [5][10] queue: [10] queue:  queue: [15][20] queue: [20] 

to achieve this, have correct tail when reach 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, 1 should protect dequeue() method against being called when queue empty. throwing nullpointerexception not nice, more sensible exception nicer. , in fact helps create more elegant dequeue(), instead of correcting tail, change sentinel - throw out old sentinel , use item dequeued our new sentinel:

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

if didn't null-check, sentinel become null when attempt dequeue, , we'd never able dequeue again. null-checking, make sure have item dequeue, , becomes sentinel. if happens last item in queue, have tail , sentinel pointing same item, did in beginning, know can continue adding items , reachable through sentinel.

note method checking whether queue empty before attempting dequeue come in handy.