Undefined use of next in a queue?

[berky]

I was looking over an example queue and was confused about the way it works.


it creates a node called next, but never really does anything with it. Later in the queue it refers to it the way
you would expect next to work. But since we never did anything with next, it makes no sense that it would act
the way its used. Its just a random node. Why is it possible to use it in a distinctive way?

 // Queue.java
// An integer queue ADT

class Queue{

   private class Node{
      // Fields
      int data;
      Node next;
      // Constructor
      Node(int data) { this.data = data; next = null; }
      // toString:  Overides Object's toString method.
      public String toString() { return String.valueOf(data); }
   }

   // Fields
   private Node front;
   private Node back;
   private int length;

   // Constructor
   Queue() { front = back = null; length = 0; }


   // Access Functions //////////////////////////////////////////////////////////////////

   // getFront(): returns front element in this queue
   // Pre: !this.isEmpty()
   int getFront(){
      if( this.isEmpty() ){
         throw new RuntimeException("Queue Error: getFront() called on empty Queue");
      }
      return front.data;
   }

   // getLength(): returns length of this queue
   int getLength() { return length; }

   // isEmpty(): returns true if this is an empty queue, false otherwise
   boolean isEmpty() { return length==0; }


   // Manipulation Procedures ///////////////////////////////////////////////////////////

   // Enqueue(): appends data to back of this queue
   void Enqueue(int data){
      Node node = new Node(data);
      if( this.isEmpty() ) { front = back = node; }
      else { back.next = node; back = node; }
      length++;
   }

   // Dequeue(): deletes element from front of this queue
   // Pre: !this.isEmpty()
   void Dequeue(){
      if(this.isEmpty()){
         throw new RuntimeException("Queue Error: Dequeue() called on empty Queue");
      }
      if(this.length>1) {front = front.next;}
      else {front = back = null;}
      length--;
   }


   // Other Functions ///////////////////////////////////////////////////////////////////

   // toString():  overides Object's toString() method.
   public String toString(){
      String str = "";
      for(Node N=front; N!=null; N=N.next){
         str += N.toString() + " ";
      }
      return str;
   }

   // equals(): returns true if this Queue is identical to  Q, false otherwise.
   boolean equals(Queue Q){
      boolean flag  = true;
      Node N = this.front;
      Node M = Q.front;

      if( this.length==Q.length ){
         while( flag && N!=null){
            flag = (N.data==M.data);
            N = N.next;
            M = M.next;
         }
         return flag;
      }else{
         return false;
      }
   }

   // copy(): returns a new Queue identical to this one.
   Queue copy(){
      Queue Q = new Queue();
      Node N = this.front;

      while( N!=null ){
         Q.Enqueue(N.data);
         N = N.next;
      }
      return Q;
   }

}

[Nepomuk]

OK, let's have a look at every place that next is used:

Node next;
//...
Node(int data) { this.data = data; next = null; }

A so far empty node called next is defined. Also, in the constructor it is initialized as null. Pretty simple so far.

// Enqueue(): appends data to back of this queue
void Enqueue(int data){
   Node node = new Node(data);
   if( this.isEmpty() ) { front = back = node; }
   else { back.next = node; back = node; }
   length++;
}

OK, here it get's interesting. If the current node isn't empty, next is defined as the new Node node so now it exists as a real (so far empty) object.

// Dequeue(): deletes element from front of this queue
// Pre: !this.isEmpty()
void Dequeue(){
   if(this.isEmpty()){
      throw new RuntimeException("Queue Error: Dequeue() called on empty Queue");
   }
   if(this.length>1) {front = front.next;}
   else {front = back = null;}
   length--;
}

If the queue is longer than 1 item, the node front is defined as front.next, so effectively front (the first element of the queue) is removed from the queue.

OK, now it's also used in toString(), equals() and copy(), but as they just read it those aren't important here.

So, to summarize: in every node we have a reference to the first, last and next element, which we define while building up the queue. Does that answer your question?

Greetings,
Nepomuk