Important Interfaces and Classes of Collections Framework
In the previous section, we mentioned that Java Collections Framework consists of some core interfaces and their implementing class (i.e. concrete classes). The present section describes some of the important interfaces and classes of this framework in brief.
1. List interface
It is an ordered collection that allows duplicate elements. We can easily access and manipulate its elements using their index position. The index value start with 0, just like an array.
Its signature is as follows:
public interface List<E> extends Collection<E>
Some useful classes which implement java.util.List
interface are – ArrayList, LinkedList, Stack, and Vector.
2. Set interface
It is a collection that does not allow duplicate elements. This interface does not provide any guarantee to return the elements in a predictable order; though some implementations of Set store elements in their natural ordering and guarantee the order of their elements.
Its signature is as follows:
public interface Set<E> extends Collection<E>
SortedSet is a sub-interface of the Set interface that preserves its elements in ascending order.
Some useful classes which implement java.util.Set
interface are – HashSet, LinkedHashSet, TreeSet, and EnumSet.
3. Queue interface
It is a collection that contains multiple elements prior to processing. Queues generally process elements in a FIFO (first-in, first-out) manner. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations.
Its signature is as follows:
public interface Queue<E> extends Collection<E>
Deque is a sub-interface of the Queue interface. A deque is a special kind of queue that supports element insertion and removal at both ends, but not in the middle. The name deque is the abbreviated form of “double ended queue” and is usually pronounced “deck”.
Some useful classes which implement java.util.Queue
interface are – ArrayDeque, LinkedList, and PriorityQueue.
4. Map interface
It is a collection that enables us to store data in key-value pairs (keys should be immutable). A map can not allow duplicate keys. Every key in this collection can map to at most one value.
Its signature is as follows:
public interface Map<K,V>
SortedMap is a sub-interface of the Map interface that preserves its mappings in ascending key order.
Some useful classes which implement java.util.Map
interface are – EnumMap, HashMap, Hashtable, LinkedHashMap, Properties, and TreeMap.
The basic operations of Map are put()
, get()
, containsKey()
, containsValue()
, size()
, and isEmpty().
5. ListIterator interface
ListIterator is a type of Iterator (i.e. sub-interface) for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator’s current position in the list. A ListIterator
has no current element; its cursor position always lies between the element that would be returned by a call to previous()
and the element that would be returned by a call to next()
.
Its signature is as follows:
public interface ListIterator<E> extends Iterator<E>
6. HashSet class
It is the basic implementation the Set interface that is backed by a HashMap. It makes no guarantees for iteration order of the set and permits the null element.
Its signature is as follows:
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable
This class offers constant time performance for basic operations [add()
, remove()
, contains()
and size()]
, assuming the hash function disperses the elements properly among the buckets. We can set the initial capacity and load factor for this collection. The load factor is a measure of how full the hash map is allowed to get before its capacity is automatically increased.
7. TreeSet class
It is a NavigableSet
implementation based on a TreeMap
. The elements are ordered using their natural ordering, or by a Comparator
provided at set creation time, depending on which constructor is used.
Its signature is as follows:
public class TreeSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, Serializable
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo() / compare() method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.
8. ArrayList class
ArrayList is the resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. This class is roughly equivalent to Vector, except that it is not synchronized.
Its signature is as follows:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
The size(), isEmpty(), get(), set(), iterator(), and listIterator() methods run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time. The constant factor is low compared to that for the LinkedList implementation.
9. LinkedList class
It is the doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
Its signature is as follows:
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable
All of the operations perform as expected for a doubly-linked list. Operations that index into the list will traverse the list from the start or the end, whichever is closer to the specified index.
10. HashMap class
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations and permits null values and the null key. HashMap class is roughly equivalent to Hashtable, except that it is not synchronized and permits null. This class makes no guarantees for the order of the map.
Its signature is as follows:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
This implementation provides constant-time performance for the basic operations [get()
and put()
]. It provides constructors to set initial capacity and load factor for the collection.
11. TreeMap class
It is a Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
Its signature is as follows:
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable
This implementation provides guaranteed log(n) time cost for the containsKey(), get(), put() and remove() operations.
Note that the ordering maintained by a TreeMap, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo() / compare() method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.
12. PriorityQueue class
Queue processes its elements in FIFO order but sometimes we want elements to be processed based on their priority. We can use PriorityQueue in this case and we need to provide a Comparator implementation while instantiation the PriorityQueue.
Its signature is as follows:
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
PriorityQueue doesn’t allow null values and it’s unbounded.
13. Vector class
The Vector
class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector
can grow or shrink as needed to accommodate adding and removing items after the Vector
has been created.
Its signature is as follows:
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
Each vector tries to optimize storage management by maintaining a capacity()
and a capacityIncrement()
. The capacity
is always at least as large as the vector size; it is usually larger because as components are added to the vector, the vector’s storage increases in chunks the size of capacityIncrement()
. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation.
Vector class is synchronized and thus thread safe unlike ArrayList.
14. Stack class
The Stack
class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push() and pop() operations are provided, as well as a method to peek() at the top item on the stack, a method to test for whether the stack is empty(), and a method to search() the stack for an item and discover how far it is from the top.
Its signature is as follows:
public class Stack<E> extends Vector<E>
15. Collections class
Java Collections class consists of only static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, “wrappers”, which return a new collection backed by a specified collection, and a few other odds and ends. Its signature is as follows:
public class Collections extends Object
This class contains methods for collection framework algorithms, such as binary search, sorting, shuffling, reverse etc.
N.B. One example of using Collections class is given at the bottom while describing Enumeration interface.
♦ Java 8 Collections
Java SE 8 was a major release which introduced lambda expression through functional interfaces in Java. As a result, The Collection Framework classes was also improved. For example, we can iterate over collections in single line and perform an action on all elements of collection using forEach statement. Another thing is that with lambda expressions the way Generics are to be used in Collections also changed. See the example below.
TestCollections.java
import java.util.ArrayList;
public class TestCollections {
public static void main(String[] args) {
//Java SE 8 Style for Generics with Collections using "<>"
ArrayList<E> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
System.out.println("ArrayList elements are: ");
System.out.println("======================");
list.forEach(System.out::println);
}
}
Output:
ArrayList elements are:
================
10
20
30
♦ Useful Interfaces of java.util package
Though these interfaces are not the members of Java Collections Framework directly, they are still used to access the elements of different collection objects.
I) Comparator Interface
This interface provides a comparison function, which imposes a total ordering on some collection of objects.
Its signature is as follows:
public interface Comparator<T>
Here T
is the type of objects that may be compared by this comparator.
Comparators can be passed to a sort method (such as Collections.sort
or Arrays.sort
) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures (such as sorted sets
or sorted maps
), or to provide an ordering for collections of objects that don’t have a natural ordering
.
The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 ande2 in S.
II) Enumeration Interface
It indicates that an object which implements the Enumeration interface generates a series of elements, one at a time. Successive calls to its nextElement()
method return successive elements of the series.
Its signature is as follows:
public interface Enumeration<E>
Here E is the type of collection objects on which the Enumeration enumerates.
It has got two methods and they are namely:
- boolean hasMoreElements() — It tests if this enumeration contains more elements.
- E nextElement() — It returns the next element of this enumeration if this enumeration object has at least one more element to provide.
See the example below for accessing elements of ArrayList object.
EnumerationTester.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Enumeration;
public class EnumerationTester {
public static void main(String args[]) {
// Creating ArrayList objects
ArrayList<String> dayNames = new ArrayList<String>();
dayNames.add("Sunday");
dayNames.add("Monday");
dayNames.add("Tuesday");
dayNames.add("Wednesday");
dayNames.add("Thursday");
dayNames.add("Friday");
dayNames.add("Saturday");
Enumeration days = Collections.enumeration(dayNames);
System.out.println("Days of a week are:~");
System.out.println("====================");
// Enumerating the elements in the ArrayList
while (days.hasMoreElements()) {
System.out.print(days.nextElement() + " ");
}
System.out.println();
}
}
Output:
Days of a week are:~
====================
Sunday Monday Tuesday Wednesday Thursday Friday Saturday
NOTE: The functionality of this interface is duplicated by the Iterator interface. In addition, Iterator adds an optional remove operation, and has shorter method names. New implementations should consider using Iterator in preference to Enumeration.
In the following sections we will discuss about the several important classes of Java Collections Framework.