A collection is an object that is composed of elements.

• The elements can be either:
  • Values in a primitive type (such as int).
  • References to objects.

• For example, an array is:
  • A collection of elements.
  • Of the same type.
  • That are stored contiguously in memory.
• Contiguous means "adjacent", so the individual elements are stored next to each other.
  • Actually, all that matters is that, to a user of an array, the elements are stored as if they were contiguous, so an element can be accessed directly from its index.

For example, we can create an array of five String elements (strictly speaking, each element is a reference to a String object.

String[] names = new String[5];

• Here, the new operator allocates space for an array of five String references.
  • Each initialized to null by the Java Virtual Machine (JVM).
  • And returns a reference to the beginning of the space allocated.
  • This reference is stored in names.
     
• There is an important consequence of the fact that that arrays are sorted contiguously:
  • An individual element in an array can be accessed without first accessing any of the other individual elements.
  • This is called the random access property.

Drawabacks of arrays

1. The size of the array is fixed.
   • Space for the entire array (of primitive values or references) must be allocated before any elements can be stored in the array.
   • If that size is too small, a larger array must be allocated and the contents of the smaller array copied to the larger array.
2. Another problem with arrays is that the programmer must provide all the code for operating on an array.
   • For example, inserting and deleting in an array may require that many elements be moved.
   • Suppose an array's indexes range from 0 to 999, inclusive.
   • And there are elements stored in order in the locations 0 to 755.
   • To insert an element into the location with index 300, we must first move the elements at indexes 300 to 755 into the locations at indexes 301 to 756.
      

• A collection class is a class in which each instance is a collection of elements, and each element is a a reference to an object.
• For example,
  • A String object.
  • A FullTimeEmployee object. can be an element.
• Values in a primitive type are not objects, so we cannot create an instance of a collection class in which each element is of type int.
• But for each primitive type, there is a corresponding class, called a wrapper class, whose purpose is to enable a primitive type to be represented by (that is, wrapper inside) a class.
   

The Java Collections Framework includes a number of collection classes that have wide applicability.

• All of those collection classes have some common methods.

• For example, each collection class has an isEmpty() method whose method specification is:

/** Determines if this collection has no elements. 
* 
* @return true – if this collection has no elements. 
* 
*/
public boolean isEmpty()

Instances of a collection class usually consume memory in proportion to the number of elements in the collection.

• So the way such a collection is stored in memory can have a substantial impact on the space efficiency of a program.

Contiguous Relations

• One straightforward way to store a collection instance in memory is to store, in an array, a reference to each element in the collection.

That is, an array could be field in the collection class.

• Such a class is called a contiguous-collection class.

For example, the ArrayList class has an array field, and a reference to each element in an ArrayList instance is stored in that instance's array.

• For many applications of contiguous-collection classes, the random access feature of an array is a great asset.

What about the disavantages, cited earlier, of an array.

• The size of an array is fixed.
• The programmer is responsible for writing all the code that works with the array.
   
• With a contiguous-collection class, those are problems for the developer of the class, not for users of that class.
• Basically, the developer of a contiguous collection class writes the code-once-for methods that manipulate that array.
• The user may not even be aware that there is an array field in the class, and by the Principle of Data Abstraction, would not rely on that field anyway.

Links Relation

• Instead of a contiguous relationship, the elements are related by links.
• A link is another name for a reference.
• Basically, each element is housed in a special object called an entry (sometimes called a node).
• Within each entry object there will be at least one link to another entry object.
   

An abstract class is a class that is:

• Allowed to have abstract methods as well as defined methods.
• The abstract methods must be defined on each subclass (unless the subclass is also abstract).

public abstract class Parent {
	/**
	* Returns the String object "I am".
	* 
	* @returns "I am".
	* 
	*/
	public String getPrefix() 
	{
		return "I am";
	} // method getPrefix

	/**
	* Returns a String object.
	*
	* @return a String object.
	* 
	*/
	public abstract String getClassName();	
} //class Parent

• An abstract class is denoted by the abstract modifier at the beginning of its declaration.
• And within an abstract class,
  • Each abstract method's heading must include the modifier abstract before the return type.
  • A semicolon after the method heading.
• Because the Parent class lacks a definition for one of its methods, we cannot instantiate the Parent class.
• That is, we cannot define a Parent object.

Parent p = new Parent(); // illegal because Parent is an abstract class.

We can now declare two subclasses, Child1 and Child2, of Parent.

public class Child1 extends Parent 
{
	/**
	* Returns the String object "Child1".
	* 
	* @return the String object "Child1".
	* 
	*/
	public String getClassName() 
	{
		return "Child1";
	} // method getClassName
} // class Child1

public class Child2 extends Parent 
	/**
	* Returns the String object "Child2".
	* 
	* @return the String object "Child2".
	* 
	*/
	public String getClassName() 
	{
		return "Child2";
	} // method getClasssName
} // class Child2.

• The main benefit of abstract methods is that they:
  • Promote flexibility (defined methods may be, but need not be, overriden in subclasses).
  • Promote Consistency (abstract-class headings must be identical in subclasses).

Parent p;

int code;

// Get the value for code;
...

if(code == 1) 
	p = new Child1();
else
	p = new Child2();
System.out.println(p.getPrefix() + " " + p.getClassName());

• The variable p is a polymorphic reference, so the version of getClassName() called depends on the type-Child1 or Child2-of the object referenced by p.

The output will be "I am Child1" or "I am Child2", depending on the value of the variable code.

• The Java Collections Framework has quite a few abstract classes:
  • AbstractCollection.
  • AbstractList.
  • AbstractSet.

Typically, one of these classes will:

• Declare as abstract any method whose definition depends on fields in its subclasses.
• Define any method whose definition does not depend on those fields.

Here are a few more details on the relationship between interfaces, abstract classes, and fully defined classes.

1. If a class implements some but not all of the methods in the interface, then the class would have to be declared as an abstract class-and therefore cannot be instantiated.
2. An interface can extend one or more other interfaces. For example, we could have:

public interface Container extends Collection, Comparable {

}

3. A class can extend at most one other class.
   • By default, the Object class is the superclass of every class.
   • Multiple inheritance- the ability of a class to have more than one immediate superclass-is illegal in Java.
   • Multiple inheritance is illegal because of the danger of ambiguity.
      
   • For example, viewing a teaching assistant as both a student and an employee, we could have a TeachingAssistant class that is the immediate subclass of classes Student and StaffMember.
      
   • Now suppose classes Student and StaffMember each has its own getHolidays() method.
   • If we define,

TeachingAssistant teacher = new TeachingAssistant();

4. A class can implement more than one interface.
   • For example, we could have:

class NewClass implements Interface1, Interface2 {

}

• This feature, especially when combined with feature 3, allows us to come close to achieving multiple inheritance.
• We can write:

class NewClass extends OldClass implements Interface1, Interface2 {


}

• There is no ambiguity when a method is invoked because any methods in an interface are abstract, and any non-final methods can be explicitly Overriden-that is, re-defined- in the subclass.
• For example, suppose OldClass, Interface1, and Interface2 all have a writeOut() method, and we have:

NewClass myStuff = new NewClass();
...
myStuff.writeOut();

Which versions of the writeOut() method will be invoked?

• Certainly not the version from Interface1 or Interface2, because those methods must be abstract.
• If NewClass implements a writeOut() method, that is the one that will be invoked.
• Otherwise, the version of writeOut() method defined in (or inherited by) OldClass will be invoked.

For example, suppose we want to declare and initialize an ArrayList object to hold a collection of grade point averages in which each grade point average will be stored as a Double.

ArrayList<Double> gpaList  = new ArrayList<Double>();

• Only elements of type Double can be inserted into gpaList; an attempt to insert a String or Integer element will be disallowed by the compiler.

As a result, you can be certain that any element retrieved from gpaList will be of type Double.

1. The add method inserts the element argument at the end of the ArrayList object.

gpaList.add(new Double(2.7));

• This will append to the end of gpaList a (reference to a) Double object whose double value is 2.7.''

2. For retrievals, the get method returns the element in the ArrayList object at the specified index.

Double gpa = gpaList.get(0);

Note 1: we don't need to cast the expression on the right-hand side to Double because the element at index 0 of gpaList must of type Double.

Note 2: now suppose that we want to add that grade point average to double variable sum initialized to 0.0.

• The method doubleValue() in the Double class returns the double value corresponding to the calling Double object.
• The assignment to sum is:

sum = sum + gpa.doubleValue();

In this example, ArrayList<Double> is a parameterized type.

• A parameterized type consists of a class or interface identifier followed, in angle brackets, by a list of one or more class identifiers separated by commas.
• A parameterized type is sometimes called "generics".

If you make a mistake and try to insert an element of type String for example, you will be notified at compile time.

• Without parameterized types, the insertion would be allowed, but the assignment of (Double)gpaList.get(0) to gpa would generate a ClassCastException at runtime.
• And this exception, if uncaught, could crash a critical program.

Using boxing and unboxing

• Boxing --> To simplify your working with parameterized collection classes, the Java compiler automatically translates primitive values into wrapper objects.

gpaList.add(2.7);

• Unboxing --> translates a wrapper object into its primitive value.

sum = sum + gpa;

• The collection interface has E-for "element"-as the type parameter.
• That is, E is replaced with an actual class, such as Double or FullTimeEmployee, in the declaration of an instance of any class that implements the interface.

public class ArrayList<E> implements Collection<E> ...

• Here is an instance of the ArrayList class with FullTimeEmployee elements:

ArrayList<FullTimeEmployee> employeeList = new ArrayList<FullTimeEmployee>();

• The Collection interface provides a core of methods useful for applications.
• But each application will almost certainly have some specialized tasks that do not correspond to any method in the Collection interface.

1. Given a Collection object of students, print out each student who made the Dean's list.
2. Given a Collection object of words, determine how many are four-letter words.
3. Given a Collection object of club members, update the dues owed for each member.
4. Given a Collection object of full-time employees, calculate the average salary for the employees.

Notice that in each of the four examples above, the task entails accessing each element in a Collections object.

Iterators

• Iterators are objects that allow the elements of Collection objects to be accessed in a consistent way.
• Each iterator class must itself implement the following Iterator interface.

public interface Iterator<E> {
	/**
	* Determines if this Iterator object is positioned at an element in this Collections object.
	* 
	* @return true - if this Iterator object is positioned at an element in this Collection object
	*
	*/
	boolean hasNext();

	/**
	* Advances this Iterator object, 
	* and returns the element this Iterator object was positioned at before
	* this call was made.
	* 
	* @throws NoSuchElementException - if this Iterator object is not positioned at an element in the Collection object.
	*/
	E next();

	/**
	* Removes the element returned by the most recent call to next().
	* The behavior of this Iterator object is unspecified if the underlying collection is modified - while this iteration is in progress - other than by calling this remove() method.
	*
	* @throws IllegalStateException - 
	* if next() had not been called before this call to remove(),
	* or if there had been an intervening call to remove() between the most recent call to next() and this call.
	*/
	void remove(); 
} // interface Iterator<E>

Iterators inside Collections interface

/**
* Returns an Iterator object over this Collection object.
*
* @return an Iterator object over this Collection object.
*
*/
Iterator<E> iterator();

• The value returned is (a reference to) an Iterator object, that is, an object in class that implements the Iterator interface.
• With the help of this method, a user can iterate through a Collection object with String elements, and we want to print out each element in myCol .
• We first create an iterator object:

Iterator<String> itr = myCol.iterator();

• The variable itr is a polymorphic reference:
  • It can be assigned a reference to an object in any class that implements the Iterator<String> interface.
• The actual iteration is fairly easy:

String word;
while(itr.hasNext()) {
	word = itr.next();
	if(word.charAt(0) == 'a') 
		System.out.println(word);
} //while

• The false iteration is:

while(itr.hasNext()) {
	if(itr.next().charAt(0) == 'a') 
		System.out.println(itr.next());
}

Because of the two calls to itr.next(), if the next word returned during a loop iteration starts with the letter 'a', the word after that word will be printed.

for each loop

• Very often, all we want to do during an iteration is to access each element in the collection.
• For such situations, Java provides an enhanced for statement.
  • Sometimes called for-each loop.

for(String word: myCol) 
	if(word.charAt(0) == 'a')
		System.out.println(word);

The colon should be interpreted as "in", so the control part of this for statement can be read "For each word in myCol".

• The effect of this code is the same as before, but some of the drudgery-creating and initializing the iterator, and invoking hasNext() and next() methods-has been relegated to the compiler.

Example of using for-each loop

// Calculates the mean grade-point-average
import java.util.*;

public class EnhancedFor {
	public static void main(String[] args) {
		new EnhancedFor().run();
	} // method main

	public void run() {
		final double MIN_GPA = 0.0, MAX_GPA = 4.0, SENTINEL = -1.0;
		final String INPUT_PROMPT = "Please enter a GPA in the range" + " from " + MIN_GPA + " to " + MAX_GPA + ", inclusive (or " + SENTINEL + " to quit): ";
		final String RANGE_ERROR = "The grade point average must" + " be at least " + MIN_GPA + " and at most " + MAX_GPA + ".";
		final String MESSAGE = "\n\nThe mean GPA is ";
		final String NO_VALID_INPUT = "\n\nError: there were no valid " + "grade-point-averages in the input.";
		
		ArrayList<Double> gpaList = new ArrayList<Double>();
		Scanner sc = new Scanner(System.in);
		double oneGPA, sum = 0.0;
	
	  while(true) {
		  try {
				System.out.print(INPUT_PROMPT);
				oneGPA = sc.nextDouble();
				if(oneGPA == SENTINEL)
					break;
			    if(oneGPA < MIN_GPA || oneGPA > MAX_GPA) 
				    throw new ArithmeticException(RANGE_ERROR);
				gpaList.add(oneGPA); // inserts at end of gpaList.
			}	// try
			catch(Exception e) {
				System.out.println(e + "\n");
				sc.nextLine();
			} // catch 
		} // while
		for(Double gpa : gpaList) 
			sum += gpa;
		if(gpaList.size() > 0) 
			System.out.println(MESSAGE + (sum/gpaList.size()));
		else
		   System.out.println(NO_VALID_INPUT);
	} // method run	
} // class EnhancedFor

The iterator vs the for-each loop.

• For-each loop -->
  1. Simplifies your code.
     • Makes your code easier to understand.
     • You should use it whenever possible, that is, if you were to use an iterator instead, the only iterator methods invoked would be haNext() and next().
• Iterator -->
  • You cannot use an enhanced for loop if the collection may be modified during the iteration.
  • For example, if you wanted to delete, from gpaList, each grade-point-average below 1.0, you would need to explicitly set up an iterator:

Iterator<Double> itr = gpaList.iterator();
while(itr.hasNext()) 
	if(itr.next() < 1.0) 
		itr.remove();

The use of iterators is an example of a design pattern.

• A general programming technique that can be applied in a variety of situations.
• The basic idea is that each design pattern provides you with a problem that occurs frequently and the outline of a solution.

Java Collection Framework's List interface extends the Collection interface by providing some index-based related methods.

• For example, there is a get method that returns the element at a given index.
   
• In any List object, that is, in any instance of a class that implements the List interface, the elements are stored in sequence, according to an index.
• Duplicates are allowed.

import java.util.*;
public class RandomList {
	public static void main(String[] args) {
		new RandomList().run();
	}
	public void run() {
		final int SEED = 111;
		List<Integer> randList = new ArrayList<Integer>();
		
		Random r = new Random(SEED);

		// Insert 10 random integers, in the range 0..99, into randList:
		for(int i = 0; i < 10; i++) 
			randList.add(r.nextInt(100)); // insertion

		// Print out randList:
		System.out.println(randList);

		// See if 22 is in randList:
		if(randList.contains(22)) 
			System.out.println("Yes, 22 is in randList.");
		else
			System.out.println("No, 22 is not in randList.");

		// Print out the Integer at index 3.
		System.out.println(randList.get(3) + " is at index 3");

		// Remove the Integer at index 6.
		randList.remove(6);

		// Insert a new random Integer at index 5:
		randList.add(5, r.nextInt(100));

		// Print out randList.
		System.out.println(randList);

		// Remove all even Integers:
		Iterator<Integer> itr = randList.iterator();
		while(itr.hasNext()) 
			if(itr.next() % 2 == 0) 
				itr.remove();
		// Print out randList.
		System.out.println(randList);   
	} // method run.
} // class RandomList

Some notes:

• The line:

System.out.println(randList);

• Is equivalent to:

System.out.println(randList.toString());

Every class in the Java Collections Framework has a toString() method, so all the elements in a an instance of one of the classes can be output with a single call to println().

• The output is:
   

We could not use an enhanced for statement to iterate over randList because we needed to remove some of that object's elements, not merely access them.

• In the program, randList is declared as a polymorphic reference and then immediately initialized as a reference to an ArrayList obje.
• To re-run the program with a LinkedList, the only change is the constructor call:

List<Integer> randList = new LinkedList<Integer>();

How do these versions compare?

• ArrayList advantage --> part of the program-printing the Integer at index 3-is executed more quickly with an ArrayList object because of the random access ability of the underlying array.
• LinkedList advantage --> part of it-removing all even Integer elements-is executed more quickly with a LinkedList object.
  • That is because an entry in a linked list can be removed by adjusting links: no movement of elements is needed.

In general, there is no "best" implementation of the List interface.