Collections
Java Collections Framework, List, Map
© Amir Kirsh
Collections Overview
Collection classes in Java are containers
of Objects which by polymorphism can
hold any class that derives from Object
(which is actually, any class)
Using Generics the Collection classes can
be aware of the types they store
2
Collections
Java collections refer to a collection of individual objects
that are represented as a single unit. You can
perform all operations such as searching, sorting,
insertion, manipulation, deletion, etc., on Java
collections just like you do it on data.
A Java collection framework provides an architecture to
store and manipulate a group of objects. A Java
collection framework includes the following:
• Interfaces
• Classes
• Algorithm
Need for Java Collection Framework
• Reducing the effort required to write the code by
providing useful data structures and algorithms
• Java collections provide high-performance and high-
quality data structures and algorithms thereby
increasing the speed and quality
• Unrelated APIs can pass collection interfaces back
and forth
• Decreases extra effort required to learn, use, and
design new API’s
• Supports reusability of standard data structures and
algorithms
Which Collections do we have?
There are two main interfaces for all the collection
types in Java:
– Collection<E>
– Map<K,V>
List of all Collections and related frameworks:
http://java.sun.com/javase/6/docs/technotes/guides/collections/ref
erence.html
5
Java Collection Framework
Iterator and Collection interface
Methods in Iterator interface
• hasNext()
• next()
• remove()
Methods in collection interface include–
• Add – add(), addAll()
• Remove – remove(), removeAll(), retailAll(),…
• check the presence of elements from the collection – contains(),
containsAll()
List
List interface is the child interface of Collection interface. It
inhibits a list type data structure in which we can store the
ordered collection of objects. It can have duplicate values.
List interface is implemented by the classes ArrayList
(dynamic array non synchronized), LinkedList
(implemented using doubly linked list), Vector (dynamic
array sunchronized), and Stack.
To instantiate the List interface, we must use :
Vector
Vector is a synchronized dynamically growable array
with efficient access by index
Example: initialCapacity is optional
Vector<Integer> vec =
new Vector<Integer>(10/*initialCapacity*/);
vec.add(7);
Vector is an old (Java 1.0) container and is less in use today,
replaced mainly by ArrayList (Java 1.2) which is not synchronized
9
ArrayList
ArrayList is a non-synchronized dynamically
growable array with efficient access by index
Example: initialCapacity is optional
ArrayList<Integer> arr =
new ArrayList<Integer>(10/*initialCapacity*/);
arr.add(7);
ArrayList is in fact not a list (though implementing the List interface)
If you need a list use the LinkedList class!
When performing many
How should I know? adds and removes
10
String s = (String) itr.next();
System.out.println(s);
Example ArrayList
1st Example:
static public void main(String[] args) {
ArrayList argsList = new ArrayList();
for(String str : args) {
argsList.add(str);
}
if(argsList.contains("Koko") {
System.out.println("We have Koko");
}
String first = (String)argsList.get(0);
System.out.println("First: " + first);
}
12
Example ArrayList
2nd Example – now with Generics:
static public void main(String[] args) {
ArrayList<String> argsList =
new ArrayList<String>();
for(String str : args) {
argsList.add(str); // argsList.add(7) would fail
}
if(argsList.contains("Koko") {
System.out.println("We have Koko");
}
String first = argsList.get(0); // no casting!
System.out.println("First: " + first);
}
13
HashMap
HashMap is a non-synchronized key-value Hashtable
Example 1:
HashMap<String, Person> id2Person;
...
Person p = id2Person.get("021212121");
if(p != null) {
System.out.println("found: " + p);
}
HashMap is a Java 1.2 class.
There is a similar Java 1.0 class called Hashtable which is
synchronized and is less used today
14
HashMap
Example 2:
HashMap<String, Integer> frequency(String[] names) {
HashMap<String, Integer> frequency =
new HashMap<String, Integer>();
for(String name : names) {
Integer currentCount = frequency.get(name);
if(currentCount == null) {
currentCount = 0; // auto-boxing
}
frequency.put(name, ++currentCount);
}
return frequency;
}
15
HashMap
Example 2 (cont’):
public static void main(String[] args) {
System.out.println( (
(
frequency(new String[]{
"Momo", "Momo", "Koko", "Noa", "Momo", "Koko"
) )
}).toString());
}
HashMap has a nice toString!
Print out of this main is:
{Koko=2, Noa=1, Momo=3}
HashMap doesn’t
guarantee any order!
16
HashMap
For a class to properly serve as a key in HashMap
the equals and hashCode methods should both be
appropriately implemented
Example:
Parameter MUST be Object
public class Person {
public String name; (and NOT Person!)
boolean equals(Object o) {
return (o instanceof Person &&
((Person)o).name.equals(name));
}
public int hashCode() {
return name.hashCode();
}
}
17
Hash Map Example Traversal
19
20
Exercise 1
Create an ArrayList of Student objects (Name, Age) and
display the objects with age greater than 10.
21
Exercise 2
Get Strings from the command line, present in the console a
vertical bar chart of the frequency of each letter in the input.
• Treat small and capital letters the same -- as capital
• Ignore any char that is not an English letter
Example
For the following input: Hey how are you?
we expect the following chart:
A #
E ##
H ##
O ##
R #
Y ##
U #
W #
22
