Transcript Slides

Introduction to Java 2
Programming
Lecture 5
The Collections API
Overview
• Collection classes
– Types of collection
– Working with Collections
– Sorting
Collections
• Implementations of common data structures, such
as Linked Lists, Sets, etc.
– Part of the java.util package.
– Also known as “containers”
• Advantages
– Can hold any kind of object
– Much more flexible than arrays
• Disadvantages
– Not as efficient as arrays (for some uses)
– Can’t store primitive types
– Not type-safe. Store references to Object
Types of Collection
• Two Types of Containers
• Collections
– Group of objects, which may restricted or manipulated
in some way
– E.g. ordered to make a List or LinkedList
– E.g. a Set, an unordered group which can only contain
one of each item
• Maps
– Associative array, Dictionary, Lookup Table, Hash
– A group of name-value pairs
Java Collections
Collection Implementations
• Several implementations associated with each of
the basic interfaces
• Each has its own advantages/disadvantages
• Maps
– HashMap, SortedMap
• Lists
– ArrayList, LinkedList
• Sets
– HashSet, SortedSet
The Basics
• HashMap and ArrayList are most commonly
encountered
• Usual object creation syntax
• Always refer to the objects via one of the
Collections interfaces
– Take advantage of polymorphism
List myList = new ArrayList();
List otherList = new ArrayList(5);
Map database = new HashMap();
Set things = new HashSet();
Adding Items
• For Collections, use add()
List myList = new ArrayList();
myList.add(“A String”);
myList.add(“Other String”);
• For Maps, use put()
Map myMap = new HashMap();
myMap.put(“google”, “http://www.google.com”);
mpMap.put(“yahoo”, “http://www.yahoo.com”);
Copying
• Very easy, just use addAll()
List myList = new ArrayList();
//assume we add items to the list
List otherList = new ArrayList();
myList.addAll(myList);
Getting Individual Items
• Use get()
• Note that we have to cast the object to its original
type.
• Collections…
String s = (String)myList.get(1); //get first element
String s2 = (String)myList.get(10); //get tenth element
• Maps…
String s = (String)myMap.get(“google”);
String s2 = (String)mpMap.get(“yahoo”);
Getting All items
• For Lists, we could use a for loop, and
loop through the list to get() each item
• But this doesn’t work for Maps.
• To allow generic handling of collections,
Java defines an object called an Iterator
– An object whose function is to walk through a
Collection of objects and provide access to each
object in sequence
Getting All items
• Get an iterator using the iterator() method
• Iterator objects have three methods:
– next() – gets the next item in the collection
– hasNext() – tests whether it has reached the end
– remove() – removes the item just returned
• Basic iterators only go forwards
– Lists objects have a ListIterator that can go forward and
backward
Getting All items (List)
• Simple example:
List myList = new ArrayList();
//we add items
Iterator iterator = myList.iterator();
while (iterator.hasNext())
{
String s = (String)iterator.next();
//do something with it
}
Getting All Items (Map)
• Example of using a Map
• Note that we can get a Set of all keys (keySet)
or Collection of all values (values)
Map myMap = new HashMap();
//we add items
Iterator iterator = myMap.keySet.iterator();
while (iterator.hasNext()) {
String theKey = (String)iterator.next();
Object theValue = myMap.get(theKey);
//do something useful
}
Other Functions
• The java.util.Collections class has
many useful methods for working with
collections
– min, max, sort, reverse, search, shuffle
• Virtually all require your objects to
implement an extra interface, called
Comparable
Comparable
• The Comparable interface labels objects that can
be compared to one another.
– Allows sorting algorithms to be written to work on any
kind of object
– so long as they support this interface
• Single method to implement
public int compareTo(Object o);
• Returns
– A negative number of parameter is less than the object
– Zero if they’re equal
– A positive number if the parameter is greater than the
object
Comparable Example
public class Person implements Comparable {
private String email;
private String lastName;
public int compareTo(Object object) {
Person other = (Person)object;
//compare based on email address only
return other.getEmail().compareTo(email);
}
}
Comparable Example
Person a = new Person(“[email protected]”,
Dodds”);
Person b = new Person(“[email protected]”,
“Builder”);
List people = new ArrayList();
People.add(a);
People.add(b);
Java.util.Collections.sort(people);
//collection is now sorted by email
Comparator
• Like Comparable, but is a stand-alone object used
for comparing other objects
– Useful when you want to use your criteria, not that of
the implementor of the object.
– Or altering the behaviour of a system
• Many of the methods in the Collections object also
allow a Comparator to be specified
• Again method has single method:
public int compare(Object obj1, Object obj2)
Comparator Example
• Java String comparison is lexicographic not
alphabetic, I.e. based on the character set, not
alphabetic order
public class AlphaComparison implements Comparator
{
public int compare(Object obj1, Object obj2)
{
String s1 = ((String)o1).toLowerCase();
String s2 = ((String)o2).toLowerCase();
return s1.compareTo(s2);
}
}
Comparator Example
String one = “One”;
String two = “Two”;
String three = “Three”;
List strings = new ArrayList();
strings.add(one);
strings.add(two);
strings.add(three);
Collections.sort(strings, new AlphaComparison());
//now in alphabetical order