The Collections API and Generics

Collections

Just data structures

• provide general, reusable implementations of common data structures

• are not inherently part of the language per se…

• simply implemented as classes

Java Collections

implemented through an interface hierarchy

• therefore, all data structures implementation have the same API

• classes such as LinkedList implement these interfaces

Collection Interface

public interface Collection<E> {
//basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean containsAll(Collection<?> c);
Iterator<E> iterator();

//add/remove operators
boolean add(E element);
boolean remove(Object element);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();

//array operations
Object[] toArray{};
<T> T[] toArray(T[] a);
}

List interface

public interface List<E> extends Collection<E>
{
//positional access
E get(int index);
//add/remove operations
E set(int index, E element);
void add(int index, E element);
E remove(int index);
boolean addAll(int index, Collection<? extends E> c);
//search
int indexOf(Object o);
int lastIndexOf(Object o);
//range-view
List<E> subList(int from, int to);
}

Set Interface

public interface Set<E> extends Collection<E>
{
	//uniqueness operations
	boolean equals(Object o);
	int hashCode();
}

Queue Interface

public interface Queue<E> extends Collection<E>
{
	E element(); //return head item - exception if none
	E peek(); //return head item - null if none
	boolean offer(E e); //add item - false if full
	E remove(); //pop head item - exception if none
	E poll{}; //pop lead item - null if none

Common Implementations

• ArrayList ordered, indexed list

• LinkedList ordered, non-indexed

• PriorityQueue FIFO with optional prioritisation

• HashSet unique, unordered

• TreeSet unique, ordered

• HashMap hashed key-value pairs (no ordering)

• TreeMap hashed key-value pairs (ordered by key)

Using the Collections API

Collections are classes, so we just treat them as such

• Create an object using its constructor

• Use its methods to interact with that data structure

• Choose the best data structure for your application. ArrayList is a good default…

import java.util.Collections.*;
import java.util.*;

public class University
{
	public void doSomething()
	{
		ArrayList<Person> staff = new ArrayList<>();
		staff.add(new Person("Joe"));
		staff.add(new Person("Saad"));
	}
}

ArrayList<Person> = the type of things you want to store

Methods in Collections API

We can use any of the methods defined in the relevant interfaces

• add

• remove

• contains

• get

We can also iterate over them in loops

import java.util.Collections.*;
import java.util.*;

public class University
{
	public void doSomething()
	{
		ArrayList<Person> staff = new ArrayList<>();
		Person j = new Person("Joe"));
		Person s = new Person("Saad");
		staff.add(j);
		staff.add(j);
		for (Person p : staff)
			System.out.println(p.getName());
		staff.remove(j);
		if (staff.contains(s))
			System.out.println("Saad is a staff memmber!");
	}
}

ArrayList

Acts much like an extensible array

• Items are maintained in a sequence, add/removed dynamically, etc

• Items are also enumerated and indexed by location

• Implemented internally as a simple array…

• if the array becomes full, a new one is created and the data copied from the old one

ArrayList Complexities

• O(1) complexity for index lookups

• O(1) complexity for additions (on average!)

• O(n) complexity for remove

Makes this a good choice for a general purpose data structure

HashMap

Unordered collection of key/value pairs

• Note here we define two types when creating an object (key and value)

• put() and get() methods allow us to add/remove objects from the collection

• VERY fast. Approaching O(1) for key based addition, deletion, lookup

public class University
{
	public void doSomething()
	{
		Person j = new Person("Joe");
		HashMap<String, Person> users = new HashMap<>();
		users.put("Finneyj", j);
		Person p = users.get("finneyj");
	}
}

Generics

Classes can be parameterised, just like functions and methods

• Class definition can be appended with one or more formal type parameters in angled brackets

• These parameters represent types that need to be defined when an object of that class can be created using new…

• Within the class, the formal type parameter can be used in instance variables, method signatures…

public class LinkedList<E>
{
	private E data;
	public E getData()
	{
		return data;
	}
}

Using Generics

Formal type parameters bind to real types when objects are created using new

• The actual types are defined also in angled brackets at this point

• At this point, a new class is generated for that specific type…

• ...that class is then instantiated, and a strongly typed object reference returned

LinkedList<Person> staff = new LinkedList<Person>();