<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">// 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.
public 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 e and next field n */
    public List(Object e, List n) {
        element= e;
        next= n;
    }
    
    /** = length of List l */
    public static int length(List l) {
        return l==null ? 0 : 1+length(l.next);
    }
        
    /** prepend x to l and return (the name of) the new List */
    public static List prepend(Object x, List l) {
        return new List(x,l);
    }
    
    /** = the element of the first node of list l. Precondition: l is not null  */
    public static Object first(List l) {
        return l.element;
    }
    
    /** = (the name of) List l with its first element removed (null if l
           has only one element). Precondition: l != null.  */
    public static List rest(List l) {
        return l.next;
    }
    
    /** = "list l is empty --i.e. null"  */
    public static boolean isEmpty(List l) {
        return l == null;
    }
    
    /** = "o1 = o2" (they could both be null) */
    public static boolean equals(Object o1, Object o2) {
        if (o1==null  &amp;&amp;  o2==null)
            return true;
        if (o1==null  || o2==null)
            return false;
        return o1.equals(o2);
    }
    
    /** = "p1 = p2" --i.e. p1 and p2 are lists of the same length
           and corresponding elements have the same values */
    public static boolean equals(List p1, List p2) {
        if (p1 == p2)
            return true;
        if (p1==null || p2==null)
            return false;
        return p1.element.equals(p2.element) &amp;&amp; 
               equals(p1.next,p2.next);
    }

    
    /** Print the elements of list l on a single line, with each element followed
        by a blank. Print the null list as a blank line. Return null.
     */
    public static Object printList(List l) {
            if (l==null) {
                System.out.println();
                return null;
            }
            System.out.print(first(l) + " ");
            return printList(rest(l));
    }
    
    /** = the elements of list l, separated by commas and delimited by ( and )
     */
    public static String toString(List l) {
           return "(" + listElements(l) + ")";
    }
    
    /** = the elements of this list, separated by commas and delimited by ( and ) */
    public String toString() {
        return toString(this);
    }
    
    /** = the elements of list l, separated by commas */
    public static String listElements(List l) {
            if (l==null)
                {  return "";  }
            if (l.next==null)
                {  return "" + first(l);  }
            return "" + first(l) + ", " + listElements(rest(l));
   }

    
    /** = "o is a member of l" */
    public static boolean isMember(Object o, List l) {
        if (l == null)
            return false;
         if (o==null) {
            return first(l)==null || isMember(o, rest(l));
        }
        // {l is not null and o is not null}
        return o.equals(first(l)) || isMember(o, rest(l));
    }
    
    /** = a list whose elements are those of l, in the same order, but with
          the first occurrence of o deleted. If l contains no such element,
          return a new list that has the same elements as l
     */
    public static List deleteFirst(Object o, List l) {
        if (l==null)
            return null;
        if (o==null) {
            if (first(l) == null)
                return rest(l);
            return prepend(first(l),deleteFirst(o, rest(l)));
        }
        // {o is not null}
        if (o.equals(first(l)))
            return rest(l);
        return prepend(first(l),deleteFirst(o, rest(l)));
    }
    
    /** = a list whose elements are those of l, in the same order, but with
          all occurrences of o deleted. If l contains no such element,
          return a new list that has the same elements as l
     */
    public static List deleteAll(Object o, List l) {
        if (l==null)
            return null;
        if (o==null) {
            if (first(l) == null)
                return deleteAll(o, rest(l));
            return prepend(first(l),deleteAll(o, rest(l)));
        }
        // {o is not null}
        if (o.equals(first(l)))
            return deleteAll(o, rest(l));
        return prepend(first(l),deleteAll(o, rest(l)));
    }
    
    /** = 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));
    }
    
    /** = reverse of l */
    public static List reverse(List l) {
        if (l==null)
            return null;
        return append(reverse(rest(l)), prepend(first(l),null));
    }
    
    /** = the set difference of l1 and l2: the set of elements that
          are in l1 but not in l2. Precondition: l1 does not contain
          duplicates and l2 does not contain duplicates
       */
    public static List difference(List l1, List l2) {
        if (isEmpty(l1))
            return l1;
        if (isMember(first(l1), l2))
            return difference(rest(l1), l2);
        return prepend(first(l1), difference(rest(l1), l2));
    }
    
    /** = the union of sets l1 and l2: the set of all elements that are in
          at least one of l1 and l2.  Precondition: l1 does not contain
          duplicates and l2 does not contain duplicates
       */
    public static List union(List l1, List l2) {
        if (isEmpty(l1))
            return l2;
        if (isMember(first(l1), l2))
            return union(rest(l1), l2);
        return prepend(first(l1), union(rest(l1), l2));
    }
    
    /** = the intersection of sets l1 and l2: the set of all elements that are in
          both l1 and l2.  Precondition: l1 does not contain
          duplicates and l2 does not contain duplicates
       */
    public static List intersection(List l1, List l2) {
        if (isEmpty(l1))
            return l1;
        if (isMember(first(l1), l2))
            return prepend(first(l1), intersection(rest(l1), l2));
        return intersection(rest(l1), l2);
    }

    
}</pre></body></html>