Unit – I

Collections
Collections Overview
• The Java Collections Framework standardizes the way in which groups
of objects are handled by your programs.
• added by J2SE 1.2
• Prior it was Dictionary, Vector, Stack, and Properties classes.
• These classes unifying theme lacked a central, e.g. the way that you
used Vector was different from the way that you used Properties.
• Java.util package contains al the classes and interfaces of collection
framework.
Goals of Collection Framework
• The framework had to be high-performance.
• The implementations for the fundamental collections (dynamic arrays,
linked lists, trees, and hash tables) are highly efficient. You seldom, if
ever, need to code one of these “data engines” manually.
• The framework had to allow different types of collections to work in a
similar manner and with a high degree of interoperability.
• Extending and/or adapting a collection is easy.
The Collection Interfaces
• The entire Collections Framework is built upon a set of standard
interfaces such as LinkedList, HashSet, and TreeSet etc.
• In addition to the collection interfaces, collections also use the
Comparator, RandomAccess, Iterator, and ListIterator interfaces.
• The collection interfaces allow some optional methods that enable
you to modify the contents of a collection. These methods are called
modifiable.
• Collections that do not allow their contents to be changed are called
unmodifiable.
• If an attempt is made to use one of these methods on an unmodifiable
collection, an UnsupportedOperationException is thrown.
The Collection Interface
• The Collection interface must be implemented by any class that
defines a collection.
• Collection extends the Iterable interface. This means that all
collections can be cycled through.
 Method Description

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 and 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 succeeded (i.e., the elements were added).
Otherwise, returns false.

void clear( ) Removes all elements from the invoking collection.

boolean contains(Object Returns true if obj is an element of the invoking collection.

obj) 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.
 Method Description

Iterator<E> iterator( ) Returns an iterator for the invoking collection.

boolean remove(Object Removes one instance of obj from the invoking collection.
obj) Returns true if the element was removed. Otherwise,
returns false.
boolean Removes all elements of c from the invoking collection.
removeAll(Collection 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.
The List Interface
• The List interface extends Collection and declares the behavior of a
collection that stores a sequence of elements.
• Elements can be inserted or accessed by their position in the list,
using a zero-based index.
• A list may contain duplicate elements.
 Method Description

void add(int index, E obj) Inserts obj into the invoking list at the index passed in
index. Any preexisting elements at or beyond the point
of insertion are shifted up. Thus, no elements are
overwritten.

boolean addAll(int index, Inserts all elements of c into the invoking list at the
Collection<? extends E> index passed in index. Any preexisting elements at or
c) beyond the point of insertion are shifted up. Thus, no
elements are overwritten. Returns true if the invoking
list changes and returns false otherwise.

E 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.
 Method Description

int lastIndexOf(Object Returns the index of the last instance of obj in the
obj) invoking list. If obj is not an element of the list, –1 is
returned.

ListIterator<E> Returns an iterator to the start of the invoking list.

listIterator( )

ListIterator<E> Returns an iterator to the invoking list that begins at the

listIterator(int index) specified index.

E 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.
The Set Interface
• The Set interface defines a set.
• It extends Collection and declares the behavior of a collection that
does not allow duplicate elements.
• It does not define any additional methods of its own.

The SortedSet Interface

• The SortedSet interface extends Set and declares the behavior of a
set sorted in ascending order.
 Method Description

Comparator<? super E> Returns the invoking sorted set’s comparator. If the
comparator( ) natural ordering is used for this set, null is returned.

E first( ) Returns the first element in the invoking sorted set.

SortedSet<E> headSet(E Returns a SortedSet containing those elements less than

end) end that are contained in the invoking sorted set.
Elements in the returned sorted set are also referenced
by the invoking sorted set.

E last( ) Returns the last element in the invoking sorted set.

The Queue Interface
• The Queue interface extends Collection interface.
• It declares the behavior of a queue, which is often a first-in, first-out
list.
 Method Description

E element( ) Returns the element at the head of the queue. The

element is not removed. It throws
NoSuchElementException if the queue is empty.

boolean offer(E obj) Attempts to add obj to the queue. Returns true if obj was
added and false otherwise.

E peek( ) Returns the element at the head of the queue. It returns

null if the queue is empty.
The element is not removed.

E remove( ) Removes the element at the head of the queue, returning

the element in the process.
It throws NoSuchElementException if the queue is empty.
The Map Interface
• The Map interface maps unique keys to values.
• A key is an object that you use to retrieve a value at a later date.
• Given a key and a value, you can store the value in a Map object.
 Method Description

void clear( ) Removes all key/value pairs from the invoking map.

boolean Returns true if the invoking map contains k as a key.

containsKey(Object k) Otherwise, returns false.

boolean Returns true if the map contains v as a value. Otherwise,

containsValue(Object v) returns false.
Set<Map.Entry<K, V>> Returns a Set that contains the entries in the map. The
entrySet( ) set contains objects of type Map.Entry. Thus, this
method provides a set-view of the invoking map.

boolean equals(Object Returns true if obj is a Map and contains the same
obj) entries. Otherwise, returns false.
 Method Description

V get(Object k) Returns the value associated with the key k. Returns null if
the key is not found.
int hashCode( ) Returns the hash code for the invoking map.

boolean isEmpty( ) Returns true if the invoking map is empty. Otherwise,

returns false.
Set<K> 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.

V put(K k, V 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.
 Method Description

V remove(Object k) Removes the entry whose key equals k.

int size( ) Returns the number of key/value pairs in the map.

Collection<V> values( ) Returns a collection containing the values in the map. This
method provides a collection-view of the values in the
map.
The Collection Classes
Class Description

AbstractCollection Implements most of the Collection interface.

AbstractList Extends AbstractCollection and implements most of the
List interface.
AbstractQueue Extends AbstractCollection and implements parts of the
Queue interface.
AbstractSequentialList Extends AbstractList for use by a collection that uses
sequential rather than random access of its elements.
LinkedList Implements a linked list by extending
AbstractSequentialList.
ArrayList Implements a dynamic array by extending AbstractList.
Class Description

ArrayDeque Implements a dynamic double-ended queue by extending

AbstractCollection and implementing the Deque interface.
(Added by Java SE 6.)
AbstractSet Extends AbstractCollection and implements most of the Set
interface.
EnumSet Extends AbstractSet for use with enum elements.

HashSet Extends AbstractSet for use with a hash table.

LinkedHashSet Extends HashSet to allow insertion-order iterations.
PriorityQueue Extends AbstractQueue to support a priority-based queue.

TreeSet Implements a set stored in a tree. Extends AbstractSet.

The ArrayList Class
• The ArrayList class extends AbstractList and implements the
List interface.
• ArrayList supports dynamic arrays that can grow as needed.
• In Java, standard arrays are of a fixed length. After arrays are
created, they cannot grow or shrink.
• To handle this situation, the Collections Framework defines
ArrayList
• In essence, an ArrayList is a variable-length array of object
references. That is, an ArrayList can dynamically increase or
decrease in size.
• ArrayLists are created with an initial size. When this size is
exceeded, the collection is automatically enlarged. When
objects are removed, the array can be shrunk.
• Constructors:

ArrayList( )
ArrayList(Collection<? extends E> c)
ArrayList(int capacity)
The LinkedList Class
• The LinkedList class extends AbstractSequentialList class.
• It implements the List, Deque, and Queue interfaces.
• It provides a linked-list data structure.
• Constructors:

LinkedList( )
LinkedList(Collection<? extends E> c)
The HashSet Class
• HashSet extends AbstractSet class.
• It implements the Set interface.
• It creates a collection that uses a hash table for storage.
• Constructors:

HashSet( )
HashSet(Collection<? extends E> c)
HashSet(int capacity)
• In hashing, the informational content of a key is used to
determine a unique value, called its hash code.
• The hash code is then used as the inde0x at which the data
associated with the key is stored.
• The transformation of the key into its hash code is performed
automatically— you never see the hash code itself.
• Also, your code can’t directly index the hash table.
• The advantage of hashing is that it allows the execution time
of add( ), contains( ), remove( ), and size( ) to remain constant
even for large sets.
The LinkedHashSet Class
• The LinkedHashSet class extends HashSet and adds no members of its
own.
• LinkedHashSet maintains a linked list of the entries in the set, in the
order in which they were inserted.
• That is, when cycling through a LinkedHashSet using an iterator, the
elements will be returned in the order in which they were inserted.
The TreeSet Class
• TreeSet extends AbstractSet and implements the NavigableSet interface.
• It creates a collection that uses a tree for storage.
• Objects are stored in sorted, ascending order.
• Access and retrieval times are quite fast, which makes TreeSet an
excellent choice when storing large amounts of sorted information that
must be found quickly.
• Constructors:
TreeSet( )
TreeSet(Collection<? extends E> c)
TreeSet(Comparator<? super E> comp)
TreeSet(SortedSet<E> ss)
The Map Classes
• Map classes provide implementations of the Map interfaces.

Class Description

AbstractMap Implements most of the Map interface.

HashMap Extends AbstractMap to use a hash table.
TreeMap Extends AbstractMap to use a tree.
LinkedHashMap Extends HashMap to allow insertion-order iterations.
The HashMap Class
• The HashMap class extends AbstractMap and implements the Map
interface.
• It uses a hashtable to store the map. This allows the execution time of
get( ) and put( ) to remain constant even for large sets.

HashMap( )
HashMap(Map<? extends K, ? extends V> m)
HashMap(int capacity)
The TreeMap Class
• The TreeMap class extends AbstractMap and implements the
NavigableMap interface.
• It creates maps stored in a tree structure.
• A TreeMap provides an efficient means of storing key/value pairs in
sorted order and allows rapid retrieval.
• Unlike a hash map, a tree map guarantees that its elements will be
sorted in ascending key order.
TreeMap( )

TreeMap(Comparator<? super K> comp)

TreeMap(Map<? extends K, ? extends V> m)

TreeMap(SortedMap<K, ? extends V> sm)

The LinkedHashMap Class
• LinkedHashMap extends HashMap.
• It maintains a linked list of the entries in the map, in the order in
which they were inserted.
• This allows insertion-order iteration over the map. That is, when
iterating through a collection-view of a LinkedHashMap, the elements
will be returned in the order in which they were inserted.
• You can also create a LinkedHashMap that returns its elements in the
order in which they were last accessed.
Accessing a Collection via an Iterator
• Iterator is used to cycle through the elements in a collection.
• Iterator is an object that implements either the Iterator or
the ListIterator interface.
• Iterator enables you to cycle through a collection,
obtaining or removing elements.
• ListIterator extends Iterator to allow bidirectional
traversal of a list, and the modification of elements.
Method Description

void add(E 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 Returns true if there is a previous element. Otherwise, returns

hasPrevious( ) false.
E next( ) Returns the next element. A NoSuchElementException is thrown if
there is not a next element.
E previous( ) Returns the previous element. A NoSuchElementException is
thrown if there is not a previous element.
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(E obj) Assigns obj to the current element. This is the element last
returned by a call to either next( ) or previous( ).
• Following steps are used to use an iterator to cycle through
the contents of a collection:
• Obtain an iterator to the start of the collection by calling
the collection’s iterator( ) method.
• Set up a loop that makes a call to hasNext( ). Have the
loop iterate as long as hasNext( ) returns true.
• Within the loop, obtain each element by calling next( ).
Comparators
• Both TreeSet and TreeMap store elements in sorted order.
• However, it is the comparator that defines precisely what “sorted order”
means.
• By default, these classes store their elements by using what Java refers to as
“natural ordering,” which is usually the ordering that you would expect (A
before B, 1 before 2, and so forth).
• If you want to order elements a different way, then specify a Comparator
when you construct the set or map.
• Doing so gives you the ability to govern precisely how elements are stored
within sorted collections and maps.
• The Comparator interface defines two methods: compare( ) and equals( ).
compare( )
• compares two elements for order:

int compare(T obj1, T 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.
• The method can throw a ClassCastException if the types of the objects
are not compatible for comparison.
• By overriding compare( ), you can alter the way that objects are ordered.
equals( )
• tests whether an object equals the invoking comparator:

boolean equals(Object obj)

• Here, 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.
Vector
• Vector implements a dynamic array.
• It is similar to ArrayList, but with two differences:
• Vector is synchronized,
• it contains many legacy methods that are not part of the Collections Framework.
• With the advent of collections, Vector was reengineered to extend
AbstractList and to implement the List interface.
• With the release of JDK 5, it was retrofitted for generics and
reengineered to implement Iterable.
• This means that Vector is fully compatible with collections, and a Vector
can have its contents iterated by the enhanced for loop.
Vector constructors:
Vector( )
• creates a default vector, which has an initial size of 10.
Vector(int size)
• creates a vector whose initial capacity is specified by size.
Vector(int size, int incr)
• creates a vector whose initial capacity is specified by size and whose
increment is specified by incr.
• The increment specifies the number of elements to allocate each time
that a vector is resized upward.
Vector(Collection<? extends E> c)
• creates a vector that contains the elements of collection c.
Method Description

void addElement(E element) The object specified by element is added to the vector.

int capacity( ) Returns the capacity of the vector.

Object clone( ) Returns a duplicate of the invoking vector.

boolean contains(Object element) Returns true if element is contained by the vector, and returns
false if it is not.

void copyInto(Object array[ ]) The elements contained in the invoking vector are copied into the
array specified by array.

E elementAt(int index) Returns the element at the location specified by index.

Enumeration<E> elements( ) Returns an enumeration of the elements in the vector.
void ensureCapacity(int size) Sets the minimum capacity of the vector to size.
E firstElement( ) Returns the first element in the vector.

int indexOf(Object element) Returns the index of the first occurrence of element. If the object
is not in the vector, –1 is returned.

int indexOf(Object element, int Returns the index of the first occurrence of element at or after
start. If the object is not in that portion of the vector, –1 is
start) returned.

void insertElementAt(E element,

Adds element to the vector at the location specified by index.
int index)

boolean isEmpty( ) Returns true if the vector is empty, and returns false if it contains
one or more elements.
E lastElement( ) Returns the last element in the vector.

int lastIndexOf(Object element) Returns the index of the last occurrence of element. If the object
is not in the vector, –1 is returned.

int lastIndexOf(Object element, Returns the index of the last occurrence of element before start.
int start) If the object is not in that portion of the vector, –1 is returned.

void removeAllElements( ) Empties the vector. After this method executes, the size of the
vector is zero.

Removes element from the vector. If more than one instance of

boolean removeElement(Object the specified object exists in the vector, then it is the first one
element) that is removed. Returns true if successful and false if the object
is not found.

void removeElementAt(int index) Removes the element at the location specified by index.
void setElementAt(E element,
The location specified by index is assigned element.
int index)

Sets the number of elements in the vector to size. If the new

void setSize(int size) size is less than the old size, elements are lost. If the new size is
larger than the old size, null elements are added.

int size( ) Returns the number of elements currently in the vector.

String toString( ) Returns the string equivalent of the vector.

void trimToSize( ) Sets the vector’s capacity equal to the number of elements that
it currently holds.
Hashtable
• Hashtable was part of the original java.util and is a concrete
implementation of a Dictionary.
• With the advent of collections, Hashtable was reengineered to also
implement the Map interface.
• Thus, Hashtable is now integrated into the Collections Framework.
• It is similar to HashMap, but is synchronized.
• Like HashMap, Hashtable stores key/value pairs in a hash table.
• However, neither keys nor values can be null.
• When using a Hashtable, you specify an object that is used as a key,
and the value that you want linked to that key.
• The key is then hashed, and the resulting hash code is used as the
index at which the value is stored within the table.
• Constructors:

Hashtable( )
• default constructor, creates a hash table.

Hashtable(int size)
• creates a hash table that has an initial size specified by size.
• The default size is 11.
Hashtable(int size, float fillRatio)
• creates a hash table that has an initial size specified by size and a
fill ratio specified by fillRatio.
• This ratio must be between 0.0 and 1.0
• It determines how full the hash table can be before it is resized
upward.
• When the number of elements is greater than the capacity of the
hash table multiplied by its fill ratio, the hash table is expanded.
• If you do not specify a fill ratio, then 0.75 is used

Hashtable(Map<? extends K, ? extends V> m)

• creates a hash table that is initialized with the elements in m.
Method Description
void clear( ) Resets and empties the hash table.

Object clone( ) Returns a duplicate of the invoking object.

boolean contains(Object Returns true if some value equal to value exists within the hash
value) table. Returns false if the value isn’t found.

boolean containsKey(Object Returns true if some key equal to key exists within the hash table.
key) Returns false if the key isn’t found.

boolean containsValue(Object Returns true if some value equal to value exists within the hash
value) table. Returns false if the value isn’t found.
Enumeration<V> elements( ) Returns an enumeration of the values contained in the hash table.

Returns the object that contains the value associated with key.
V get(Object key)
If key is not in the hash table, a null object is returned.

boolean isEmpty( ) Returns true if the hash table is empty; returns false if it contains at
least one key.

Enumeration<K> keys( ) Returns an enumeration of the keys contained in the hash table.

Inserts a key and a value into the hash table. Returns null if key isn’t
V put(K key, V value) already in the hash table; returns the previous value associated with
key if key is already in the hash table.
void rehash( ) Increases the size of the hash table and rehashes all of its keys.

V remove(Object key) Removes key and its value. Returns the value associated with key. If key is
not in the hash table, a null object is returned.

int size( ) Returns the number of entries in the hash table.

String toString( ) Returns the string equivalent of a hash table.

References:
Herbert Schildt, Complete Reference Java (8th edition), Tata
McGraw Hill Edition