8. Collections
The Collections
Collection Framework
It contains the following
Interfaces - Allow collections to be manu=ipulated independently of the details of their representation
Implementation (aka Classes) - Comcrete implementation of the collection interface
Algorithms - Methods that provide computation e.g. seach, sort. Algorithms are polymorphic, same method for many different implementations of collection interface
The Collection Interfaces
Collection Interface
A Collection can hold a group of objects in different ways which Set, List and Queue provide.
List Interface
This extends Collection and an instance of List stores an ordered collection of elements. It can contain duplicate entries
Set Interface
This extends Collection to handle sets, which must contain unique elements (defined by the equals method of the object type it holds).
SortedSet Interface
This extends Set with property of sorted sets.
NavigableSet Interface
This extends SortedSet and allows us to navigate through the sorted list, providing methods for retrieving the next element greater or smaller than a given element of the Set.
Queue Interface
This extends Collection to handle queue with two sides. Entries are added to its tail end while entries are removed from the top or the head. e.g. FIFO
The Collection Classes
Java provides a set of standard collection classes that implement Collection interfaces.
Some of the classes provide full implementations that can be used as-is and others are abstract class, providing skeletal implementations that are used as starting points for creating concrete collections.
AbstractCollection
Implements most of the Collection interface.
AbstractList
Extends AbstractCollection and implements most of the List interface.
AbstractSequentialList
Extends AbstractList for use by a collection that uses sequential rather than random access of its elements.
ArrayList
Implements a dynamic array by extending AbstractList. Fast - Iterate\Read, Slow - Add\Remove
LinkedList
Implements a linked list by extending AbstractSequentialList. Slow - Iterate\Read, Fast - Add\Remove
PriorityQueue
Implements a Queue interface, that keeps its elements ordered automatically. It has functionality similar to TreeSet, except that it allows duplicate entries.
AbstractSet
Extends AbstractCollection and implements most of the Set interface.
HashSet
Extends AbstractSet for use with a hash table.
LinkedHashSet
Extends HashSet to allow insertion-order iterations as with List, does not allow duplicates as with sets.
TreeSet
Extends AbstractSet. Implements a set stored in a tree.
The Map Interface
Map Interface
The Map interface, one which oddly enough has no relation to the Collection interface. A Collection operates on one entity, while a Map operates on two: a unique key.
This maps unique keys to values.
Map.Entry
This describes an element (a key/value pair) in a map. This is an inner class of Map.
SortedMap
This extends Map with property of sorted maps.
NavigableMap
This extends SortedMap and allows us to navigate through the sorted maps, providing methods for retrieving the next element greater or smaller than a given element of the Map.
AbstractMap
Implements most of the Map interface.
HashMap
Extends AbstractMap to use a hash table.
TreeMap
Extends AbstractMap to use a tree. Implements a map stored in a tree.
WeakHashMap
Extends AbstractMap to use a hash table with weak keys.
LinkedHashMap
Extends HashMap to allow insertion-order iterations.
IdentityHashMap
Extends AbstractMap and uses reference equality when comparing documents.
The Collections Algorithms
The collections framework defines several algorithms that can be applied to collections and maps.
These algorithms are defined as static methods within the Collections class.
Several of the methods can throw a ClassCastException, which occurs when an attempt is made to compare incompatible types, or an UnsupportedOperationException, which occurs when an attempt is made to modify an unmodifiable collection.
Collections define three static variables: EMPTY_SET, EMPTY_LIST, and EMPTY_MAP. All are immutable.
Iterator
Iterator enables you to cycle through a collection, obtaining or removing elements.
ListIterator extends Iterator to allow bidirectional traversal of a list.
Comparator
Both TreeSet and TreeMap store elements in a sorted order. However, it is the comparator that defines precisely what sorted order means.
This interface lets us sort a given collection any number of different ways.
Legacy Classes
Vector
This implements a dynamic array. It is similar to ArrayList, performance is suboptimal, so no new code should ever have to use it. An ArrayList or LinkedList simply does a better job.
Hashtable
Hashtable was part of the original java.util and is a concrete implementation of a Dictionary, performance is suboptimal.
The class is deprecated because of its suboptimal performance.
Stack
Stack is a subclass of Vector that implements a standard last-in, first-out stack.
Dictionary
Dictionary is an abstract class that represents a key/value storage repository and operates much like Map.
Properties
Properties is a subclass of Hashtable. It is used to maintain lists of values in which the key is a String and the value is also a String.
BitSet
A BitSet class creates a special type of array that holds bit values. This array can increase in size as needed.
Collections APIs
Collection Interface
boolean add(Object obj)
Adds obj to the invoking collection. Returns true if obj was added to the collection. Returns false if obj is already a member of the collection, or if the collection does not allow duplicates.
boolean addAll(Collection c)
Adds all the elements of c to the invoking collection. Returns true if the operation succeeds (i.e., the elements were added). Otherwise, returns false.
void clear( )
Removes all elements from the invoking collection.
boolean contains(Object obj)
Returns true if obj is an element of the invoking collection. Otherwise, returns false.
boolean containsAll(Collection c)
Returns true if the invoking collection contains all elements of c. Otherwise, returns false.
boolean equals(Object obj)
Returns true if the invoking collection and obj are equal. Otherwise, returns false.
int hashCode( )
Returns the hash code for the invoking collection.
boolean isEmpty( )
Returns true if the invoking collection is empty. Otherwise, returns false.
Iterator iterator( )
Returns an iterator for the invoking collection.
boolean remove(Object obj)
Removes one instance of obj from the invoking collection. Returns true if the element was removed. Otherwise, returns false.
boolean removeAll(Collection c)
Removes all elements of c from the invoking collection. Returns true if the collection changed (i.e., elements were removed). Otherwise, returns false.
boolean retainAll(Collection c)
Removes all elements from the invoking collection except those in c. Returns true if the collection changed (i.e., elements were removed). Otherwise, returns false.
int size( )
Returns the number of elements held in the invoking collection.
Object[ ] toArray( )
Returns an array that contains all the elements stored in the invoking collection. The array elements are copies of the collection elements.
Object[ ] toArray(Object array[ ])
Returns an array containing only those collection elements whose type matches that of array.
Examples:
---------
List a1 = new ArrayList();
a1.add("Zara");
List l1 = new LinkedList();
Set s1 = new HashSet();
Map m1 = new HashMap();
m1.put("Zara", "8");
List Interface
void add(int index, Object obj)
Inserts obj into the invoking list at the index passed in the index. Any pre-existing elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten.
boolean addAll(int index, Collection c)
Inserts all elements of c into the invoking list at the index passed in the index. Any pre-existing elements at or beyond the point of insertion are shifted up. Thus, no elements are overwritten. Returns true if the invoking list changes and returns false otherwise.
Object get(int index)
Returns the object stored at the specified index within the invoking collection.
int indexOf(Object obj)
Returns the index of the first instance of obj in the invoking list. If obj is not an element of the list, .1 is returned.
int lastIndexOf(Object obj)
Returns the index of the last instance of obj in the invoking list. If obj is not an element of the list, .1 is returned.
ListIterator listIterator( )
Returns an iterator to the start of the invoking list.
ListIterator listIterator(int index)
Returns an iterator to the invoking list that begins at the specified index.
Object remove(int index)
Removes the element at position index from the invoking list and returns the deleted element. The resulting list is compacted. That is, the indexes of subsequent elements are decremented by one.
Object set(int index, Object obj)
Assigns obj to the location specified by index within the invoking list.
List subList(int start, int end)
Returns a list that includes elements from start to end.1 in the invoking list. Elements in the returned list are also referenced by the invoking object.
LinkedList Class
Constructor & Destructor
LinkedList( )
This constructor builds an empty linked list.
LinkedList(Collection c)
This constructor builds a linked list that is initialized with the elements of the collection c.
void addFirst(Object o)
Inserts the given element at the beginning of this list.
void addLast(Object o)
Appends the given element to the end of this list.
Object clone()
Returns a shallow copy of this LinkedList.
Object getFirst()
Returns the first element in this list. Throws NoSuchElementException if this list is empty.
Object getLast()
Returns the last element in this list. Throws NoSuchElementException if this list is empty.
Object removeFirst()
Removes and returns the first element from this list. Throws NoSuchElementException if this list is empty.
Object removeLast()
Removes and returns the last element from this list. Throws NoSuchElementException if this list is empty.
LinkedList ll = new LinkedList();
ll.add("A");
ll.add("B");
ll.add("C");
ll.remove("C");
ll.remove(0);
Object val = ll.get(0);
ArrayList Class
ArrayList( )
This constructor builds an empty array list.
ArrayList(Collection c)
This constructor builds an array list that is initialized with the elements of the collection c.
ArrayList(int capacity)
This constructor builds an array list that has the specified initial capacity. The capacity is the size of the underlying array that is used to store the elements.
The capacity grows automatically as elements are added to an array list.
Object clone()
Returns a shallow copy of this ArrayList.
void ensureCapacity(int minCapacity)
Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
protected void removeRange(int fromIndex, int toIndex)
Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.
void trimToSize()
Trims the capacity of this ArrayList instance to be the list's current size.
HashSet Class
HashSet( )
This constructor constructs a default HashSet.
HashSet(Collection c)
This constructor initializes the hash set by using the elements of the collection c.
HashSet(int capacity)
This constructor initializes the capacity of the hash set to the given integer value capacity. The capacity grows automatically as elements are added to the HashSet.
HashSet(int capacity, float fillRatio)
This constructor initializes both the capacity and the fill ratio (also called load capacity) of the hash set from its arguments.
Here the fill ratio must be between 0.0 and 1.0, and it determines how full the hash set can be before it is resized upward.
Specifically, when the number of elements is greater than the capacity of the hash set multiplied by its fill ratio, the hash set is expanded.
Object clone()
Returns a shallow copy of this HashSet instance: the elements themselves are not cloned.
HashSet hs = new HashSet();
hs.add("B");
Map Interface
void clear( )
Removes all key/value pairs from the invoking map.
boolean containsKey(Object k)
Returns true if the invoking map contains k as a key. Otherwise, returns false.
boolean containsValue(Object v)
Returns true if the map contains v as a value. Otherwise, returns false.
Set entrySet( )
Returns a Set that contains the entries in the map. The set contains objects of type Map.Entry. This method provides a set-view of the invoking map.
boolean equals(Object obj)
Returns true if obj is a Map and contains the same entries. Otherwise, returns false.
Object get(Object k)
Returns the value associated with the key k.
int hashCode( )
Returns the hash code for the invoking map.
boolean isEmpty( )
Returns true if the invoking map is empty. Otherwise, returns false.
Set keySet( )
Returns a Set that contains the keys in the invoking map. This method provides a set-view of the keys in the invoking map.
Object put(Object k, Object v)
Puts an entry in the invoking map, overwriting any previous value associated with the key. The key and value are k and v, respectively. Returns null if the key did not already exist. Otherwise, the previous value linked to the key is returned.
void putAll(Map m)
Puts all the entries from m into this map.
Object remove(Object k)
Removes the entry whose key equals k.
int size( )
Returns the number of key/value pairs in the map.
Collection values( )
Returns a collection containing the values in the map. This method provides a collection-view of the values in the map.
HashMap Class
HashMap( )
This constructor constructs a default HashMap.
HashMap(Map m)
This constructor initializes the hash map by using the elements of the given Map object m.
HashMap(int capacity)
This constructor initializes the capacity of the hash map to the given integer value, capacity.
HashMap(int capacity, float fillRatio)
This constructor initializes both the capacity and fill ratio of the hash map by using its arguments.
void clear()
Removes all mappings from this map.
Object clone()
Returns a shallow copy of this HashMap instance: the keys and values themselves are not cloned.
boolean containsKey(Object key)
Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value)
Returns true if this map maps one or more keys to the specified value.
Set entrySet()
Returns a collection view of the mappings contained in this map.
Object get(Object key)
Returns the value to which the specified key is mapped in this identity hash map, or null if the map contains no mapping for this key.
boolean isEmpty()
Returns true if this map contains no key-value mappings.
Set keySet()
Returns a set view of the keys contained in this map.
Object put(Object key, Object value)
Associates the specified value with the specified key in this map.
putAll(Map m)
Copies all of the mappings from the specified map to this map. These mappings will replace any mappings that this map had for any of the keys currently in the specified map.
Object remove(Object key)
Removes the mapping for this key from this map if present.
int size()
Returns the number of key-value mappings in this map.
Collection values()
Returns a collection view of the values contained in this map.
HashMap hm = new HashMap();
hm.put("Zara", new Double(3434.34));
double balance = ((Double)hm.get("Zara")).doubleValue();
Iterator
Iterator
boolean hasNext( )
Returns true if there are more elements. Otherwise, returns false.
Object next( )
Returns the next element. Throws NoSuchElementException if there is not a next element.
void remove( )
Removes the current element. Throws IllegalStateException if an attempt is made to call remove( ) that is not preceded by a call to next( ).
Iterator itr = al.iterator();
if(itr.hasNext())
Object element = itr.next();
ListIterator
void add(Object obj)
Inserts obj into the list in front of the element that will be returned by the next call to next( ).
boolean hasNext( )
Returns true if there is a next element. Otherwise, returns false.
boolean hasPrevious( )
Returns true if there is a previous element. Otherwise, returns false.
Object next( )
Returns the next element. A NoSuchElementException is thrown if there is not a next element.
int nextIndex( )
Returns the index of the next element. If there is not a next element, returns the size of the list.
Object previous( )
Returns the previous element. A NoSuchElementException is thrown if there is not a previous element.
int previousIndex( )
Returns the index of the previous element. If there is not a previous element, returns -1.
void remove( )
Removes the current element from the list. An IllegalStateException is thrown if remove( ) is called before next( ) or previous( ) is invoked.
void set(Object obj)
Assigns obj to the current element. This is the element last returned by a call to either next( ) or previous( ).
Comparator
The Comparator interface defines two methods: compare( ) and equals( ). The compare( ) method, shown here, compares two elements for order −
The compare Method
int compare(Object obj1, Object obj2)
obj1 and obj2 are the objects to be compared. This method returns zero if the objects are equal. It returns a positive value if obj1 is greater than obj2. Otherwise, a negative value is returned.
By overriding compare( ), you can alter the way that objects are ordered. For example, to sort in a reverse order, you can create a comparator that reverses the outcome of a comparison.
The equals Method
The equals( ) method, shown here, tests whether an object equals the invoking comparator −
boolean equals(Object obj)
obj is the object to be tested for equality. The method returns true if obj and the invoking object are both Comparator objects and use the same ordering. Otherwise, it returns false.
Overriding equals( ) is unnecessary, and most simple comparators will not do so.
import java.util.*;
class Dog implements Comparator<Dog>, Comparable<Dog> {
private String name;
private int age;
Dog() {
}
Dog(String n, int a) {
name = n;
age = a;
}
public String getDogName() {
return name;
}
public int getDogAge() {
return age;
}
// Overriding the compareTo method
public int compareTo(Dog d) {
return (this.name).compareTo(d.name);
}
// Overriding the compare method to sort the age
public int compare(Dog d, Dog d1) {
return d.age - d1.age;
}
}
public class Example {
public static void main(String args[]) {
// Takes a list o Dog objects
List<Dog> list = new ArrayList<Dog>();
list.add(new Dog("Shaggy", 3));
list.add(new Dog("Lacy", 2));
list.add(new Dog("Roger", 10));
list.add(new Dog("Tommy", 4));
list.add(new Dog("Tammy", 1));
Collections.sort(list); // Sorts the array list
for(Dog a: list) // printing the sorted list of names
System.out.print(a.getDogName() + ", ");
// Sorts the array list using comparator
Collections.sort(list, new Dog());
System.out.println(" ");
for(Dog a: list) // printing the sorted list of ages
System.out.print(a.getDogName() +" : "+ a.getDogAge() + ", ");
}
}
This will produce the following result −
Output
Lacy, Roger, Shaggy, Tammy, Tommy,
Tammy : 1, Lacy : 2, Shaggy : 3, Tommy : 4, Roger : 10,
References