//*************************************************
//
// An example of linked lists, initially for lists of 
// integers. We define the class and appropriate methods
//
//**************************************************

public class List
{
  private boolean eol;    // (1)
  private int data;       // (2)
  private List next;      // (3)

  /* A list is an element with data, followed by a list
     or is empty. 
     Because of the peculiarities of OOP we cannot actually have null as
     the empty list as we would then have to have instance variables and
     methods associated with null. So a work around is to have a list element
     marked as empty at the end of every list. 
     (1) eol is true if this is an end of list marker, otherwise it is false
     (2) the data in the list element (an integer)
     (3) next is the next list element (and may be the end of list element)
     */

  public List()
  {
    eol = true;
    data = -999;
    next = null;
  }
  /* The default constructor, producing an empty list element
     Generally, when we initially create a list it will be empty,
     and therefore composed of this single element marking the end of list (eol)
     I have assumed that when it is an end of list the data is irrelevant.
     */

  public List(int e)
  {
    eol = false;                     // (1)
    data = e;                        // (2) 
    next = new List();               // (3)
  }
  /* Create a single element list with e as data
     (1) it is NOT the end of list
     (2) data is set to be e
     (3) the next element is an end of list element
     */

  public List(int e, List tail)
  {
    eol = false;                    // (1)
    data = e;                       // (2)
    next = tail;                    // (3)
  }    
  /* Create me a new list element with e as the data and tail as the rest
     of the list, where tail is a List. We would use this when adding a new
     element to the list.
     (1) it is NOT an end of list 
     (2) e is the data
     (3) tail is the net of the list
     */

  public List add(int e)
  {
    return new List(e,this);
  }
  /* add e onto the list. Similar to function cons in scheme and lisp
   */

  public boolean isEmpty()
  {
    return eol;    
  }
  /* Is the list empty?
   */

  public int head()
  {
    return data;
  }
  /* Return the data in the list element, 
     and it's an integer.
     */

  public List tail()
  {
    return next;
  }
  /* Get me the tail of the list, that is
     deliver the next of the list.
     */

  public void print()
  {
    if (isEmpty())
      System.out.println("");
    else 
      {
	System.out.print(head() + " ");
	tail().print();
      }
  }

  public int length()
  {
    if (isEmpty())
      return 0;
    else return 1 + tail().length();
  }

  
  public List append(List l2)
  {
    if (isEmpty())
      return l2;
    else return new List(head(),tail().append(l2));
  }


  public List insert(int e)
  {
    if (isEmpty())
      return new List(e);
    else if (e < head())      
      return new List(e,this);
    else return new List(head(),tail().insert(e));
  }

  public List delete(int e)
  {
    if (isEmpty())
      return this;
    else if (e == head())
      return tail();
    else return new List(head(),tail().delete(e));
  }
        
  
  private List rev(List temp)
  {
    if (isEmpty())
      return temp;
    else return tail().rev(new List(head(),temp));
  }

  public List reverse()
  {
    return rev(new List());
  }


  /*
    Lab Work Below Lab Work Below Lab Work Below Lab Work Below Lab Work Below
    Lab Work Below Lab Work Below Lab Work Below Lab Work Below Lab Work Below
    
    Implement the methods nth and sum

    */


  public int nth(int n)
  {
    return 0;
  }
  /*
    Deliver as a result the data in the nth item 
    in the list. That is, L.nth(0) delivers data of
    1st item, L.nth(1) delivers the data in the 2nd item,
    and generaly L.nth(i) delivers data of i-1th item.
    Note: deliver -999 if list is empty or request 
    to get ith element of list that has less than
    i-1 items.
    */

  public int sum()
  {
    return 0;
  }
  /*
    Given a list of integer L, L.sum() delivers
    the sum of the integers in the list. Note, if the
    list isEmpty deliver zero as a result;
    */
}