/** An instance has two fields: element and next. They are public.
   An instance is a linked list: the first element is in field element
   and the rest of the list is given by field next.

   NOTE: THE CONSTRUCTORS AND METHODS EQUAL AND APPEND ARE CORRECT.
   ALL OTHER METHODS HAVE RETURN STATEMENTS ONLY IN ORDER FOR YOU
   TO BE ABLE TO COMPILE. YOU MUST WRITE THESE METHODS.
   REMOVE THIS NOTE BEFORE SUBMITTING YOUR PROJECT.
   */
class List {
    public Object element;
    public List next;
    
    /** Constructor: an instance with one node, which contains the value null*/
    public List() {
        element= null; next= null; 
    }
    
    /** Constructor: an instance with element field d and next field n */
    public List(Object e, List n) {
        element= e;
        next= n;
    }
        
    /** #1 Prepend x to l and return (the name of) the new List */
    public static List prepend(Object x, List l) {
        return null;
    }
    
    /** #2 = the element of the first node of list l.
        Precondition: l is not null  
      */
    public static Object first(List l) {
        return null;
    }
    
    /** #3 = (the name of) List l with its first element removed (i.e. (the name of)
          the second ListNode in this list (null if l has only one element)
          Preconditon: l is not null.  
       */
    public static List rest(List l) {
        return null;
    }
    
    /** #4 = "list l is empty --i.e. null"  */
    public static boolean isEmpty(List l) {
        return true;
    }
    
    /** = "o1 = o2" (they could both be null, in which case they are equal) */
    public static boolean equal(Object o1, Object o2) {
        if (o1==null  &&  o2==null)
            return true;
        if (o1==null  || o2==null)
            return false;
        return o1.equals(o2);
    }
    
        /** = l1 with l2 appended to it */
    public static List append(List l1, List l2) {
        if (isEmpty(l1))
            return l2;
        return prepend(first(l1), append(rest(l1),l2));
    }
    
}