Java Collections

The Java Collections API provide Java developers with a set of classes and interfaces that makes it
easier to work with collections of objects, e.g. lists, maps, stacks etc.

Rather than having to write your own collection classes, Java provides these ready-to-use collection
classes for you. This tutorial will look closer at the Java Collections, as they are also sometimes
referred to, and more specifically the Java Collections available in Java 8 and later.

 The Java Collections Framework

 Java arrays have limitations.
o They cannot dynamically shrink and grow.
o They have limited type safety.
o Implementing efficient, complex data structures from scratch would be difficult.
 The Java Collections Framework is a set of classes and interfaces implementing complex
collection data structures.
o A collection is an object that represents a group of objects.
 The Java Collections Framework provides many benefits:
o Reduces programming effort (already there)
o Increases performance (tested and optimized)
o Part of the core API (available, easy to learn)
o Promotes software reuse (standard interface)
o Easy to design APIs based on generic collections
13.2. The Collection Interface
 java.util.Collection is the root interface in the collections hierarchy.
o It represents a group of Objects.
 The Collection interface includes a variety of methods:
o Adding objects to the collection: add(E), addAll(Collection)
o Testing size and
membership: size(), isEmpty(), contains(E), containsAll(Collection)
o Iterating over members: iterator()
o Removing
members: remove(E), removeAll(Collection), clear(), retainAll(Colle
ction)
o Generating array representations: toArray(), toArray(T[])

The Collection interface does not say anything about:

 the order of elements

 whether they can be duplicated
 whether they can be null
 the types of elements they can contain

13.3. Iterating Over a Collection

 An iterator is an object that iterates over the objects in a collection.

 java.util.Iterator is an interface specifying the capabilities of an iterator.

o Invoking the iterator() method on a collection returns an iterator object that
implements Iterator and knows how to step through the objects in the underlying
collection.
 The Iterator interface specifies the following methods:
o hasNext() - Returns true if there are more elements in the
collection; false otherwise
o next() - Returns the next element
o remove() - Removes from the collection the last element returned by the iterator

For example, to print all elements in a collection:

private static void print(Collection c) {

Iterator i = c.iterator();
while (i.hasNext()) {
Object o = i.next();
System.out.println(o);
}
}

This can also be written as:

private static void print(Collection c) {

for (Iterator i = c.iterator(); i.hasNext(); ) {
System.out.println(i.next());
}
}

And in Java 5, the Iterator can be used implicitly thanks to for-each:

private static void print(Collection c) {

for (Object o : c) {
System.out.println(o);
}
}

The List Interface

 The java.util.List Interface extends the Collection interface.
 The List interface declares methods for managing an ordered collection of object
(a sequence). You can:
o Control where each element is inserted in the list
o Access elements by their integer index (position in the list)
o Search for elements in the list
o Insert duplicate elements and null values, in most List implementations

Tip
Especially if you’re dynamically resizing a collection of object, favor using a List over a
Java array.
 Some additional methods provided by List include:
o add(int index, E element) — Insert an element at a specific location (without
an index argument, new elements are appended to the end)
o get(int index) — Return an element at the specified location
o remove(int index) — Remove an element at the specified location
o set(int index, E element) — Replace the element at the specified location
o subList(int fromIndex, int toIndex) — Returns as a List a modifiable
view of the specified portion of the list (that is, changes to the view actually affect the
underlying list)
Classes Implementing List
 Java provides several classes that implement the List interface.
 Two are used most commonly:
java.util.ArrayList
An ArrayList is usually your best bet for a List if the values remain fairly static once you’ve
created the list. It’s more efficient than a LinkedList for random access.
java.util.LinkedList
A LinkedList provides better performance than an ArrayList if you’re frequently inserting and
deleting elements, especially from the middle of the collection. But it’s slower than an
ArrayList for random-access.
In the following example, notice the use of the java.util.Collections.sort() static method,
which does an in-place sort of the elements in a List:

The Set and SortedSet Interfaces

 The java.util.Set Interface extends the Collection interface.
 The Set interface declares methods for managing a collection of objects that contain no
duplicates.
o The basic Set interface makes no guarantee of the order of elements.
o A Set can contain at most one null element.
o Mutable elements should not be changed while in a Set.
 The Set interface adds no methods beyond those of the Collection interface.
o The Set interface simply enforces behavior of the collection.
 The java.util.SortedSet interface extends Set so that elements are automatically
ordered.
o A SortedSet Iterator traverses the Set in order.
o A SortedSet also adds the methods first(), last(), headSet(), tailSet(),
and subSet()

Classes Implementing Set

Java provides several classes that implement the Set interface, including:

java.util.HashSet:: A hash table implementation of the Set interface. The best all-around
implementation of the Set interface, providing fast lookup and updates.
java.util.LinkedHashSet
A hash table and linked list implementation of the Set interface. It maintains the insertion
order of elements for iteration, and runs nearly as fast as a HashSet.
java.util.TreeSet
A red-black tree implementation of the SortedSet interface, maintaining the collection in
sorted order, but slower for lookups and updates.
The Queue Interface
 The java.util.Queue interface is a collection designed for holding elements prior to
processing.
o Besides basic Collection operations, queues provide additional insertion, extraction,
and inspection operations.
o Queues can implement FIFO (queue), LIFO (stack), and priority ordering.
o Queues generally do not accept null elements.
 Queue operations include:
o Inserting elements: add() and offer()
o Removing and returning elements: remove() and poll()
o Returning elements without removal: element() and peek()
 The java.util.concurrent.BlockingQueue interfaces declare additional
blocking put() and take() methods, designed for concurrent access by multiple threads.

General-purpose Queue implementations:

 java.util.LinkedList
 java.util.PriorityQueue

13.9. The Map Interface

 The java.util.Map interface does not extend the Collection interface!
 A Map is a collection that maps key objects to value objects.
o A Map cannot contain duplicate keys
o Each key can map to at most one value.
 The Map interface methods include:
o Adding key-value pairs to the collection: put(K, V), putAll(Map)
o Retrieving a value by its key: get(K)
o Testing size: size(), isEmpty()
o Testing membership: containsKey(K), containsValue(V)
o Removing members: remove(K), clear()
 The java.util.SortedMap interface extends Map so that elements are automatically
ordered by key.
o Iterating over a SortedMap iterates over the elements in key order.
o A SortedMap also adds the
methods firstKey(), lastKey(), headMap(), tailMap(), and subMap()

13.10. Retrieving Map Views

 You can also retrieve collections as modifiable views from the Map representing the keys
(keySet()), the values (values()), and a Set of key-value pairs (entrySet()).
o These collections are used typically to iterate over the Map elements.
 o These collections are backed by the Map, so changes to the Map are reflected in the
collection views and vice-versa.
 Iterating over Map elements is done typically with a Set of objects implementing
the java.util.Map.Entry interface.
o You retrieve the Set of Map.Entry objects by invoking Map.entrySet().
o To iterate over the Map elements using an explicit Iterator:

for (Iterator i = map.entrySet().iterator; i.hasNext(); )

{
Map.Entry entry = (Map.Entry) i.next();
System.out.println( entry.getKey() + ":\t" + entry.getValue() );
}

To iterate over the Map elements using the for-each syntax:

for ( Map.Entry entry: map.entrySet() )

{
System.out.println(entry.getKey() + ":\t" + entry.getValue());
}

Classes Implementing Map

Java provides several classes that implement the Map interface, including:

java.util.HashMap:: A hash table implementation of the Map interface. The best all-around
implementation of the Map interface, providing fast lookup and updates.
java.util.LinkedHashMap
A hash table and linked list implementation of the Map interface. It maintains the insertion
order of elements for iteration, and runs nearly as fast as a HashMap.
java.util.TreeMap
A red-black tree implementation of the SortedMap interface, maintaining the collection in
sorted order, but slower for lookups and updates.

The Collections Class

 The java.util.Collections class (note the final "s" ) consists exclusively of static
methods that operate on or return collections. Features include:
o Taking a collection and returning an unmodifiable view of the collection
o Taking a collection and returning a synchronized view of the collection for thread-
safe use
o Returning the minimum or maximum element from a collection
o Sorting, reversing, rotating, and randomly shuffling List elements
  Several methods of the Collections class require objects in the collection to be comparable.
o The object class must implement the java.lang.Comparable interface.
o The object class must provide an implementation of the compareTo() method,
which a negative integer, zero, or a positive integer as this object is less than, equal
to, or greater than the specified object.

Type Safety in Java Collections

 The Java Collections Framework was designed to handle objects of any type.
o In Java 1.4 and earlier they used Object as the type for any object added to the
collection.
o You had to explicitly cast the objects to the desired type when you used them or else
you would get compile-time errors.

Employee e = (Employee) list.get(0);

o Worse yet, if you were dealing with a collection of objects, say of type Dog, and then
accidentally added an object of an incompatible type, say a Cat, your code could
eventually try to cast the object to the incompatible type, resulting in a runtime
exception.

Java Generics
 Java Generics, introduced in Java 5, provide stronger type safety.
 Generics allow types to be passed as parameters to class, interface, and method
declarations. For example:

List<Employee> emps = new ArrayList<Employee>();

Java List Basic List operations: adding, retrieving, updating,

removing elements Collection Examples

The following is a quick example of creating a new ArrayList and LinkedList which hold String

objects; add some elements to them; and then print out the collections:

ArrayList  quick example:

List<String> listStrings = new ArrayList<String>();

listStrings.add("One");
 listStrings.add("Two");

listStrings.add("Three");

listStrings.add("Four");

System.out.println(listStrings);

 LinkedList  quick example:

List<String> listStrings = new LinkedList<String>();

listStrings.add("Five");

listStrings.add("Six");

listStrings.add("Seven");

listStrings.add("Eight");

System.out.println(listStrings);

The code examples in above revolve on the two common .

Creating a new list

It’s a good practice to declare a list instance with a generic type parameter, for example:

List<Object> listAnything = new ArrayList<Object>();

List<String> listWords = new ArrayList<String>();

List<Integer> listNumbers = new ArrayList<Integer>();

List<String> linkedWords = new LinkedList<String>();

Since Java 7, we can remove the type parameter on the right side as follows:

List<Integer> listNumbers = new ArrayList<>();

List<String> linkedWords = new LinkedList<>();

When creating a new ArrayList using the empty constructor, the list is constructed with an initial
capacity of ten. If you are sure how many elements will be added to the list, it’s recommended to
specify a capacity which is large enough. Let’s say, if we know that a list contains around 1000
elements, declare the list as follows:
List<Integer> listNumbers = new ArrayList<>(1000);

It’s also possible to construct a list that takes elements from an existing collection, for example:

List<Integer> listNumberOne;  // existing collection

List<Integer> listNumberTwo = new ArrayList<>(listNumberOne);

The listNumberTwo constructed with copies of all elements from the listNumberOne.

Adding elements to a List:

The methods add(Object), add(index, Object) and addAll() are used to add elements to the list. It
requires to add elements of the same type (or sub type) as the type parameter declared by the list.
For example:

List<String> listStrings = new ArrayList<String>();

// OK to add Strings:

listStrings.add("One");

listStrings.add("Two");

listStrings.add("Three");

// But this will cause compile error

listStrings.add(123);

Adding elements of sub types of the declared type:

List<Number> linkedNumbers = new LinkedList<>();

linkedNumbers.add(new Integer(123));

linkedNumbers.add(new Float(3.1415));

linkedNumbers.add(new Double(299.988));

linkedNumbers.add(new Long(67000));

We can insert an element into the list at a specified index, for example:
listStrings.add(1, "Four");

That inserts the String “Four” at the 2nd position in the list.

We can also add all elements of an existing collection to the end of the list:
listStrings.addAll(listWords);

Or add the elements to the list at a specified position:

listStrings.addAll(2, listWords);

That inserts all elements of the listWords collection at 3rd position of the listStrings collection.

Retrieving elements from a List

The get() method is used to retrieve an element from the list at a specified index. For example, the
following code gets an element at 2nd position in the array list and an element at 4th position in the
linked list:

String element = listStrings.get(1);

Number number = linkedNumbers.get(3);

For a LinkedList implementation, we can get the first and the last elements like this:

LinkedList<Number> numbers = new LinkedList<Number>();

// add elements to the list...

// get the first and the last elements:

Number first = numbers.getFirst();

Number last = numbers.getLast();

Note that the getFirst() and getLast() methods are specific to the LinkedList class.

Updating elements in a List

Use the set(index, element) method to replace the element at the specified index by the specified
element. For example:
listStrings.set(2, "Hi");

That replaces the 3rd element in the list by the new String “Hi”.

Removing elements from a List

To remove an element from the list, use the remove(index) or remove(Object) method which
removes the element at the specified index or by object reference. For example:

o Remove the element at the 3rd position in the list:

listStrings.remove(2);

o If the specified index is out of range (index < 0 or index >= list size),
a java.lang.IndexOutOfBoundsException is thrown.
o Remove the String element “Two” in the list:

listStrings.remove("Two");

Notes about the remove(Object) method:
 o It compares the specified object with the elements in the list using their equals() method,
so if you use your own defined object type, make sure it implements the equals() method
correctly.
o It only removes the first occurrence of the specified element in the list (i.e. if a list contains
duplicate elements, only the first element is removed).
o It returns true if the list contained the specified element, or falseotherwise. Thus it’s
recommended to check return value of this method, for example:

if (listStrings.remove("Ten")) {

    System.out.println("Removed");

} else {

    System.out.println("There is no such element");

To remove all elements in the list, use the clear() method:

listStrings.clear();

Iterating over elements in a list

Basically, we can use the enhanced for loop to iterate through all elements in the list, as follows:
for (String element : listStrings) {

    System.out.println(element);

Or use an iterator like this:

Iterator<String> iterator = listStrings.iterator();

while (iterator.hasNext()) {

    System.out.println(iterator.next());

For more list-specific, use a list iterator as shown below:

Iterator<Number> iterator = linkedNumbers.listIterator();

while (iterator.hasNext()) {

    System.out.println(iterator.next());

Since Java 8, we can use the forEach()method like this: 

listStrings.forEach(s -> System.out.println(s));
Searching for an element in a list
To search for position of a specific element in the list or to know if the list contains the specified
element, the following methods can be used:

o boolean contains(Object): returns trueif the list contains the specified element.

o int indexOf(Object): returns the index of the first occurrence of the specified element in the
list, or -1 if the element is not found.
o int lastIndexOf(Object): returns the index of the last occurrence of the specified element in
the list, or -1 if the element is not found.

if (listStrings.contains("Hello")) {

    System.out.println("Found the element");

} else {

    System.out.println("There is no such element");

int firstIndex = linkedNumbers.indexOf(1234);

int lastIndex = listStrings.indexOf("Hello");

Note that the above methods compare the elements using their equals() method, so if you define
your own type, make sure it implements the equals() method correctly.

Sorting a list
Before Java 8, the simplest way to sort out elements in a list is using the Collections.sort() static
method which sorts the specified list into ascending order, based on the natural ordering of its
elements. Here’s an example:
List<String> listStrings = new ArrayList<String>();

listStrings.add("D");

listStrings.add("C");

listStrings.add("E");

listStrings.add("A");

listStrings.add("B");

System.out.println("listStrings before sorting: " + listStrings);

Collections.sort(listStrings);

System.out.println("listStrings after sorting: " + listStrings);

Output:
listStrings before sorting: [D, C, E, A, B]

listStrings after sorting: [A, B, C, D, E]

Note that all elements in the list must implement the Comparableinterface, so if you define your own
type, make sure it implements that interface and its compareTo() method.

Since Java 8, the List interface introduces the sort() method, so you can sort elements in
an ArrayList or LinnkedList directly like this:

listStrings.sort(null); // sort by natural ordering of the elements

For more details and examples, see the article: Sorting List Collections Examples

Copying elements from one list into another

The Collections.copyList(dest, src) static method allows us to copy all elements from the source list
into the destination one. Note that the destination list must be large enough to contain the entire
source list. Here’s an example:

List<String> sourceList = new ArrayList<String>();

sourceList.add("A");

sourceList.add("B");

sourceList.add("C");

sourceList.add("D");

List<String> destList = new ArrayList<String>();

destList.add("V");

destList.add("W");

destList.add("X");

destList.add("Y");

destList.add("Z");

System.out.println("destList before copy: " + destList);

Collections.copy(destList, sourceList);

System.out.println("destList after copy: " + destList);

The output would be:

destList before copy: [V, W, X, Y, Z]
 destList after copy: [A, B, C, D, Z]

Shuffling elements in a list

To randomly permute elements in a list, use the Collections.shuffle() static method. Here’s a quick
example:
List<Integer> numbers = new ArrayList<Integer>();

for (int i = 0; i <= 10; i++)

numbers.add(i);

System.out.println("List before shuffling: " + numbers);

Collections.shuffle(numbers);

System.out.println("List after shuffling: " + numbers);

The output would be:

List before shuffling: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

List after shuffling: [6, 4, 5, 0, 1, 3, 9, 7, 2, 10, 8]

 
Reversing elements in a list
To reverse order of elements in a list, use the Collections.reverse() static method. Here’s a quick
example:
List<Integer> numbers = new ArrayList<Integer>();

for (int i = 0; i <= 10; i++) numbers.add(i);

System.out.println("List before reversing: " + numbers);

Collections.reverse(numbers);

System.out.println("List after reversing: " + numbers);

The output would be:

List before reversing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

List after reversing: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

 
Extracting a portion of a list
The subList(fromIndex, toIndex) allows us to get a portion of the list between the
specified fromIndex(inclusive) and toIndex(exclusive). Here’s an example:
 List<String> listNames = Arrays.asList("Tom", "John", "Mary", "Peter", "David", "Alice"

System.out.println("Original list: " + listNames);

List<String> subList = listNames.subList(2, 5);

System.out.println("Sub list: " + subList);

Output:

Original list: [Tom, John, Mary, Peter, David, Alice]

Sub list: [Mary, Peter, David]

Note that the sub list is just a view of the original list, so any modifications made on the original list
will reflect in the sub list.

Converting between Lists and arrays

The Java Collection Framework allows us to easily convert between lists and arrays.

The Arrays.asList(T… a) method converts an array of type T to a list of type T. Here’s an example:

List<String> listNames = Arrays.asList("John", "Peter", "Tom", "Mary", "David", "Sam");

List<Integer> listNumbers = Arrays.asList(1, 3, 5, 7, 9, 2, 4, 6, 8);

System.out.println(listNames);

System.out.println(listNumbers);

Output:

[John, Peter, Tom, Mary, David, Sam]

[1, 3, 5, 7, 9, 2, 4, 6, 8]

And the Listinterface provides the toArray() method that returns an array of Objects containing all of
the elements in the list in proper sequence (from first to last element). Here’s an example:

List<String> listWords = new ArrayList<String>();

// add elements to the list

Object[] arrayWords = listWords.toArray();

And the toArray(T[] a) method returns an array of type T, for example:

String[] words = listWords.toArray(new String[0]);

Integer[] numbers = listNumbers.toArray(new Integer[0]);

Note that the returned array contains copies of elements in the list, which that means we can safely
modify the array without affecting the list.