Howdy. 

Project will be decided soon. 

Let's implement ArrayList. 

You only have arrays and you want the ArrayList behavior. 

Target is something like this: 

ArrayList<String> a = new ArrayList<String>();

But we can't do this. 

The issue is: Generic Programming. 

We have to wait until Generics to be able to use <'s properly. 

So let's look at how LinkedList's work: 

public class LinkedList {

}

public class Program {
  public static void main(String[] args) {
    LinkedList a = new LinkedList(); 
    System.out.println( a ); // [ ] 
    a = a.cons( "Pacers" ); 
    System.out.println( a ); 
    a = a.cons( 23 ); 
    System.out.println( a ); [ 23, "Pacers" ]
    System.out.println( a.first() ); 23
    System.out.println( a.rest() ); // [ "Pacers" ]
    System.out.println( a.contains( "Cubs" ) ); // false    
  } 
}

 1. choose data representation
 2. give some examples
 3. choose name, number and names of arguments, as well as types (contract, signature)
 4. purpose statement (semantic aspect that the syntax can't account for)
 5. give some examples of input and output 
 6. write the template 
 7. finish code
 8. run the check-expects 

Let's agree on this specific test:

public class Program {
  public static void main(String[] args) {
    LinkedList a = new LinkedList(); 
    System.out.println( a ); // [ ] 
    a.cons( "Pacers" ); 
    System.out.println( a ); 
    a.cons( 23 ); 
    System.out.println( a ); // [ 23, "Pacers" ]
    System.out.println( a.first() ); // 23
    System.out.println( a.rest() ); // [ "Pacers" ]
    System.out.println( a.contains( "Cubs" ) ); // false    
  } 
}

Let's make a data representation choice: 

import java.util.*;

public class LinkedList extends ArrayList<Object> {
  public void cons(Object a) {
    this.add(0, a); 
  }
  public Object first() {
    return this.get(0);      
  }
  public LinkedList rest() {
    LinkedList result = new LinkedList(); 
    for (int i = 1; i < this.size(); i++)
      result.add( this.get(i) );
    return result; 
  }
}

Then our test program produces: 

public class Program {
  public static void main(String[] args) {
    LinkedList a = new LinkedList(); 
    System.out.println( a ); // [ ] 
    a.cons( "Pacers" ); 
    System.out.println( a ); 
    a.cons( 23 ); 
    System.out.println( a ); // [ 23, "Pacers" ]
    System.out.println( a.first() ); // 23
    System.out.println( a.rest() ); // [ "Pacers" ]
    System.out.println( a.contains( "Cubs" ) ); // false    
  } 
}

In DrJava:

Welcome to DrJava.  Working directory is C:\Users\soicloan\Desktop\11142016
> run Program
[]
[Pacers]
[23, Pacers]
23
[Pacers]
false
> 

Notice we didn't have to provide a contains method. 

Now we change the data representation:

http://www.techeuler.com/wp-content/uploads/2016/07/Tail-linked-list.png

public class LinkedList {
  Object car; 
  LinkedList cdr; 
  LinkedList(Object first, LinkedList rest) {
    this.car = first; 
    this.cdr = rest; 
  }
  public Object first() {
    return this.car; 
  }
  public LinkedList rest() {
    return this.cdr;  
  }
  public LinkedList cons(Object e) {
     return new LinkedList(e, this);  
  }
  public String toString() {
    return this.car + " " + this.cdr;  
  }
  public boolean contains(Object e) {
    if (this.car.equals( e ))
      return true;
    else
      if (this.cdr == null) return false;
      else return this.cdr.contains( e );
  }
}

public class Program {
  public static void main(String[] args) {
    LinkedList a = null; 
    System.out.println( a ); // [ ]     
    a = new LinkedList( "Pacers", a ); 
    System.out.println( a ); 
    a = a.cons( 23 ); 
    a = a.cons( "Cubs" ); 
    System.out.println( a ); // [ 23, "Pacers" ]
    System.out.println( a.first() ); // 23
    System.out.println( a.rest() ); // [ "Pacers" ]
    System.out.println( a.contains( "Pacers" ) ); // true 
    System.out.println( a.contains( "Cleveland" ) ); // false     
  } 
}

--

Welcome to DrJava.  Working directory is C:\Users\soicloan\Desktop\second attempt
> run Program
null
Pacers null
Cubs 23 Pacers null
Cubs
23 Pacers null
true
false
> 

------------

FYI the generic programming version of it is: 

public class LinkedList<T> {
  T car; 
  LinkedList<T> cdr; 
  LinkedList(T first, LinkedList<T> rest) {
    this.car = first; 
    this.cdr = rest; 
  }
  public T first() {
    return this.car; 
  }
  public LinkedList<T> rest() {
    return this.cdr;  
  }
  public LinkedList<T> cons(T e) {
     return new LinkedList<T>(e, this);  
  }
  public String toString() {
    return this.car + " " + this.cdr;  
  }
  public boolean contains(T e) {
    if (this.car.equals( e ))
      return true;
    else
      if (this.cdr == null) return false;
      else return this.cdr.contains( e );
  }
}