// Fig. 22.3: List.java
// Class ListNode and class List definitions
package com.deitel.jhtp3.ch22;

class ListNode {
   // package access data so class List can access it directly
   Object data;    
   ListNode next;

   // Constructor: Create a ListNode that refers to Object o.
   ListNode( Object o ) { this( o, null ); }

   // Constructor: Create a ListNode that refers to Object o and
   // to the next ListNode in the List.
   ListNode( Object o, ListNode nextNode )
   {
      data = o;         // this node refers to Object o
      next = nextNode;  // set next to refer to next
   }

   // Return a reference to the Object in this node
   Object getObject() { return data; }

   // Return the next node
   ListNode getNext() { return next; }
}

// Class List definition
public class List {
   private ListNode firstNode;
   private ListNode lastNode;
   private String name;  // String like "list" used in printing

   // Constructor: Construct an empty List with s as the name
   public List( String s )
   {
      name = s;
      firstNode = lastNode = null;
   }

   // Constructor: Construct an empty List with
   // "list" as the name
   public List() { this( "list" ); }                             

   // Insert an Object at the front of the List
   // If List is empty, firstNode and lastNode will refer to
   // the same object. Otherwise, firstNode refers to new node.
   public synchronized void insertAtFront( Object insertItem )
   {
      if ( isEmpty() )
         firstNode = lastNode = new ListNode( insertItem );
      else 
         firstNode = new ListNode( insertItem, firstNode );
   }

   // Insert an Object at the end of the List
   // If List is empty, firstNode and lastNode will refer to
   // the same Object. Otherwise, lastNode's next instance
   // variable refers to new node.
   public synchronized void insertAtBack( Object insertItem )
   {
      if ( isEmpty() )
         firstNode = lastNode = new ListNode( insertItem );
      else 
         lastNode = lastNode.next = new ListNode( insertItem );
   }

   // Remove the first node from the List.
   public synchronized Object removeFromFront()
          throws EmptyListException
   {
      Object removeItem = null;

      if ( isEmpty() )
         throw new EmptyListException( name );

      removeItem = firstNode.data;  // retrieve the data

      // reset the firstNode and lastNode references
      if ( firstNode.equals( lastNode ) )
         firstNode = lastNode = null;
      else
         firstNode = firstNode.next;

      return removeItem;  
   }

   // Remove the last node from the List.
   public synchronized Object removeFromBack()
          throws EmptyListException
   {
      Object removeItem = null;

      if ( isEmpty() )
         throw new EmptyListException( name );

      removeItem = lastNode.data;  // retrieve the data

      // reset the firstNode and lastNode references
      if ( firstNode.equals( lastNode ) )
         firstNode = lastNode = null;
      else {
         ListNode current = firstNode;

         while ( current.next != lastNode )  // not last node
            current = current.next;      // move to next node
   
         lastNode = current;
         current.next = null;
      }

      return removeItem;
   }

   // Return true if the List is empty
   public synchronized boolean isEmpty()
      { return firstNode == null; }

   // Output the List contents
   public synchronized void print()
   {
      if ( isEmpty() ) {
         System.out.println( "Empty " + name );
         return;
      }

      System.out.print( "The " + name + " is: " );

      ListNode current = firstNode;

      while ( current != null ) {
         System.out.print( current.data.toString() + " " );
         current = current.next;
      }

      System.out.println( "\n" );
   }
}

/**************************************************************************
 * (C) Copyright 1999 by Deitel & Associates, Inc. and Prentice Hall.     *
 * All Rights Reserved.                                                   *
 *                                                                        *
 * DISCLAIMER: The authors and publisher of this book have used their     *
 * best efforts in preparing the book. These efforts include the          *
 * development, research, and testing of the theories and programs        *
 * to determine their effectiveness. The authors and publisher make       *
 * no warranty of any kind, expressed or implied, with regard to these    *
 * programs or to the documentation contained in these books. The authors *
 * and publisher shall not be liable in any event for incidental or       *
 * consequential damages in connection with, or arising out of, the       *
 * furnishing, performance, or use of these programs.                     *
 *************************************************************************/