On Java - ArrayList - 2020

Three implementation of the List interface are provided in the java.util package: ArrayList, LinkedList, and Vector.
In this chapter we'll deal with ArrayList which is one of the most commonly used of all the classes in the Collections.

Some of the advantages of ArrayList over arrays are:

1. It can grow dynamically.
2. It provides more powerful insertion and search mechanisms that arrays.

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

List<String> myList =
new ArrayList<String>();

String [] myList =
new String[3]; 

String s1 = 
new String("Donald Knuth");
String s2 = 
new String("Edsger Dijkstra");
String s3 = 
new String("Alan Turing");

String s1 = 
new String("Donald Knuth");
String s2 = 
new String("Edsger Dijkstra");
String s3 = 
new String("Alan Turing");

myList.add(s1); 
myList.add(s2); 
myList.add(s3); 

myList[0] = s1;
myList[1] = s2;
myList[2] = s2;

int szList = myList.size();

int szList = myList.length;

Object o = myList.get(2);

String o = myList[2];

myList.remove(2);

myList[2] = null;

boolean isIn = myList.contain(s3);

boolean isIn = false;
for (String item : myList) {
  if(s3.equals(item)) {
    isIn = true;
    break;
  }
}

Let's look at the table in detail.

1. A plain old array has to know its size at the time it's created.

   	new String[3]
   	

   But for ArrayList, we just make an object of type ArrayList. It can grow dynamically.

   	new ArrayList<String>()
   	

2. To put an object in a regular array, we must assign it to a specific location.

   	myList[2] = s3;
   	

   With ArrayList, we can specify an index using the add(int, Object) method, or we can just add(Object) and the ArrayList will keep growing.

   	myList.add(s3);
   	

3. Arrays use array syntax that's not used anywhere else in Java.
   But ArrayList are plain old Java objects, so they have no special syntax.

   	myList[2]
   	

4. ArrayLists are parameterized
   

   	ArrayList<String>
   	

   The in angle bracket is a "type parameter" as opposed to ArrayList which means, "a list of Animals".

Here is an array example: how to create and to pass into a method:

import java.util.*;

public class test {
	public static void main(String[] args) {
		System.out.println("Binary search");
		(new test()).go();
	}
	
	public void go() {
		int[] array = new int[]{0,1,2,3,4,5,6,7,8,9};
		int x = BinarySearch(array, 4);
	        if(x == -1)	
	    	    System.out.println(x+" is not in the array!");
	        else
	    	    System.out.println(x+" is at " + x);				
	}
	
	public int BinarySearch(int[] a, int n) {
		int upper = a.length - 1;
		int lower = 0;
		int mid = 0;
		
		while(lower <= upper) {
			mid = (upper + lower)/2;
			if(n < a[mid])
				upper = mid - 1;
			else if(n > a[mid])
				lower = mid + 1;
			else 
				return mid;
		}
		return -1;
	}
}

Output:

Binary search
4 is at 4

The following code is a slightly modified version using ArrayList instead of the simple integer array. I made some changes to the code: two classes instead of just one.

// test.java

package com.bogo;

import java.util.ArrayList;

public class test {
	public static void main(String[] args) {
		System.out.println("Binary search");
		(new test()).go();
	}
	
	public void go() {
		ArrayList<Integer> array = new ArrayList<Integer>();
		for(int i = 0; i < 10; i++) {
			array.add(i);
		}
		Algorithms al = new Algorithms();
		int x = al.BinarySearchArrayList(array, 4);
	        if(x == -1)	
	    	    System.out.println(x+" is not in the array!");
	        else
	    	    System.out.println(x+" is at " + x);		
		
	}
}

// Algorithms.java

package com.bogo;

import java.util.ArrayList;

public class Algorithms {
	
	public int BinarySearch(int[] a, int n) {
		int upper = a.length - 1;
		int lower = 0;
		int mid = 0;
		
		while(lower <= upper) {
			mid = (upper + lower)/2;
			if(n < a[mid])
				upper = mid - 1;
			else if(n > a[mid])
				lower = mid + 1;
			else 
				return mid;
		}
		return -1;
	}
	
	public int BinarySearchArrayList(ArrayList<Integer> a, int n) {
		int upper = a.size() - 1;
		int lower = 0;
		int mid = 0;
		
		while(lower <= upper) {
			mid = (upper + lower)/2;
			if(n < a.get(mid))
				upper = mid - 1;
			else if(n > a.get(mid))
				lower = mid + 1;
			else 
				return mid;
		}
		return -1;
	}
}

We're going to do a simple sorting for the ArrayList of Strings. But we'll use a utility from java.util.Collections class not from the ArrayList's method, sort().

import java.util.*;
public class StringArrayList {
	public static void main(String[] args) {
		ArrayList<String> Universities =
			new ArrayList<String>();
		Universities.add("Carnegie Mellon");
		Universities.add("MIT");
		Universities.add("UC Berkeley");
		Universities.add("Stanford");
		Universities.add("Cornell");
		Universities.add("Illinois-Urbana-Champaign");
		System.out.println("--Unsorted--");
		for(String s: Universities) {
			System.out.println(s);
		}
		System.out.println("\n--Sorted--");
		Collections.sort(Universities);
		for(String s: Universities) {
			System.out.println(s);
		}
	}
}

Output from the run is:

--Unsorted--
Carnegie Mellon
MIT
UC Berkeley
Stanford
Cornell
Illinois-Urbana-Champaign

--Sorted--
Carnegie Mellon
Cornell
Illinois-Urbana-Champaign
MIT
Stanford
UC Berkeley

import java.util.*;
import java.io.*;

class University {
	// Three instance variables for the University attribute in the file.
	String name;
	String city;
	String state;
	// The variables are all set in the constructor
	// when the University is created
	University (String n, String c, String s) {
		name = n;
		city = c;
		state = s;
	}
	public String getName() {
		return name;
	}
	public String getCity() {
		return city;
	}
	public String getState() {
		return state;
	}
	// Override toString(), because when we do a
	// System.out.println(aUniversityObject), we want to
	// see the name of the University. When we do a 
	// System.out.println(aListOfUniversities), it calls
	// the toString() method of each element in the list.
	public String toString() {
		return name;
	}
}

public class UnivArrayList {
	// ArrayList of University object 
	// instead of String.
	ArrayList<University> uList =
		new ArrayList<University>();
	
	public static void main(String[] args) {
		new UnivArrayList().go();
	}
	
	public void go(){
		getUniversities();
		System.out.println(uList);
		Collections.sort(uList);
		System.out.println(uList);
	}
	void getUniversities(){
		try {
			File file = new File("UnivList.txt");
			BufferedReader r = 
				new BufferedReader(new FileReader(file));
			String line = null;
			while ( !((line = r.readLine()).isEmpty()) ){
				addUniversity(line);
			}
		} catch(Exception e) {
			e.printStackTrace();
		}
	}
	void addUniversity(String lineToParse) {
		String[] s = lineToParse.split("/");
		// Create a new University object using the three strings. 
		// Then add the University to the list.
		University nextUniv = new University(s[0],s[1],s[2]);
		uList.add(nextUniv);
	}
}

Input file, UnivList.txt is:

Carnegie Mellon University /Pittsburgh/ PA
Massachusetts Institute of Technology /Cambridge/MA
University of California-Berkeley /Berkeley/ CA
Cornell University /Ithaca,/NY
University of Illinois-Urbana-Champaign /Urbana/ IL
University of Washington /Seattle/WA
Princeton University /Princeton/NJ

The University list file holds three attributes instead of just one. And we want all of them in our list, so we need to make a University class with instance variables for all three University attributes.

But the code won't compile. Instead we'll get the following message:

Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	Bound mismatch: The generic method sort(List<T>) of type Collections is not 
	applicable for the arguments (ArrayList<University>). 
	The inferred type University is not a valid substitute for 
	the bounded parameter <T extends Comparable<? super T>>

	at UnivArrayList.go(UnivArrayList.java:47)
	at UnivArrayList.main(UnivArrayList.java:41)

And we may get additional information as well though it's telling the same thing:

Bound mismatch: 
	The generic method sort(List<T>) of type Collections is not
	applicable for the arguments (ArrayList<University>). 
	The inferred type University is not a valid substitute 
	for the bounded parameter <T extends Comparable<? super T>>

We know for sure that the Collections class has a sort() method and we used it in the previous section. We sorted successfully the ArrayList of Strings but not with this ArrayList of University Objects!

The error message says there is a mismatch between sort(List<T>) and (ArrayList<University>). And it gives us some keyword that can be a clue to our problem. The keyword is Comparable as in "parameter <T extends Comparable<? super T>>"

Actually, String implements Comparable, and that's the reason why we could sort a list of Strings using Collections.sort() method. But our University object did nothing related to the Comparable interface, and probably that's why we failed in sorting.

The Comparable Interface is used by the Collections.sort() method to sort List and it is also used by java.util.Arrays.sort() method to sort array of objects.

So, how we implement Comparable?
To implement Comparable, a class must implement a method, compareTo().

We are fortunate because the Comparable interface is really simple, with only one method to implement:

public interface Comparable<T> {
	int CompareTo(T o);

int n = thisObj.compareTo(anotherObj);

It returns:

1. n: positive
   thisObj > anotherObj
2. n: zero
   thisObj = anotherObj
3. n: negative
   thisObj < anotherObj

It looks like the will be called on one University object, passing that University a compareTo() method reference to a different University.

The sort() method is using compareTo() to find out the way how it should sort things. Because we have to implement compareTo() for our classes, we can set our own criteria to sort instances of our classes.

In other words, our big job now is to decide what makes one University greater than another; and then implement the compareTo() method to reflect that.

The modified version for the University class:

import java.util.*;
import java.io.*;

class University implements Comparable<University>{
	String name;
	String city;
	String state;
	University (String n, String c, String s) {
		name = n;
		city = c;
		state = s;
	}
	public String getName() {
			return name;
	}
	public String getCity() {
			return city;
	}
	public String getState() {
			return state;
	}
	public String toString() {
		return name + " " + city + " " + state + "\n";
	}
	public int compareTo(University u) {
		return name.compareTo(u.getName());
	}
}

public class UnivArrayList {
	// ArrayList of University object 
	// instead of String.
	ArrayList<University> uList =
		new ArrayList<University>();
	
	public static void main(String[] args) {
		new UnivArrayList().go();
	}
	
	public void go(){
		getUniversities();
		System.out.println(uList);
		Collections.sort(uList);
		System.out.println(uList);
	}
	void getUniversities(){
		try {
			File file = new File("UnivList.txt");
			BufferedReader r = 
				new BufferedReader(new FileReader(file));
			String line = null;
			while ( !((line = r.readLine()).isEmpty()) ){
				addUniversity(line);
			}
		} catch(Exception e) {
			e.printStackTrace();
		}
	}
	void addUniversity(String lineToParse) {
		String[] s = lineToParse.split("/");
		// Create a new University object using the three strings. 
		// Then add the University to the list.
		University nextUniv = new University(s[0],s[1],s[2]);
		uList.add(nextUniv); 
	}
}

The new output we got:

[Carnegie Mellon University  Pittsburgh  PA
, Massachusetts Institute of Technology  Cambridge MA
, Stanford University  Stanford  CA
, University of California-Berkeley  Berkeley  CA
, Cornell University  Ithaca NY
, University of Illinois-Urbana-Champaign  Urbana  IL
, University of Washington  Seattle WA
, Princeton University  Princeton NJ
, University of Texas-Austin  Austin  TX
, Georgia Institute of Technology  Atlanta GA
]
[Carnegie Mellon University  Pittsburgh  PA
, Cornell University  Ithaca NY
, Georgia Institute of Technology  Atlanta GA
, Massachusetts Institute of Technology  Cambridge MA
, Princeton University  Princeton NJ
, Stanford University  Stanford  CA
, University of California-Berkeley  Berkeley  CA
, University of Illinois-Urbana-Champaign  Urbana  IL
, University of Texas-Austin  Austin  TX
, University of Washington  Seattle WA
]

It worked!
It prints the list, then calls sort which puts the University in alphabetical order by name.

Let's summarize what we've been through.
We were able to pass the ArrayList<University> to the sort() only after the University class implemented Comparable since that's the way sort().

Let's look at the declaration of sort() method in detail. In the api for java.util.Collections:

public static <T extends Comparable<? super T>> void sort(List<T< list)

1. T extends Comparable
   This says "Whatever T is must be of type Comparable."
   Comparable is an interface, so this reads,"T must be implements the Comparable interface.
   It doesn't matter whether the Comparable is a class or interface... we still say extends because in generics, extends means extends or implements.
2. <? super T>
   It just mean that the type parameter for Comparable must be of type T or one of T's supertypes.
3. List<T>
   We can pass in only a List (or subtype of list, like ArrayList) that uses a parameterized type that extends Comparable

There's new problem: If we want two different list of the University list, one by the name and one by the state!

However, when we make a collection element comparable by having it implement Comparable, we get only one chance to implement the compareTo() method. So what we can do about it?

Let's look at the Collections class API again!
There's a second sort() method. It takes a Comparator.

sort(List<T> list, Comparator<? super T>c)

This method is an overloaded version of sort() that takes both a list and something called a Comparator. The Comparator interface gives us:

1. The capability to sort a given collection any number of different ways.
2. We can use it to sort instances of any class-even classes we can't modify-unlike the Comparable interface, which forces us to change the class whose instances we want to sort.
3. The interface is very easy to implement, having only one method, compare().

   public interface Comparator<T> {
   	int compare(T o1, T o2);
   }
   

Which one?
sort(List o) or sort(List o, Comparator c)?

1. Invoking the one-argument sort(List o)
   This means the list element's compareTo() method determines the order. So the elements in the list MUST implement the Comparable interface.


2. Invoking the sort(List o, Comparator c)
   This means the list element's compareTo() method will NOT be called, and the Comparator's compare() method will be used instead. That means the elements in the list do NOT need to implement the Comparable interface.

Here is a new code uses Comparator.

import java.util.*;
import java.io.*;

class University implements Comparable<University>{
	String name;
	String city;
	String state;
	University (String n, String c, String s) {
		name = n;
		city = c;
		state = s;
	}
	public String getName() {
			return name;
	}
	public String getCity() {
			return city;
	}
	public String getState() {
			return state;
	}
	public String toString() {
		return name + " " + city + " " + state + "\n";
	}
	public int compareTo(University u) {
		return name.compareTo(u.getName());
	}
}

public class UnivArrayList2 {
	ArrayList<University> uList =
		new ArrayList<University>();
	
	public static void main(String[] args) {
		new UnivArrayList2().go();
	}
	
	// Create a new inner class that implements Comparator
	// (note that its type parameter matches the type we're
	// going to compare - in this case University objects)
	class StateCompare implements Comparator {
		// We're letting the String variables(for state) 
		// do that actual comparison, since Strings already
		// know how to alphabetize themselves.
		public int compare(University one, University two) {
			return one.getState().compareTo(two.getState());
		}
	}
	
	public void go(){
		getUniversities();
		System.out.println(uList);
		Collections.sort(uList);
		// Invoke sort(), passing it the list and 
		// a reference to the new custom Comparator object.
		StateCompare stateCompare =
			new StateCompare();
		Collections.sort(uList, stateCompare);
		System.out.println(uList);
	}
	void getUniversities(){
		try {
			File file = new File("UnivList.txt");
			BufferedReader r = 
				new BufferedReader(new FileReader(file));
			String line = null;
			while ( !((line = r.readLine()).isEmpty()) ){
				addUniversity(line);
			}
		} catch(Exception e) {
			e.printStackTrace();
		}
	}
	void addUniversity(String lineToParse) {
		String[] s = lineToParse.split("/");
		// Create a new University object using the three strings. 
		// Then add the University to the list.
		University nextUniv = new University(s[0],s[1],s[2]);
		uList.add(nextUniv); 
	}
}

What we did in the code:

1. Created an inner class that implements Comparator (and thus compare() method that does the work previously done by compareTo()).
2. Made an instance of the Comparator inner class.
3. Called the overloaded sort() method, giving it both the University list and the instance of the Comparator inner class.

The output is sorted by the name of the state:

[Carnegie Mellon University  Pittsburgh  PA
, Massachusetts Institute of Technology  Cambridge MA
, Stanford University  Stanford  CA
, University of California-Berkeley  Berkeley  CA
, Cornell University  Ithaca NY
, University of Illinois-Urbana-Champaign  Urbana  IL
, University of Washington  Seattle WA
, Princeton University  Princeton NJ
, University of Texas-Austin  Austin  TX
, Georgia Institute of Technology  Atlanta GA
]
[Stanford University  Stanford  CA
, University of California-Berkeley  Berkeley  CA
, University of Illinois-Urbana-Champaign  Urbana  IL
, Carnegie Mellon University  Pittsburgh  PA
, University of Texas-Austin  Austin  TX
, Georgia Institute of Technology  Atlanta GA
, Massachusetts Institute of Technology  Cambridge MA
, Princeton University  Princeton NJ
, Cornell University  Ithaca NY
, University of Washington  Seattle WA
]

int objOne.compareTo(objTwo)

int compare(objOne, objTwo)