Collection Interfaces - Java Collection Diagrams

And when we include maps:

Deque in java

The java.util.Deque interface is a subtype of the java.util.Queue interface. It represents a queue where you can insert and remove elements from both ends of the queue. Thus, "Deque" is short for "Double Ended Queue" and is pronounced "deck", like a deck of cards.

Deque Implementations

Being a Queue subtype all methods in the Queue and Collection interfaces are also available in the Deque interface.

Since Deque is an interface you need to instantiate a concrete implementation of the interface in order to use it. You can choose between the following Deque implementations in the Java Collections API:

• java.util.ArrayDeque (Click on the link to read about it.)
• java.util.LinkedList

LinkedList is a pretty standard Deque / Queue implementation.

Internal Implementation
ArrayDeque stores its elements internally in an array. If the number of elements exceeds the space in the array, a new array is allocated, and all elements moved over. In other words, the ArrayDeque grows as needed, even if it stores its elements in an array.

Possible Usage
Because the double-ended queue supports addition or removal of elements from either end of the data structure, it can be used as a queue (first-in-first-out/FIFO) or as a stack (last-in-first-out/LIFO). J2SE 5 introduced a Queue interface and the Deque interface extends this interface. Note that a Vector-based Stack class has been present since JDK 1.0, but the Javadoc documentation for this class states that Deque should be used instead because it provides better LIFO operation support. Implementations of Deque are typically expected to perform better than Stack as well.

The Deque interface is extended by the concurrency-supporting interface BlockingDeque and is implemented by classes LinkedBlockingDeque (introduced in Java SE 6), LinkedList (available since JDK 1.2, but now implements Deque), and ArrayDeque (introduced in Java SE 6). For this blog entry, I will demonstrate using one Deque instance as a queue and one Deque instance as a stack using ArrayDeque for both. ArrayDeque is not thread-safe and does not allow for elements of the data structure to be null (a recommended but not required condition of Deque implementations and uses).

Operations on Deque
Adding to deque
To add elements to the tail of a Deque you call its add() method. You can also use the addFirst() and addLast() methods, which add elements to the head and tail of the deque.

Deque dequeA = new LinkedList();

dequeA.add     ("element 1"); //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast ("element 3"); //add element at tail

Getting or Peeking the element
You can peek at the element at the head of the queue without taking the element out of the queue. This is done via the element() method. You can also use the getFirst and getLast() methods, which return the first and last element in the Deque. Here is how that looks:

Object firstElement = dequeA.element();
Object firstElement = dequeA.getFirst();
Object lastElement  = dequeA.getLast();

Removing the element
To remove elements from a deque, you call the remove(), removeFirst() and removeLast methods. Here are a few examples:

Object firstElement = dequeA.remove();
Object firstElement = dequeA.removeFirst();
Object lastElement  = dequeA.removeLast();

Iterating over the elements
One method is normal foreach style:

//access via new for-loop
for(Object object : dequeA) {
    String element = (String) object;
}

Another method is via iterator

//access via Iterator
Iterator iterator = dequeA.iterator();
while(iterator.hasNext(){
  String element = (String) iterator.next();
}

Map.Entry interface methods (java)

Each element is a map has a key and value. Each key-value pair is saved in a java.util.Map.Entry object. A set of these map entries can be obtained by calling a map's entrySet() method. Iterating over a map is done by iterating over this set.
Assume in the following table that me is a Map.Entry object.

Result	Method	Description
obj =	me.getKey()	Returns the key from the pair.
obj =	me.getValue(key)	Returns the value from the Map pair.
obj =	me.setValue(val)	This is an optional operation and may not be supported by all Map.Entry objects. Sets the value of the pair, which modifies the Map which it belongs to. Returns the orginal value.

Map interface methods (java)

Here are some of the most useful Map methods. m is a Map, b is a boolean, i is an int, set is a Set, col is a Collection, key is an Object used as the key used to store a value, val is an Object stored as the value associated with the key.

Result	Method	Description
Adding key-value pairs to a map
obj =	m.put(key, val)	Creates mapping from key to val. It returns the previous value (or null) associated with the key.
	m.putAll(map2)	Adds all key-value entries from another map, map2.
Removing key-value pairs from a map
	m.clear()	Removes all elements from a Map
obj =	m.remove(key)	Deletes mapping from key to anything. Returns previous value (or null) associated with the key.
Retrieving information from the map
b =	m.containsKey(key)	Returns true if m contains a key key
b =	m.containsValue(val)	Returns true if m contains val as one of the values
obj =	m.get(key)	Returns value corresponding to key, or null if there is no mapping. If null has been stored as a value, use containsKey to see if there is a mapping.
b =	m.isEmpty()	Returns true if m contains no mappings.
i =	m.size()	Returns number of mappings in m.
Retrieving all keys, values, or key-value pairs (necessary for iteration)
set =	m.entrySet()	Returns set of Map.Entry values for all mappings.
set =	m.keySet()	Returns Set of keys.
col =	m.values()	Returns a Collection view of the values in m.

Array Operations on collections in java

The toArray methods are provided as a bridge between collections and older APIs that expect arrays on input. They allow the contents of a Collection to be translated into an array. The simple form with no arguments creates a new array of Object. The more complex form allows the caller to provide an array or to choose the runtime type of the output array. For example, suppose c is a Collection The following snippet dumps the contents of c into a newly allocated array of Object whose length is identical to the number of elements in c:

Object[] a = c.toArray();

Suppose c is known to contain only strings. The following snippet dumps the contents of c into a newly allocated array of String whose length is identical to the number of elements in c:

String[] a = (String[]) c.toArray(new String[0]);

Bulk Operations on collections in java

The bulk operations perform some operation on an entire Collection in a single shot. They are shorthands in the sense that each of them can be simulated, perhaps less efficiently, using the operations described above.

• containsAll: Returns true if the target Collection contains all of the elements in the specified Collection (c).
• addAll: Adds all of the elements in the specified Collection to the target Collection.
• removeAll: Removes from the target Collection all of its elements that are also contained in the specified Collection.
• retainAll: Removes from the target Collection all of its elements that are not also contained in the specified Collection. That is to say, it retains only those elements in the target Collection that are also contained in the specified Collection.
• clear: Removes all elements from the Collection.

The addAll, removeAll, and retainAll methods all return true if the target Collection was modified in the process of executing the operation. As a simple example of the power of the bulk operations, consider following idiom to remove all instances of a specified element, e from a Collection, c.:

c.removeAll(Collections.singleton(e));

More specifically, suppose that you want to remove all of the null elements from a Collection:

c.removeAll(Collections.singleton(null));

This idiom uses Collections.singleton, which is a static factory method that returns an immutable Set containing only the specified element.

Set & List interface extend Collection, but Map interface don't?

Map is considered part of collection framework, but it does not extend collection interface. The reason behind it is the design.But what design do we follow?

And the answer to this questions is best described in Sun's FAQ Page: This was by design. We feel that mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface (or vice versa). If a Map is a Collection, what are the elements? The only reasonable answer is "Key-value pairs", but this provides a very limited (and not particularly useful) Map abstraction. You can't ask what value a given key maps to, nor can you delete the entry for a given key without knowing what value it maps to.

Collection could be made to extend Map, but this raises the question: what are the keys? There's no really satisfactory answer, and forcing one leads to an unnatural interface. Maps can be viewed as Collections (of keys, values, or pairs), and this fact is reflected in the three "Collection view operations" on Maps (keySet, entrySet, and values). While it is, in principle, possible to view a List as a Map mapping indices to elements, this has the nasty property that deleting an element from the List changes the Key associated with every element before the deleted element. That's why we don't have a map view operation on Lists.

The SortedMap Interface

A SortedMapis a Mapthat maintains its entries in ascending order, sorted according to the keys' natural order, or according to a Comparator provided at SortedMap creation time. (Natural order and Comparators are discussed in the section on Object Ordering.) In addition to the normal Map operations, the Map interface provides operations for:

• Range-view: Performs arbitrary range operations on the sorted map.
• Endpoints: Returns the first or last key in the sorted map.
• Comparator access: Returns the Comparator used to sort the map (if any).

public interface SortedMap extends Map {
    Comparator comparator();
    SortedMap subMap(Object fromKey, Object toKey);
    SortedMap headMap(Object toKey);
    SortedMap tailMap(Object fromKey);
    Object first();
    Object last();
}

This interface is the Map analogue of SortedSet.

 

Map Operations in SortedMap

The operations that SortedMap inherits from Map behave identically on sorted maps and normal maps with two exceptions:

• The Iterator returned by the iterator operation on any the sorted map's Collection-views traverse the collections in order.
  
• The arrays returned by the Collection-views' toArray operations contains the keys, values, or entries in order.

Although it isn't guaranteed by the interface, the toString method of the Collection-views in all the JDK's SortedMap implementations returns a string containing all the elements of the view, in order.

 

Standard Constructors in SortedMap interface

By convention, all Map implementations provide a standard constructor that takes a Map, and SortedMap implementations are no exception. This constructor creates a SortedMap object that orders its entries according to their keys' natural order. Additionally, by convention, SortedMap implementations provide two other standard constructors:

• One that takes a Comparator and returns a new (empty) SortedMap sorted according to the specified Comparator.
  
• One that takes a SortedMap and returns a new SortedMap containing the same mappings as the given SortedMap, and sorted according to the same Comparator (or using the elements' natural ordering, if the specified SortedMap did too). Note that it is the compile-time type of the argument that determines whether this constructor is invoked in preference to the ordinary Map constructor, and not its runtime type!

The first of these standard constructors is the normal way to create an empty SortedMap with an explicit Comparator. The second is similar in spirit to the standard Map constructor: It creates a copy of a SortedMap with the same ordering, but with a programmer specified implementation type.

 

Comparison to SortedSet

Because this interface is a precise Map analogue of SortedSet, all of the idioms and code examples in the SortedSet section apply to SortedSet with only trivial modifications.

The SortedSet interface

A SortedSetis a Setthat maintains its elements in ascending order, sorted according to the elements' natural order, or according to a Comparator provided at SortedSet creation time. (Natural order and Comparators are discussed in the previous section, on Object Ordering.) In addition to the normal Set operations, the Set interface provides operations for:

• Range-view: Performs arbitrary range operations on the sorted set.
• Endpoints: Returns the first or last element in the sorted set.
• Comparator access: Returns the Comparator used to sort the set (if any).

The SortedSet interface is shown below:

public interface SortedSet extends Set {
    // Range-view
    SortedSet subSet(Object fromElement, Object toElement);
    SortedSet headSet(Object toElement);
    SortedSet tailSet(Object fromElement);
    // Endpoints
    Object first();
    Object last();
    // Comparator access
    Comparator comparator();
}

SortedSet Operations 

Standard Constructors 

Range-view Operations on SortedSet

Example – Creating a SortedSet

The Map Interface in java

A Mapis an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. The Map interface is shown below:

public interface Map {
    // Basic Operations
    Object put(Object key, Object value);
    Object get(Object key);
    Object remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();    boolean isEmpty();
    // Bulk Operations
    void putAll(Map t);
    void clear();
    // Collection Views
    public Set keySet();
    public Collection values();
    public Set entrySet();
    // Interface for entrySet elements
    public interface Entry {
        Object getKey();
        Object getValue();
        Object setValue(Object value);
    }
}

The JDK contains two new general-purpose Map implementations. HashMap, which stores its entries in a hash table, is the best-performing implementation. TreeMap, which stores its entries in a red-black tree, guarantees the order of iteration. Also, Hashtablehas been retrofitted to implement Map. For more information on implementations, see the Implementations lesson.

 

Interfaces in collections

The core collection interfaces are the interfaces used to manipulate collections, and to pass them from one method to another. The basic purpose of these interfaces is to allow collections to be manipulated independently of the details of their representation. The core collection interfaces are the heart and soul of the collections framework. When you understand how to use these interfaces, you know most of what there is to know about the framework. The core collections interfaces are shown below:

The core collection interfaces form a hierarchy: a Set is a special kind of Collection, and a SortedSet is a special kind of Set, and so forth. Note also that the hierarchy consists of two distinct trees: a Map is not a true Collection. To keep the number of core collection interfaces managable, the the JDK doesn't provide separate interfaces for each variant of each collection type. (Among the possible variants are immutable, fixed-size, and append-only.) Instead, the modification operations in each interface are designated optional: a given implementation may not support some of these operations. If an unsupported operation is invoked, a collection throws an UnsupportedOperationException . Implementations are responsible for documenting which of the optional operations they support. All of the JDK's general purpose implementations support all of the optional operations.
The four sections that follow teach you how to use each of the four basic core collection interfaces. In particular, they describe the idioms that allow you to use these interfaces effectively.

 

Collection

The Collection interface is the root of the collection hierarchy. A Collection represents a group of objects, known as its elements. Some Collection implementations allow duplicate elements and others do not. Some are ordered and others unordered. The JDK doesn't provide any direct implementations of this interface: It provides implementations of more specific subinterfaces like Set and List. This interface is the least common denominator that all collections implement. Collection is used to pass collections around and manipulate them when maximum generality is desired.

 

Set

A Setis a collection that cannot contain duplicate elements. As you might expect, this interface models the mathematical set abstraction. It is used to represent sets like the cards comprising a poker hand, the courses making up a student's schedule, or the processes running on a machine.

 

List

A Listis an ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List generally has precise control over where in the List each element is inserted. The user can access elements by their integer index (position). If you've used Vector, you're already familiar with the general flavor of List.

 

Map

A Mapis an object that maps keys to values. Maps cannot contain duplicate keys: Each key can map to at most one value. If you've used Hashtable, you're already familiar with the general flavor of Map.
The last two core collection interfaces (SortedSet and SortedMap) are merely sorted versions of Set and Map. In order to understand these interfaces, you have to know how order is maintained among objects. Even if you don't plan to use SortedSet or SortedMap, read the following section if you plan to sort Lists.

 

Object Ordering

There are two ways to order objects: The Comparableinterface provides automatic natural order on classes that implement it, while the Comparatorinterface gives the programmer complete control over object ordering. Note that these are not core collection interfaces, but underlying infrastructure.
Now that you know all about object ordering, here are the last two core collection interfaces:

SortedSet

A SortedSet is a Set that maintains its elements in ascending order. Several additional operations are provided to take advantage of the ordering. The SortedSet interface is used for things like word lists and membership rolls.

 

SortedMap

A SortedMapis a Map that maintains its mappings in ascending key order. It is the Map analogue of SortedSet. The SortedMap interface is used for apps like dictionaries and telephone directories.

List of interface and classes in collections

Covering the interface one by one

• Collection Interface
• Iterator Interface
• Set Interface
• List Interface
• ListIterator Interface
• Map Interface
• SortedSet Interface
• SortedMap Interface

Covering the classes

• HashSet and TreeSet Classes
• ArrayList and LinkList Classes
• HashMap and TreeMap Classes
• Vector and Stack classes

ListIterator interface

ListIterator methods

ListIterator is implemented only by the classes that implement the List interface (ArrayList, LinkedList, and Vector). ListIterator provides the following.

Result	Method	Description
Forward iteration
b =	it.hasNext()	true if there is a next element in the collection.
obj =	it.next()	Returns the next object.
Backward iteration
b =	it.hasPrevious()	true if there is a previous element.
obj =	it.previous()	Returns the previous element.
Getting the index of an element
i =	it.nextIndex()	Returns index of element that would be returned by subsequent call to next().
i =	it.previousIndex()	Returns index of element that would be returned by subsequent call to previous().
Optional modification methods. UnsupportedOperationException thrown if unsupported.
	it.add(obj)	Inserts obj in collection before the next element to be returned by next() and after an element that would be returned by previous().
	it.set()	Replaces the most recent element that was returned by next or previous().
	it.remove()	Removes the most recent element that was returned by next() or previous().

So its of form:

public interface ListIterator extends Iterator {
    boolean hasNext();
    Object next();

    boolean hasPrevious();
    Object previous();

    int nextIndex();
    int previousIndex();

    void remove();          // Optional
    void set(Object o);     // Optional
    void add(Object o);     // Optional
}

The three methods that ListIterator inherits from Iterator (hasNext, next, and remove) are intended to do exactly the same thing in both interfaces. The hasPrevious and previous operations are exact analogues of hasNext and next. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. The previous operation moves the cursor backwards whereas next moves it forwards.

Here's the standard idiom for iterating backwards through a list:

for (ListIterator i=l.listIterator(l.size()); i.hasPrevious(); ) {
    Foo f = (Foo) i.previous();
    ...
}

Note the argument to listIterator in the above idiom. The List interface has two forms of the listIterator method. The form with no arguments returns a ListIterator positioned at the beginning of the list, and the form with an int argument returns a ListIterator positioned at the specified index. The index refers to the element that would be returned by an initial call to next. If the index value of n is used, then the initial call to next would return null, since it would point just past the end of the list. An initial call to previous would return the element whose index was index-1.

In a list of length n, there are n+1 valid values for index, from 0 to n, inclusive. 

Intuitively speaking, the cursor is always between two elements, the one that would be returned by a call to previous and the one that would be returned by a call to next. The n+1 valid index values correspond to the n+1 "gaps" between elements, from the gap before the first element to the gap after the last one. The diagram below shows the five possible cursor positions in a list containing four elements.

Element(0)   Element(1)   Element(2)   Element(3)   
         ^            ^            ^            ^            ^
  Index: 0            1            2            3            4

Calls to next and previous can be intermixed, but you have to be a bit careful. The first call to previous after a sequence of calls to next returns the same element as the last call to next. Similarly, the first call to next after a sequence of calls to previous returns the same element as the last call to previous. This will become obvious if you stare at the foregoing text long enough. If it doesn't, go get yourself a steaming hot mug of Java, and try again.

nextIndex and previousIndex
It should come as no surprise that the nextIndex method returns the index of the element that would be returned by a subsequent call to next, and previousIndex returns the index of the element that would be returned by a subsequent call to previous. These calls are typically used for one of two purposes: To report the position where something was found, or to record the position of the ListIterator so that another ListIterator with identical position can be created.
It should also come as no surprise that the number returned by nextIndex is always one greater than the number returned by previousIndex. This implies the behavior of the two boundary cases: a call to previousIndex when the cursor is before the initial element returns -1, and a call to nextIndex when the cursor is after the final element returns list.size()+1. To make all of this concrete, here's a possible implementation of List.indexOf:

public int indexOf(Object o) {
    for (ListIterator i = listIterator(); i.hasNext(); )
        if (o==null ? i.next()==null : o.equals(i.next()))
            return i.previousIndex();

    return -1; // Object not found
}

Note that the indexOf method returns i.previousIndex() though it is traversing the list in the forward direction. This is because i.nextIndex() would return the index of the element that we are about to examine, and we want to return the index of the element that we just examined. The Iterator interface provides the remove operation to remove from the Collection the last element returned by next. The ListIterator interface provides two additional operations to modify the list: set and add. The set method "overwrites" the last element returned by next or previous with the specified element. It is demonstrated by the following polymorphic algorithm to replace all occurrences of one specified value with another:

public static void replace(List l, Object val, Object newVal) {
    for (ListIterator i = l.listIterator(); i.hasNext(); )
        if (val==null ? i.next()==null : val.equals(i.next()))
            i.set(newVal);
}

The only bit of trickiness in this example is the equality test between val and i.next. We have to special-case an val value of null in order to prevent a NullPointerException. The add method inserts a new element into the list, immediately before the current cursor position. This method is illustrated in the following polymorphic algorithm to replace all occurrences of a specified value with the sequence of values contained in the specified list:

public static void replace(List l, Object val, List newVals) {
    for (ListIterator i = l.listIterator(); i.hasNext(); ) {
        if (val==null ? i.next()==null : val.equals(i.next())) {
            i.remove();
            for (Iterator j = newVals.iterator(); j.hasNext(); )
                i.add(j.next());
        }
    }
}

BAD BAD BAD

Q: What does this loop do? Note mixing of iterator with index.

ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist

int i = 0;
for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
    System.out.println(alist.get(i++));
}

A: It throws an exception when it goes beyond the end.

After hasNext() returns true, the only way to advance the iterator is to call next(). But the element is retrived with get(), so the iterator is never advanced. hasNext() will continue to always be true (ie, there is a first element), and eventually the get() will request something beyond the end of the ArrayList. Use either the iterator scheme.

for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
    System.out.println(it.next());
}

Or the indexing scheme, but don't mix them.

for (int i=0; i < alist.size(); i++) {
    System.out.println(alist.get(i));
}

Set<E> interface

Sets are collections that allow only one object with a given value in them. The java.util.Set interface is a subinterface of Collection. There are two very useful concrete classes that implement the Set interface:

• java.util.HashSet is implemented with a hash table. Access time is O(1). Entries are unsorted.
• java.util.TreeSet is implemented as a balanced binary tree. Access time is O(log N). Entries are sorted.

A set is an unordered collection of elements that has no duplicate members. elements retrieved by identity, not index.

Set Interface

Set Implementations

We have following as implementing classes:

public interface Set {
    // Basic Operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    boolean add(Object element);    // Optional
    boolean remove(Object element); // Optional
    Iterator iterator();

    // Bulk Operations
    boolean containsAll(Collection c);
    boolean addAll(Collection c);    // Optional
    boolean removeAll(Collection c); // Optional
    boolean retainAll(Collection c); // Optional
    void clear();                    // Optional        

    // Array Operations
    Object[] toArray();
    Object[] toArray(Object a[]);
}

Collection Interface

The Collection interface is the parent of the List and Set interfaces, but not Map.
Present in java.util.Collection

Assume the following declaration for identifiers in the table below:

Collection coll; 
boolean b; 
Object obj; 
int i; 
Iterator it;

Returns	Method	Action
Adding objects to a collection
b =	coll.add(obj)	Adds obj to this collection. Returns true if the collection was changed because of the add (eg, it will always be true for adding to a List, but will be false when adding to a Set that already contains this object). It appends new element at the end of the list.
b =	coll.addAll(coll)	Adds all elements of obj to this collection. Returns true if the collection was changed because of the addition. It appends new element at the end of the list.
Removing objects from a collection
	coll.clear()	Removes all elements from the collection.
b =	coll.remove(obj)	Removes the specified item from the list for the first occurrence of obj from this collection. Returns true if the collection was changed because of this operation.
b =	coll.removeAll(coll)	Removes all elements of coll from this collection. Returns true if the collection was changed because of this operation.
b =	coll.retainAll(coll)	Removes all elements of which are not in coll from this collection. Returns true if the collection was changed because of this operation.
Testing for presence in a collection
b =	coll.contains(obj)	Returns true if obj is in this collection.
b =	coll.containsAll(coll)	Returns true if all the members of coll are in this collection.
b =	coll.isEmpty()	Returns true if there are no objects in this collection.
Other
it =	coll.iterator()	Returns an iterator for this collection. The order of elements is only specified if the underlying collection has an ordering (eg, List and TreeSet so, HashSet doesn't).
i =	coll.size()	Returns the number of objects in this collection.
Object[] =	coll.toArray()	Returns an array containing the elements of this collection.
Object[] =	coll.toArray(Object[])	Returns an array containing the elements of this collection.

Iterator Interface

Bulk Operations on collections in java

Array Operations on collections in java