// List.java
// ListNode and List class definitions.
package chapter35;

// class to represent one node in a list
class ListNode
{
    // data can store any object
    Object data;
    // nextNode Stores a reference to the next ListNode object in the linked list
    ListNode nextNode;

    // constructor creates a ListNode that refers to object
    ListNode( Object object )
    {
        data = object;  
        nextNode = null;
    } // end ListNode one-argument constructor

    // constructor creates ListNode that refers to
    // Object and to next ListNode
    ListNode( Object object, ListNode node )
    {
        data = object;
        nextNode = node;
    } // end ListNode two-argument constructor

    // return reference to data in node
    Object getObject()
    {
        return data; // return Object in this node
    } // end method getObject

    // return reference to next node in list
    ListNode getNext()
    {
        return nextNode; // get next node
    } // end method getNext
} // end class ListNode

// class List definition
public class List
{
    // References to the first and last ListNodes in a List
    private ListNode firstNode;
    private ListNode lastNode;
    private String name; // string like "list" used in printing

    // constructor creates empty List with "list" as the name
    public List()
    {
        name = "list";
        // Initialize both references to null
        firstNode = lastNode = null;
    } // end List no-argument constructor

    // constructor creates an empty List with a name
    public List( String listName )
    {
        name = listName;
        // Initialize both references to null
        firstNode = lastNode = null;
    } // end List one-argument constructor

    // insert Object at front of List
    public void insertAtFront( Object insertItem )
    {
        if ( isEmpty() ) // firstNode and lastNode refer to same object
            firstNode = lastNode = new ListNode( insertItem );
        else // firstNode refers to new node
            firstNode = new ListNode( insertItem, firstNode );
    } // end method insertAtFront

    // insert Object at end of List
    public void insertAtBack( Object insertItem )
    {
        if ( isEmpty() ) // firstNode and lastNode refer to same Object
            firstNode = lastNode = new ListNode( insertItem );
        else // lastNode's nextNode refers to new node
            lastNode = lastNode.nextNode = new ListNode( insertItem );
    } // end method insertAtBack

    // remove first node from List
    //public Object removeFromFront() throws EmptyListException
    public Object removeFromFront()
    {
        Object removedItem = firstNode.data; // retrieve data being removed

        // update references firstNode and lastNode
        if ( firstNode == lastNode )
            firstNode = lastNode = null;
        else
            firstNode = firstNode.nextNode;

        return removedItem; // return removed node data
    } // end method removeFromFront

    // remove last node from List
    public Object removeFromBack()
    {
        Object removedItem = lastNode.data; // retrieve data being removed

        // update references firstNode and lastNode
        if ( firstNode == lastNode )
            firstNode = lastNode = null;
        else // locate new last node
        {
            ListNode current = firstNode;

            // loop while current node does not refer to lastNode
            while ( current.nextNode != lastNode )
                current = current.nextNode;

            lastNode = current; // current is new lastNode
            current.nextNode = null;
        } // end else

        return removedItem; // return removed node data
    } // end method removeFromBack

    // determine whether list is empty
    public boolean isEmpty()
    {
        return firstNode == null; // return true if List is empty
    } // end method isEmpty

    // output List contents
    public void print()
    {
        if ( isEmpty() )
        {
            // Display a message indicating that the list is empty
            System.out.printf( "Empty %s\n", name );
            return;
        } // end if

        System.out.printf( "The %s is: ", name );
        ListNode current = firstNode;

        // while not at end of list, output current node's data
        while ( current != null )
        {
            // Output a string representation of current.data
            System.out.printf( "%s ", current.data );
            // Move to the next node in the list
            current = current.nextNode;
        } // end while

        System.out.println( "\n" );
    } // end method print
} // end class List

