Java Collections

1
 Java Collections
• A collection is an object that groups multiple
elements into a single unit
• Very useful
» store, retrieve and manipulate data
» transmit data from one method to another
» data structures and methods written by hotshots in the field

2
 Collections Framework
• Unified architecture for representing and
manipulating collections.
• A collections framework contains three things
» Interfaces
» Implementations
» Algorithms

3- cse403-10-Collections © 2003 University of Washington 3

4
5
 Collection Interface
• Defines fundamental methods
» int size();
» boolean isEmpty();
» boolean contains(Object element);
» boolean add(Object element); // Optional
» boolean remove(Object element); // Optional
» Iterator iterator();

• These methods are enough to define the basic

6
 Iterator Interface
• Defines three fundamental methods
» Object next()
» boolean hasNext()
» void remove()
• These three methods provide access to the
contents of the collection
• An Iterator knows position within collection
• Each call to next() “reads” an element from the
collection
» Then you can use it or remove it

7
Iterator Position

8
 Example - SimpleCollection
public class SimpleCollection {
public static void main(String[] args) {
Collection c;
c = new ArrayList();
System.out.println(c.getClass().getName());
for (int i=1; i <= 10; i++) {
c.add(i + " * " + i + " = "+i*i);
}
Iterator iter = c.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}

9
List Interface Context

Collection

List

10
 List Interface
• The List interface adds the notion of order to a
collection
• The user of a list has control over where an element is
added in the collection
• Lists typically allow duplicate elements
• Provides a ListIterator to step through the elements in
the list.

11
 ListIterator Interface
• Extends the Iterator interface
• Defines three fundamental methods
» void add(Object o) - before current position
» boolean hasPrevious()
» Object previous()
• The addition of these three methods defines the basic
behavior of an ordered list
• A ListIterator knows position within list

12
Iterator Position - next(), previous()

13
 ArrayList and LinkedList Context

Collection

List

ArrayList LinkedList

14
 List Implementations
• ArrayList
» low cost random access
» high cost insert and delete
» array that resizes if need be
• LinkedList
» sequential access
» low cost insert and delete
» high cost random access

15
 ArrayList overview
• Constant time positional access (it’s an array)
• One tuning parameter, the initial capacity

public ArrayList(int initialCapacity) {

16
 ArrayList methods
• The indexed get and set methods of the List interface are
appropriate to use since ArrayLists are backed by an array
» Object get(int index)
» Object set(int index, Object element)
• Indexed add and remove are provided, but can be costly if
used frequently
» void add(int index, Object element)
» Object remove(int index)
• May want to resize in one shot if adding many elements
» void ensureCapacity(int minCapacity)

17
 LinkedList overview
• Stores each element in a node
• Each node stores a link to the next and previous
nodes
• Insertion and removal are inexpensive
» just update the links in the surrounding nodes
• Linear traversal is inexpensive
• Random access is expensive
» Start from beginning or end and traverse each node while
counting

18
 LinkedList entries
private static class Entry {
Object element;
Entry next;
Entry previous;

Entry(Object element, Entry next, Entry previous) {

private Entry header = new Entry(null, null, null);

public LinkedList() {
header.next = header.previous = header;
}
19
 LinkedList methods
• The list is sequential, so access it that way
» ListIterator listIterator()
• ListIterator knows about position
» use add() from ListIterator to add at a position
» use remove() from ListIterator to remove at a position
• LinkedList knows a few things too
» void addFirst(Object o), void addLast(Object o)
» Object getFirst(), Object getLast()
» Object removeFirst(), Object removeLast()

3- cse403-10-Collections © 2003 University of Washington 20

Collection

Set

21
 Set Interface
• Same methods as Collection
» different contract - no duplicate entries
• Defines two fundamental methods
» boolean add(Object o) - reject duplicates
» Iterator iterator()
• Provides an Iterator to step through the elements
in the Set
» No guaranteed order in the basic Set interface
» There is a SortedSet interface that extends Set

22
HashSet and TreeSet Context

Collection

Set

HashSet TreeSet

23
 HashSet
• Find and add elements very quickly
» uses hashing implementation in HashMap
• Hashing uses an array of linked lists
» The hashCode() is used to index into the array
» Then equals() is used to determine if element is in the
(short) list of elements at that index
• No order imposed on elements
• The hashCode() method and the equals() method
must be compatible
» if two objects are equal, they must have the same
hashCode() value
24
 TreeSet
• Elements can be inserted in any order
• The TreeSet stores them in order
» Red-Black Trees out of Cormen-Leiserson-Rivest
• An iterator always presents them in order
• Default order is defined by natural order
» objects implement the Comparable interface
» TreeSet uses compareTo(Object o) to sort
• Can use a different Comparator
» provide Comparator to the TreeSet constructor

25
Map Interface Context

Map

26
 Map Interface
• Stores key/value pairs
• Maps from the key to the value
• Keys are unique
» a single key only appears once in the Map
» a key can map to only one value
• Values do not have to be unique

27
 Map methods
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()

28
 Map views
• A means of iterating over the keys and values in a Map
• Set keySet()
» returns the Set of keys contained in the Map
• Collection values()
» returns the Collection of values contained in the Map.
This Collection is not a Set, as multiple keys can map
to the same value.
• Set entrySet()
» returns the Set of key-value pairs contained in the Map.
The Map interface provides a small nested interface
called Map.Entry that is the type of the elements in this
Set.
29
HashMap and TreeMap Context

Map

HashMap TreeMap

30
 HashMap and TreeMap
• HashMap
» The keys are a set - unique, unordered
» Fast

• TreeMap
» The keys are a set - unique, ordered
» Same options for ordering as a TreeSet
• Natural order (Comparable, compareTo(Object))
• Special order (Comparator, compare(Object, Object))
31
 Bulk Operations
• In addition to the basic operations, a Collection may
provide “bulk” operations
boolean containsAll(Collection c);
boolean addAll(Collection c); // Optional
boolean removeAll(Collection c); // Optional
boolean retainAll(Collection c); // Optional
void clear(); // Optional
Object[] toArray();
Object[] toArray(Object a[]);

32
Utilities Context

33
 Utilities
• The Collections class provides a number of static
methods for fundamental algorithms
• Most operate on Lists, some on all Collections
» Sort, Search, Shuffle
» Reverse, fill, copy
» Min, max
• Wrappers
» synchronized Collections, Lists, Sets, etc
» unmodifiable Collections, Lists, Sets, etc

34
 Wrapper Classes
• Wrapper class in Java is one whose object wraps or contains primitive data types.
When we create an object to a wrapper class, it contains a field and in this field, we
can store primitive data types. In other words, we can wrap a primitive value into a
wrapper class object.
Need of Wrapper Classes
• There are certain needs for using the Wrapper class in Java as mentioned below:
• They convert primitive data types into objects. Objects are needed if we wish to
modify the arguments passed into a method (because primitive types are passed by
value).
• The classes in java.util package handle only objects and hence wrapper classes help
in this case.
• Data structures in the Collection framework, such as ArrayList and Vector, store
only objects (reference types) and not primitive types.
• An object is needed to support synchronization in multithreading.

35
Advantages of Wrapper Classes
• Collections allow only object data.
• On object data we can call multiple methods
compareTo(), equals(), toString()
• The cloning process only works on objects
• Object data allows null values.
• Serialization allows only object data.

36
1. Autoboxing
• The automatic conversion of primitive types to
the object of their corresponding wrapper
classes is known as autoboxing. For example –
conversion of int to Integer, long to Long,
double to Double, etc.

37
 /Java program to demonstrate Autoboxing
import java.util.ArrayList;
class Autoboxing {
public static void main(String[] args)
{
char ch = 'a';
// Autoboxing- primitive to Character object conversion
Character a = ch;
ArrayList<Integer> arrayList = new ArrayList<Integer>();
// Autoboxing because ArrayList stores only objects
arrayList.add(25);
// printing the values from object
System.out.println(arrayList.get(0));
}
}

38
2. Unboxing
• It is just the reverse process of autoboxing.
Automatically converting an object of a
wrapper class to its corresponding primitive
type is known as unboxing. For example –
conversion of Integer to int, Long to long,
Double to double, etc.

39
 Java program to demonstrate Unboxing
import java.util.ArrayList;
class Unboxing {
public static void main(String[] args)
{
Character ch = 'a';
// unboxing - Character object to primitive conversion
char a = ch;
ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(24);
// unboxing because get method returns an Integer object
int num = arrayList.get(0);
// printing the values from primitive data types
System.out.println(num);
}
}

40