Transcript The Java Collections Package

The Java Collections Package
C. DeJong
Fall 2001
Introduction
• A collection is an object that contains other
objects
• Ex: a poker hand, a phone directory, a mail
folder
Collection framework features
• Interfaces
• Implementations
• Algorithms
– Polymorphic
• cf. the Standard Template Library (STL) in
C++
Benefits
•
•
•
•
Data structures and algorithms for free
Tested
A well-known standard
Software reuse
The Collection interface
• Root of the collections hierarchy
• Other interfaces extend Collection
• Java provides implementations of
subinterfaces (Set, List, etc)
• For passing and manipulating collections
generically
• Implementations have a constructor that
accepts a Collection parameter
Collection methods (basic)
•
•
•
•
•
•
int size()
boolean isEmpty()
boolean contains(Object element)
boolean add(Object element)
boolean remove(Object element)
Iterator iterator()
The Iterator interface
• Used to traverse elements of a Collection
• Can remove elements
• Methods
– boolean hasNext()
– Object next()
– void remove()
Using Iterator
// simple method to print out each element in a collection
// using an Iterator
public void printContents(Collection stuff)
{
for(Iterator i=stuff.iterator();i.hasNext();)
{
System.out.println(i.next());
}
}
Collection methods (bulk ops)
•
•
•
•
•
boolean containsAll(Collection c)
boolean addAll(Collection c)
boolean removeAll(Collection c)
boolean retainAll(Collection c)
void clear()
Collection methods (arrays)
• Object[] toArray()
• Object[] toArray(Object a[])
A note on Collection methods
• All Collection interfaces (Set, List, Map)
have these methods (why?)
• Not all are supported
• Optional operations not supported throw
UnsupportedOperationException
• Java uses Exceptions to represent errors at
runtime (more on this later…)
The Set interface
•
•
•
•
•
extends Collection interface
Cannot contain duplicate elements
Models the mathematical Set abstraction
Implemented by HashSet and TreeSet classes
Use HashSet in most cases
Set interface methods
• Basic (size, isEmpty, contains, add, remove,
iterator)
• Bulk (containsAll, addAll, removeAll,
retainAll, clear)
• Arrays (toArray)
Using the Set interface
import java.util.*;
public class FindDups
{
public static void main(String[] args)
{
Set s = new HashSet();
for (int i=0;i<args.length;i++)
if (!s.add(args[i]))
System.out.println("Duplicate detected " + args[i]);
System.out.println(s.size() + " distinct words detected: "
+ s);
}
}
java FindDups i came i saw i left
Duplicate detected: i
Duplicate detected: i
4 distinct words detected: [came, left, saw, i]
The List interface
•
•
•
•
•
•
extends Collection interface
Ordered
Duplicates OK
Elements have a position and index number
Similar to arrays
Implemented by ArrayList, LinkedList and
Vector (use ArrayList)
• beware of java.awt.List
List interface methods
• all methods from Collection interface
• Positional access (get, set, add, remove,
addAll)
• Search (indexOf, lastIndexOf)
• Iteration (listIterator)
• Range-view (subList)
Using the List interface
List list1 = new ArrayList();
list1.add("John");
list1.add("George");
List list2 = new Vector();
list2.add("Paul");
list2.add("Ringo");
list1.addAll(list2);
for (int i=0;i<list1.size();i++)
{
String name = (String)list1.get(i);
System.out.println(name); // John, then George, etc.
}
System.out.println((String)list1.get(1)); // George
The Map Interface
• does not extend Collection interface
• Maps keys to values ("associative array")
• Like List and arrays, but key instead of
index number
• implemented by HashMap, TreeMap and
HashTable (use HashMap)
Map interface methods
• no methods from Collection interface
• Basic (put, get, remove, containsKey,
containsValue, size, isEmpty)
• Bulk (putAll, clear)
• Collection views (keySet, values, entrySet)
using the Map interface
// sample Map to store state capitols by state abbreviation
private Map capitols = new HashMap();
capitols.put("MI","Lansing");
capitols.put("IL","Springfield");
capitols.put("TX","Austin");
capitols.put("CA","Sacramento");
String michiganCap = (String)capitols.get("MI");
System.out.println("The capitol of Michigan is "
+ michiganCap);
System.out.println("Map has " + capitols.size() + " elements");
capitols.clear(); // deletes all elements
System.out.println("Map has " + capitols.size() + " elements");
The Collections class
• Not the same as the Collection interface
• Static utility methods to operate on
Collection objects
Collections class methods
•
•
•
•
•
•
•
Searching
Sorting
Copying
Min/Max
Reverse
Shuffle
Synchronization
•
•
•
•
Unmodifiable
Singletons
Fill
Constants for empty…
– List
– Set
– Map
• Etc.
using the Collections class
import java.util.*;
public class CollectionsUse
{
public static void main(String args[])
{
List states = new ArrayList();
states.add("AL");
states.add("IL");
states.add("MI");
states.add("CA");
System.out.println("first state is " + Collections.min(states));
System.out.println("last state is " + Collections.max(states));
System.out.println("states in original order " + states);
Collections.sort(states);
System.out.println("states in sorted order " + states);
Collections.reverse(states);
System.out.println("states in reverse sorted order " + states);
Collections.shuffle(states);
System.out.println("states in random order " + states);
}
}