Collections in Java - AAU

1 OOP: Collections1 Collections in java ArraysnHas special language support IteratorsnIterator (i) Collections (also called containers)nCollection (i)nSet (i), uHashSet (c), TreeSet (c)nList (i), uArrayList (c), LinkedList (c)nMap (i), uHashMap (c), TreeMap (c)OOP: Collections2 Array Most efficient way to hold references to objects. AdvantagesnAn array know the type it holds, , compile-time type array know its size, , ask for the array can hold primitive types directly. DisadvantagesnAn array can only hold one type of objects (including primitives).nArrays are fixed : Collections3 Array, Example Helper class and sort: binarySearch(), sort()nComparison: equals()(many overloaded)nInstantiation: fill()(many overloaded)nConversion: asList()class Car{};// minimal dummy classCar[] cars1; // null referenceCar[] cars2 = new Car[10]; // null referencesfor (int i = 0; i < ; i++)cars2[i] = new Car();// Aggregated initializationCar[] cars3 = {new Car(), new Car(), new Car(), new Car()};cars1 = {new Car(), new Car(), new Car()};OOP: Collections4 Overview of collection A collection is a group of data manipulate as a single object.

2 Corresponds to a bag. Insulate client programs from the , linked list, hash table, balanced binary tree Like C++'s Standard Template Library (STL) Can grow as necessary. Contain only Objects (reference types). Heterogeneous. Can be made thread safe (concurrent access). Can be made : Collections5 collection Interfaces Collections are primarily defined through a set of by a set of classes that implement the interfaces Interfaces are used of flexibility reasonsnPrograms that uses an interface is not tightened to a specific implementation of a is easy to change or replace the underlying collection class with another (more efficient) class that implements the same interface.

3 [Source: ]OOP: Collections6 collection Interfaces and Classes[Source: ]OOP: Collections7 The Iterator Interface The idea: Select each element in a collectionnHide the underlying collectionIterator hasNext() next() remove() collection isEmpty() add() remove() ..list Iterators are fail-fastnException thrown if collection is modified externally, , not via the iterator (multi-threading).OOP: Collections8 The Iterator Interface, an examplepublic static void main (String[] args){ArrayList cars = new ArrayList();for (int i = 0; i < 12; i++) (new Car());Iterator it = ();while ( ()) ((Car) ());}// the interface definitionInterface Iterator {boolean hasNext();Object next();// note "one-way" trafficvoid remove();}OOP: Collections9 The collection Interfacepublic interface collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element).}

4 // Optional Iterator iterator(); // Bulk Operations boolean containsAll( collection c); boolean addAll( collection c); // Optional boolean removeAll( collection c); // Optional boolean retainAll( collection c); // Optional void clear(); // Optional // Array Operations Object[] toArray(); Object[] toArray(Object a[]);}OOP: Collections10 The Set Interface Corresponds to the mathematical definition of a set (no duplicates are allowed). Compared to the collection interfacenInterface is constructor must create a collection without operation add cannot add an element already in the method call (set2) works at followsuset1 set2, and set2 set1 OOP: Collections11 Set Idioms set1 set2 (set2) set1 (set2) set1 (set2)OOP: Collections12 HashSet and TreeSet Classes HashSet and TreeSet implement the interface Set.

5 HashSetnImplemented using a hash ordering of , remove, and contains methods constant time complexity O(c). TreeSetnImplemented using a tree ordering of , remove, and contains methods logarithmic time complexity O(log (n)), where n is the number of elements in the : Collections13 HashSet, Example// [Source: ]import *;public class FindDups {public static void main(String args[]){Set s = new HashSet(); for (int i = 0; i < ; i++){if (! (args[i])) ("Duplicate detected: " + args[i]);} ( () + " distinct words detected: " + s); }}OOP: Collections14 The List Interface The List interface corresponds to an order group of elements.

6 Duplicates are allowed. Extensions compared to the collection interfacenAccess to elements via indexes, like arraysuadd (int, Object), get(int), remove(int), set(int, Object) (note set = replace bad name for the method)nSearch for elementsuindexOf(Object), lastIndexOf(Object)nSpecialized Iterator, call ListIteratornExtraction of sublistusubList(int fromIndex, int toIndex)OOP: Collections15 The List Interface, requirements compared to the collection Interface add(Object)adds at the end of the list. remove(Object)removes at the start of the list. (list2)the ordering of the elements is taken into consideration.

7 Extra requirements to the method (list2) implies that ()== () OOP: Collections16 The List Interface, interface List extends collection { // Positional Access Object get(int index); Object set(int index, Object element); // Optional void add(int index, Object element); // Optional Object remove(int index); // Optional abstract boolean addAll(int index, collection c); // Optional // Search int indexOf(Object o); int lastIndexOf(Object o); // Iteration ListIterator listIterator(); ListIterator listIterator(int index); // Range-view List subList(int from, int to);}OOP: Collections17 ArrayList and LinkedList Classes The classes ArrayList and LinkedList implement the List interface.

8 ArrayList is an array based implementation where elements can be accessed directly via the get and set choice for simple sequence. LinkedList is based on a double linked list nGives better performance on add and remove compared to poorer performance on get and set methods compared to : Collections18 ArrayList, Example// [Source: ]import *;public class Shuffle { public static void main(String args[]) { List l = new ArrayList(); for (int i = 0; i < ; i++) (args[i]); (l, new Random()); (l); }}OOP: Collections19 LinkedList, Exampleimport *;public class MyStack {private LinkedList list = new LinkedList();public void push(Object o){ (o);}public Object top(){return ().}}

9 }public Object pop(){return ();} public static void main(String args[]) {Car myCar; MyStack s = new MyStack(); (new Car());myCar = (Car) (); }}OOP: Collections20 The ListIterator Interfacepublic interface ListIterator extends Iterator { boolean hasNext(); Object next(); boolean hasPrevious(); Object previous(); int nextIndex(); int previousIndex(); void remove(); // Optional void set(Object o); // Optional void add(Object o); // Optional}OOP: Collections21 The Map Interface A Map is an object that maps keys to values. Also called an associative array or a dictionary.

10 Methods for adding and deletingnput(Object key, Object value)nremove (Object key) Methods for extraction objectsnget (Object key) Methods to retrieve the keys, the values, and (key, value) pairsnkeySet()// returns a Set nvalues()// returns a collection , nentrySet()// returns a setOOP: Collections22 The MAP Interface, interface Map { // Basic Operations Object put(Object key, Object value); Object get(Object key); Object remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk Operations void putAll(Map t); void clear(); // collection Views public Set keySet(); public collection values(); public Set entrySet(); // Interface for entrySet elements public interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); }}OOP: Collections23 HashMap and TreeMap Classes The HashMap and HashTree classes implement the Map interface.