//
// COMP102
// Example 9: Basic Linked List
//            Creation and Maintenance
//
// Paul E. Dunne 8/11/99
//
public class LinkedList
  {
  //******************************************************
  // Embed the ListCell Class from earlier.              *
  //******************************************************
  private class ListCell
  {
  private Object Datum;
  private ListCell Link;
  //
  private ListCell(Object head, ListCell next_cell)
    {
    Datum = head; Link=next_cell; 
    }
  }
  //******************************************************
  // Linked List Fields                                  *
  //******************************************************
  private ListCell Head;         
  private ListCell Tail;         
  private int CellCount;         // The number of list cells in this instance.
  //******************************************************
  // Linked List Constructor                             *
  //******************************************************
  public LinkedList()
    {
    Head = null;
    Tail = null;      
    CellCount=0; // Initiates the empty list.
    }
  //******************************************************
  // Linked List Instance Methods                        *
  //******************************************************
  //
  //  Test if this instance is the Empty list.
  //
  public boolean IsEmpty()
    {
    return (CellCount==0);       // `Safer' than testing for null reference.
    };
  //
  //************************************************************
  //  Add a new ListCell as the first cell in this Linked List *
  //  i.e. The `new' Linked List is [Datum]::[Previous List].  *
  //************************************************************
  //
  public void AddHead ( Object Datum )
    {
    if (IsEmpty())               // If it's currently empty;
      {
      Head = new ListCell(Datum,Head);   // Create the new Head.
      Tail = null;                       // The link is still `null'
      CellCount=1;                       // and this list now contains 1 cell.
      }
    else                                 // If it's not empty
      {
      Head = new ListCell(Datum,Head);   // Add the new List head Datum,
      Tail = Head.Link;                  // Reset the `Tail' of the list.
      CellCount++;                       // and this list now has 1 extra cell.
      };
    }
  //
  //************************************************************************
  //  Remove the ListCell at the start of this Linked List                 *
  //  i.e. if the current list is [Head]::[Tail], the `new' one is [Tail]. *
  //************************************************************************
  //
  public void RemoveHead()
    {
    if (CellCount<=1)                    // There is an argument for raising
      {                                  // an exception if CellCount=0
                                         // however, we adopt the convention
                                         // that RemoveHead() applied to
                                         // the empty list leaves the empty list.
      Head = null; 
      CellCount=0;
      }
    else
      {
      Head = Tail;                      // Tail is never the null reference here.
      CellCount--;                      // and this list has one fewer cell.
      if (CellCount==1)
        Tail=null;                      // If there's only a single cell then its Link field
                                        // must point to the empty list (i.e. null reference)
      else
        Tail = Head.Link;               // Otherwise we can update Tail without any problem.
      };
    }
  //
  //**********************************************************************
  //  Obtain the Object in the Datum field of the ListCell at            *
  //  the start of this Linked List.                                     *
  //  This method will not change the current instantiation of this List.*
  //**********************************************************************
  //
  public Object GetHead()
    {
    if (!(CellCount==0))                // If there's anything to return
      return Head.Datum;                // then return it.
    else
      return null;                      // otherwise return a null reference.
    }
  //
  //**********************************************************************
  //  Obtain the (reference) to the Linked List for the Link field of the*
  //  ListCell at the start of this Linked List                          *
  //  This method will not change the current instantiation of this List.*
  //**********************************************************************
  //
  public LinkedList GetTail()
    {
    LinkedList temporary= new LinkedList();
    temporary.Head=Head; temporary.Tail=Tail;
    temporary.CellCount = CellCount;
    temporary.RemoveHead();
    return temporary;
    };
  //
  //**************************************************************
  //  Convert this Linked List into a String in which each       *
  // Datum of the component ListCells is separated by a newline. *
  //**************************************************************
  //
  public String toString()
    {
    String res = new String();
    LinkedList temporary = new LinkedList();
    temporary.Head = Head; 
    temporary.Tail = Tail; 
    temporary.CellCount=CellCount;
    while (!temporary.IsEmpty())
      {
      res = res+(temporary.GetHead()).toString()+"\n";
      temporary = temporary.GetTail();
      };
    return res;
    }     
  }