Which of the following methods is / are available in collections class?

Introduction to the Collection Framework

Although we can use an array as a container to store a group of elements of the same type (primitives or objects). The array, however, does not support so-called dynamic allocation - it has a fixed length which cannot be changed once allocated. Furthermore, array is a simple linear structure. Many applications may require more complex data structure such as linked list, stack, hash table, set, or tree.

In Java, dynamically allocated data structures (such as ArrayList, LinkedList, Vector, Stack, HashSet, HashMap, Hashtable) are supported in a unified architecture called the Collection Framework, which mandates the common behaviors of all the classes.

A collection, as its name implied, is simply a container object that holds a collection of objects. Each item in a collection is called an element. A framework, by definition, is a set of interfaces that force you to adopt some design practices. A well-designed framework can improve your productivity and provide ease of maintenance.

The collection framework provides a unified interface to store, retrieve and manipulate the elements of a collection, regardless of the underlying actual implementation. This allows the programmers to program at the interface specification, instead of the actual implementation.

The Java Collection Framework package (java.util) contains:

  1. A set of interfaces,
  2. Implementation classes, and
  3. Algorithms (such as sorting and searching).

Similar Collection Framework is the C++ Standard Template Library (STL).

Prior to JDK 1.2, Java's data structures consist of array, Vector, and Hashtable that were designed in a non-unified way with inconsistent public interfaces. JDK 1.2 introduced the unified collection framework, and retrofits the legacy classes (Vector and Hashtable) to conform to this unified collection framework.

JDK 5 introduced Generics (which supports passing of types), and many related features (such as auto-boxing/auto-unboxing and for-each loop). The collection framework is retrofitted to support generics and takes full advantages of these new features.

To understand this chapter, you have to be familiar with:

  • Interfaces, abstract methods and their implementations.
  • Inheritance and Polymorphism, especially the upcasting and downcasting operations. See "Inheritance, Substitution, Polymorphism and Type Casting" for a quick summary.

You also need to be familar with these concepts introduced in JDK 5:

  • Auto-Boxing and Auto-Unboxing between primitive types and their wrapper classes. See "Auto-Boxing and Auto-Unboxing".
  • The enhance fo-each loop. See "Enhanced for-each Loop".
  • Generics. See "Generics".

You need to refer to the JDK API specification while reading this chapter. The classes and interfaces for the Collection Framework are kept in package java.util.

Generic Collection Framework (JDK 5) by Examples

Example 1: List<String> (List of Strings) Implemented by ArrayList

The java.util.List<E> interface is the most commonly used data structure of the Collection Framework, which models a resizable (dynamically-allocated) array supporting numerical index access. The java.util.ArrayList<E> class is the most commonly used implementation of List<E>.

The <E> indicates that the interfaces are generic in design. When you construct an instance of these generic types, you need to provide the specific type of the objects contained in these collection, e.g., <String>, <Integer>. This allows the compiler to perform type-checking when elements are added into the collection at compile-time to ensure type-safety at runtime.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;


public class J5ListOfStringTest {
   public static void main(String[] args) {
       
      
      List<String> coffeeLst = new ArrayList<>();
         
         
      coffeeLst.add("espresso");
      coffeeLst.add("latte");
      coffeeLst.add("cappuccino");
      System.out.println(coffeeLst);  

      
      Iterator<String> iter = coffeeLst.iterator();
      while (iter.hasNext()) {
         String str = iter.next();
         System.out.println(str);
      }
      
      
      

      
      for (String str : coffeeLst) System.out.println(str.toUpperCase());
      
      
      

      
      for (int i = 0; i < coffeeLst.size(); ++i) {
         System.out.println(coffeeLst.get(i).substring(0, 3));
      }
      
      
      

      
      
      
      
      
   }
}
Dissecting the Program
  • Line 1-3 imports the collection framework classes and interfaces reside in the java.util package.
  • Which of the following methods is / are available in collections class?
  • The class hierarchy of the ArrayList<E> is shown above. We observe that ArrayList<E> implements List<E>, Collection<E> and Iterable<E> interfaces. The Collection<E> and Iterable<E> interfaces define the common behaviors of all the collection implementations.
  • The interfaces/classes are designed (by the class designer) to take a generics type E. To construct an instance of an ArrayList<E>, we need to provide the actual type for generic type E. In this example, we pass the actual type String for the generic type E.
  • In line 11, we construct an ArrayList<String> instance, and upcast it to the List<String> interface. This is possible as the ArrayList<String> is a subtype of List<String>. Remember that a good program operates on the specifications instead of an actual implementation. The Collection Framework provides a set of interfaces so that you can program on these interfaces instead of the actual implementation.
  • JDK 7 supports type inference on instantiation to simplify the codes:
    List<String> coffeeLst = new ArrayList<String>();
    
    
    List<String> coffeeLst = new ArrayList<>();
    
  • Interface Collection defines how to add and remove an element into the collection. Interface Iterable defines a mechanism to iterate or traverse through all the elements of a collection.
  • The super-interface Collection<E> interface defines the common behaviors expected from a Collection<E> object (such as getting the size, adding and removing element). Instead of using the interface Collection<E> directly, it is more common to use one of its specialized sub-interfaces: List (an ordered list supporting numerical indexed access), Set (models mathematical set with no duplicate elements) or Queue (FIFO, priority queues).
    The super-interface Collection<E> declares these abstract methods, implemented in concrete class ArrayList<E>:
    Collection<E>
    abstract int size()                       
    abstract boolean isEmpty()                
    abstract boolean add(E element)           
    abstract boolean remove(Object element)   abstract boolean contains(Object element) 
    ......
    Line 14-16 adds elements (of the instantiated actual type String) to the Collection.
  • There are a few ways of traversing through the elements of a Collection:
    1. Via an associated Iterator<E> (Lines 20-24)
    2. Use the new for-each loop introduced in JDK 5 (Line 30)
    3. Use aggregate operations on Stream introduced in JDK 8. See "Example 4".
  • The super-interface Iterable<E> defines a mechanism to iterate (or traverse) through all the elements of a Collection<E> object via a so-called Iterator<E> object. The Iterable<E> interface declares one abstract method to retrieve the Iterator<E> object associated with the Collection<E>.
    abstract Iterator<E> iterator();
       
    
  • The Iterator<E> interface declares the following abstract methods for traversing through the Collection<E>.
    abstract boolean hasNext()  
    abstract E next()           
    
    Lines 20-24 retrieve the Iterator<String> associated with this ArrayList<String>, and use a while-loop to iterate through all the elements of this ArrayList<String>. Take note that you need to specify the actual type.
  • Line 30 uses the new for-each loop introduced in JDK 5 to iterate through all the elements of a Collection.
  • List supports numerical index access via .get(index) method, with index begins from 0, shown in Lines 36-38.
  • With the use of generics, the compiler checks the type of elements added or retrieved and issue compilation error "incompatible type", as shown in lines 44-47. This is known as compiled-time type-safe.

Example 2: List<Integer> with Auto-Boxing/Auto-Unboxing

Collection can hold only objects, not primitives (such as int, double). JDK 5 introduces auto-boxing/auto-unboxing to simplify the conversion between primitives and their wrapper classes (such as int/Integer, double/Double, etc.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.List;
import java.util.ArrayList;


public class J5ListOfPrimitivesTest {
   public static void main(String[] args) {
      
      
      List<Integer> numLst = new ArrayList<>();  
      numLst.add(111);  
      numLst.add(222);
      System.out.println(numLst);    
      int firstNum = numLst.get(0);  
      System.out.println(firstNum);  

      
   }
}
Dissecting the Program
  • In this example, we pass actual type Integer for the generic type E. In Line 9, we construct an ArrayList<Integer> and upcast to List<Integer>.
  • In lines 10-11, we pass int value into the .add(). The int value is auto-boxed into an Integer object, and added into the List<Integer>.
  • In line 13, the .get() returns an Integer object, which is auto-unboxed to an int value.

Example 3: Set<E> Implemented by HashSet

This example shows how to create a Collection of an user-defined objects.

The Set<E> interface models an unordered mathematical set without duplicate elements. HashSet<E> is the most common implementation of Set<E>.

We define a Person class with two private variables name and age, as follows:

Person.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Person {
   private String name;  
   private int age;

   public Person(String name, int age) {  
      this.name = name; this.age = age;
   }
   public String getName() {  
      return name;
   }
   public int getAge() {  
      return age;
   }
   public String toString() {  
      return name + "(" + age + ")";
   }

   public void sayHello() {  
      System.out.println(name + " says hello");
   }

   
   @Override
   public boolean equals(Object o) {
      return o != null && o instanceof Person && this.name.equalsIgnoreCase(((Person)o).name);
} @Override public int hashCode() { return this.name.toLowerCase().hashCode(); } }

We shall test a Set<Person> is follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Set;
import java.util.HashSet;


public class J5SetOfPersonTest {
   public static void main(String[] args) {
      Set<Person> personSet = new HashSet<>();
      personSet.add(new Person("Peter", 21));
      personSet.add(new Person("Paul", 18));
      personSet.add(new Person("John", 60));
      System.out.println(personSet);  
         

      for (Person p : personSet) p.sayHello();
      
      
      

      
      System.out.println(personSet.add(new Person("Peter", 21)));  
   }
}
Dissecting the Program
  • We define our custom objects called Person in "Person.java".
  • In this example, we pass actual type Person for the generic type E. In Line 7, we construct an instance of HashSet<Person>, and upcast to Set<Person>.
  • Take note that the elements in a Set are not ordered, as shown in the output of Line 11.
  • A Set does not duplicate elements, as shown in the output of Line 20. To compare two Peson objects, we override the .equal() and .hashCode() methods in "Person.java".

Example 4: JDK 8 Collection, Stream and Functional Programming (Preview)

JDK 8 greatly enhances the Collection Framework with the introduction of Stream API to support functional programming.

Person.java: See above

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.List;
import java.util.function.Predicate;
import java.util.stream.Collectors;


public class J8StreamOfPersonTest {
   public static void main(String[] args) {
      List<Person> personLst = List.of(  
         new Person("Peter", 21),
         new Person("Paul", 18),
         new Person("John", 60)
      );
      System.out.println(personLst);  

      
      Predicate<Person> adult = p -> p.getAge() >= 21;

      
      personLst
         .stream()
         .filter(adult)
         .forEach(Person::sayHello);
      
      

      
      personLst
         .parallelStream()
         .forEach(p -> System.out.println(p.getName()));
      

      
      double aveAgeAdults = personLst
         .stream()
         .filter(adult)
         .mapToInt(Person::getAge)
         .average()
         .getAsDouble();
      System.out.println(aveAgeAdults);
      

      
      int sumAges = personLst
         .stream()
         .collect(Collectors.summingInt(Person::getAge));
      System.out.println(sumAges);
      

      
      List<String> nameStartWithP = personLst
         .stream()
         .filter(p -> p.getName().charAt(0) == 'P')
         .map(Person::getName)
         .collect(Collectors.toList());
      System.out.println(nameStartWithP);
      
   }
}

This article focuses on JDK 5 Collection Framework. Read "Lambda Expressions, Streams and Functional Programming" and "Collection Framework, Part 2" for details on JDK 8 enhancements.

Pre-JDK 5 vs. JDK 5 Collection Framework

JDK 5 introduces Generics to support parameterized type and retrofitted the Collection Framework. To understand the differences between Pre-JDK 5 and JDK 5 Collection Framework, read "Generics".

The Collection Interfaces

The hierarchy of the interfaces and the commonly-used implementation classes in the Collection Framework is as shown below:

Which of the following methods is / are available in collections class?

  • The base interface is Collection<E> (which is a subtype of Iterable<E>), that defines the common behaviors.
  • We hardly program at the Collection<E>, but one of its specialized subtypes. The commonly-used subtypes of are List<E> (ordered elements supporting index access), Set<E> (unordered and non-duplicate) and Queue<E> (FIFO and priority queues).
  • The popular implementation classes for List<E> are ArrayList<E> and LinkedList<E>; for Set are HashSet<E> and TreeSet<E>; for Quene is PriorityQueue<E>.
  • The Iterator<E> is used to traverse (or iterate) through each element of a Collection<E>.
  • Map<K,V> (or associative array), which supports key-value pair, is NOT a subtype of Collection<E>. The popular implementation class is HashMap<K,V>.
  • The Collections (like Arrays) is a utility class, which contains static methods to support algorihtms like searching and sorting.

Iterable<E>/Iterator<E> Interfaces and for-each Loop

There are three ways to traverse through all the elements of a Collection:

  1. Via the associated Iterator<E> object retrieved from the super-type Iterable<E>
  2. Using the for-each loop (introduced in JDK 5)
  3. Via the Stream API (introduced in JDK 8) (to be discussed in "Collection Framework, Part 2")
The Iterable<E> Interface

The java.lang.Iterable<E> interface, which takes a generic type <E> and read as Iterable of elements of type E, declares one abstract method called iterator() to retrieve the Iterator<E> object associated with the Collection<E> object. This Iterator<E> object can then be used to traverse through all the elements of the associated collection.

abstract Iterator<E> iterator();

All implementations of the Collection (e.g., ArrayList, LinkedList, Vector) must implement this method, which returns an object that implements Iterator interface, for traversal of the Collection.

The Iterator<E> Interface

The Iterator<E> interface, declares the following three abstract methods:

abstract boolean hasNext()  
abstract E next()           
abstract void remove()      

You can use a while-loop to iterate through the elements with the Iterator as follows:

List<String> lst = new ArrayList<>();   
lst.add("alpha");
lst.add("beta");
lst.add("charlie");
 

Iterator<String> iter = lst.iterator();

while (iter.hasNext()) {
   
   String str = iter.next();
   System.out.println(str);
}


for (str: lst) System.out.println(str);
The for-each Loop

JDK 5 introduces a new for-each loop to simplify traversal of a Collection, as shown in the above code.

for-each Loop vs. Iterator

The for-loop provides a convenience way to traverse through a collection of elements. But it hides the Iterator, hence, you CANNOT remove (via Iterator.remove()) or replace the elements.

On the other hand, as the loop variable receives a "cloned" copy of the object reference, the enhanced for-loop can be used to modify "mutable" elements (such as StringBuilder) via the "cloned" object references, but it cannot modify "immutable" objects (such as String and primitive wrapper classes) as new references are created.

Example: Using Enhanced for-each Loop on Collection of "Mutable" Objects (such as StringBuilder)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.List;
import java.util.ArrayList;
 
public class ForEachMutableTest {
   public static void main(String[] args) {
      List<StringBuilder> lst = new ArrayList<>();
      lst.add(new StringBuilder("alpha"));
      lst.add(new StringBuilder("beta"));
      lst.add(new StringBuilder("charlie"));
      System.out.println(lst);   [alpha, beta, charlie]
 
      for (StringBuilder sb : lst) {
         sb.append("123");   
      }
      System.out.println(lst);  [alpha123, beta123, charlie123]
   }
}
Example: Using Enhanced for-each loop on Collection of "Immutable" Objects (such as String)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.List;
import java.util.ArrayList;
 
public class ForEachImmutableTest {
   public static void main(String[] args) {
      List<String> lst = new ArrayList<>();
      lst.add("alpha");
      lst.add("beta");
      lst.add("charlie");
      System.out.println(lst);   
 
      for (String str : lst) {
         str += "change!";   
      }
      System.out.println(lst);   
   }
}

Collection<E> Interface

The Collection<E>, which takes a generic type E and read as Collection of element of type E, is the root interface of the Collection Framework. It defines the common behaviors expected of all classes, such as how to add or remove an element, via the following abstract methods:

abstract int size()                        
abstract boolean isEmpty()                 


abstract boolean add(E element)            
abstract boolean remove(Object element)    
abstract boolean contains(Object element)  


abstract void clear()                               
abstract boolean addAll(Collection<? extends E> c)  
abstract boolean containsAll(Collection<?> c)       
abstract boolean removeAll(Collection<?> c)
abstract boolean retainAll(Collection<?> c)
 

abstract boolean equals(Object o)
abstract int hashCode()
 

abstract Object[] toArray()       
abstract <T> T[] toArray(T[] a)   

Take note that many of these operations are mutable, i.e., they modify the Collection object. (In the Functional Programming introduced in JDK 8, operations are immutable and should not modify the source collection.)

Collection of Primitives?

A Collection<E> can only contain objects, not primitives (such as int or double). Primitive values are to be wrapped into objects (via the respective wrapper classes such as Integer and Double). JDK 5 introduces auto-boxing and auto-unboxing to simplify the wrapping and unwrapping processes. Read "Auto-Boxing and Auto-Unboxing" section for example.

List<E>, Set<E> and Queue<E>: Specialized Sub-Interfaces of Collection<E>

In practice, we typically program on one of the specialized sub-interfaces of the Collection<E> interface: List<E>, Set<E>, or Queue<E>.

  • List<E>: models aresizable linear array, which allows numerical indexed access, with index starting from 0. List<E> can contain duplicate elements. Implementations of List<E> include ArrayList<E>, LinkedList<E>, Vector<E> and Stack<E>.
  • Set<E>: models a mathematical set, where no duplicate elements areallowed. Implementations of Set<E> include HashSet<E> and LinkedHashSet<E>. The sub-interface SortedSet<E> models an ordered and sorted set of elements, implemented by TreeSet<E>.
  • Queue<E>: models queues such as First-in-First-out (FIFO) queue and priority queue. It sub-interface Deque<E> models queues that can be operated on both ends. Implementations include PriorityQueue<E>, ArrayDeque<E> and LinkedList<E>.

The details of these sub-interfaces and implementations will be covered later in the implementation section.

Map<K,V> Interface

In Java, a Map (also known as associative array) contains a collection of key-value pairs. It is similar to List and array. But instead of an numerical key 0, 1, 2, ..., a Map's key could be any arbitrary objects.

The interface Map<K,V>, which takes two generic types K and V (read as Map of key type K and value type V), is used as a collection of "key-value pairs". No duplicate key is allowed. Implementations include HashMap<K,V>, Hashtable<K,V> and LinkedHashMap<K,V>. Its sub-interface SortedMap<K,V> models an ordered and sorted map, based on its key, implemented in TreeMap<K,V>.

Take note that Map<K,V> is not a sub-interface of Collection<E>, as it involves a pair of objects for each element. The details will be covered later.

List Interfaces, Implementations and Algorithms

A List<E> models a resizable linear array, which supports numerical indexed access, with index starts from 0. Elements in a list can be retrieved and inserted at a specific index position based on an int index. It can contain duplicate elements. It can contain null elements. You can search a list, iterate through its elements, and perform operations on a selected range of values in the list.

List is the most commonly-used data structure, as a resizable array.

Which of the following methods is / are available in collections class?

The List<E> interface declares the following abstract methods, in additional to its super-interfaces. Since List has a positional index. Operation such as add(), remove(), set() can be applied to an element at a specified index position.

abstract Iterator<E> iterator();


abstract int size()
abstract boolean isEmpty()
abstract boolean add(E element)
abstract boolean remove(Object obj)
abstract boolean contains(Object obj)
abstract void clear();
......


abstract void add(int index, E element)    
abstract E set(int index, E element)       
abstract E get(int index)                  
abstract E remove(int index)               
abstract int indexOf(Object obj)
abstract int lastIndexOf(Object obj)


abstract List<E> subList(int fromIndex, int toIndex)

The abstract superclass AbstractList provides implementations to many of the abstract methods declared in List and its supertypes Collection and Iterable. However, some methods such as get(int index) remains abstract. These methods are implemented by the concrete subclasses such as ArrayList and Vector.

[TODO] Example

ArrayList<E> and Vector<E>: Implementation Classes for List<E>

ArrayList<E> is the best all-around implementation of the List<E> interface. Many useful methods are already implemented in AbstractList but overridden for efficiency in ArrayList (e.g., add(), remove(), set() etc.).

Vector<E> is a legacy class (since JDK 1.0), which is retrofitted to conform to the Collection Framework (in JDK 1.2). Vector is a synchronized thread-safe implementation of the List interface. It also contains additional legacy methods (e.g., addElement(), removeElement(), setElement(), elementAt(), firstElement(), lastElement(), insertElementAt()). There is no reason to use these legacy methods - other than to maintain backward compatibility.

ArrayList is not synchronized. The integrity of ArrayList instances is not guaranteed under multithreading. Instead, it is the programmer's responsibility to ensure synchronization. On the other hand, Vector is synchronized internally. Read "Synchronized Collection" if you are dealing with multi-threads.

Java Performance Tuning Tip: Synchronization involves overheads. Hence, if synchronization is not an issue, you should use ArrayList instead of Vector for better performance.

[TODO] Example

Stack<E>: Implementation Class for List<E>

Stack<E> is a last-in-first-out queue (LIFO) of elements. Stack extends Vector, which is a synchronized resizable array, with five additional methods:

E push(E element)       
E pop()         
E peek()        
boolean empty()         
int search(Object obj)  

[TODO] Example

LinkedList<E>: Implementation Class for List<E>

LinkedList<E> is a double-linked list implementation of the List<E> interface, which is efficient for insertion and deletion of elements, in the expense of more complex structure.

LinkedList<E> also implements Queue<E> and Deque<E> interfaces, and can be processed from both ends of the queue. It can serve as FIFO or LIFO queue.

[TODO] Example

Converting a List to an Array: toArray()

The super-interface Collection<E> defines a method called toArray() to create a fixed-length array based on this list. The returned array is free for modification.

abstract Object[] toArray()      
abstract <T> T[] toArray(T[] a)  
Example - List to array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
public class ListToArrayTest {
   public static void main(String[] args) {
      List<String> lst = new ArrayList<>();
      lst.add("alpha");
      lst.add("beta");
      lst.add("charlie");
 
      
      Object[] strArray1 = lst.toArray();
      System.out.println(Arrays.toString(strArray1));   [alpha, beta, charlie]
 
      
      String[] strArray2 = lst.toArray(new String[lst.size()]);  
      System.out.println(strArray2.length);  
strArray2[0] = "delta"; System.out.println(Arrays.toString(strArray2)); [delta, beta, charlie] System.out.println(lst); } }

Using an Array as a List: Arrays.asList()

The utility class java.util.Arrays provides a static method Arrays.asList() to convert an array into a List<T>. However, change to the list write-thru the array and vice versa. Take note that the name of the method is asList and not toList.

public static <T> List<T> asList(T[] a)
Example - Array as List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
public class TestArrayAsList {
   public static void main(String[] args) {
      String[] strs = {"alpha", "beta", "charlie"};
      System.out.println(Arrays.toString(strs));   [alpha, beta, charlie]
 
      List<String> lst = Arrays.asList(strs);
      System.out.println(lst);  [alpha, beta, charlie]
 
      
      strs[0] += "88";
      lst.set(2, lst.get(2) + "99");
      System.out.println(Arrays.toString(strs)); [alpha88, beta, charlie99]
      System.out.println(lst);  [alpha88, beta, charlie99]
 
      
      List<Integer> lstInt = Arrays.asList(22, 44, 11, 33);
      System.out.println(lstInt);  [22, 44, 11, 33]
   }
}

Comparison of ArrayList, Vector, LinkedList and Stack

[TODO] Example on benchmarking ArrayList, Vector, LinkedList, and Stack

List's Algorithms

The utility class java.util.Collections provides many useful algorithms for collection. Some work for any Collections; while many work for Lists (with numerical index) only.

Mutating Operators
static void swap(List<?> lst, int i, int j)   
static void shuffle(List<?> lst)              
static void shuffle(List<?> lst, Ramdon rnd)  
static void rotate(List<?> lst, int distnace) 
static void reverse(List<?> lst)              
static <T> void fill(List<? super T>, T obj)  
static <T> void copy(List<? super T> dest, List<? extends T> src)  
static <T> boolean replaceAll(List<T> lst, T oldVal, T newVal)     

[TODO] example

Sub-List (Range-View) Operations

The List<E> supports range-view operation via .subList() as follows. The returned List is backup by the given List, so change in the returned List are reflected in the original List.

List<E> subList(int fromIdx, int toIdx)

The Utility class Collections supports these sub-list operations:

static int indexOfSubList(List<?> src, List<?> target)
static int lastIndexOfSubList(List<?> src, List<?> target)

For example,

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class SubListTest {
   public static void main(String[] args) {
      List<Integer> lst = new ArrayList<>();
      for (int i = 0; i < 10; ++i) lst.add(i * 10);
      System.out.println(lst);  

      lst.subList(3, 6).clear();  
      System.out.println(lst);    

      System.out.println(lst.subList(2, 5).indexOf(60));  

      List<Integer> lst2 = List.of(20, 60, 70);  
      System.out.println(Collections.indexOfSubList(lst, lst2));      
      System.out.println(Collections.lastIndexOfSubList(lst, lst2));  
   }
}
Searching, Sorting and Ordering

The utility class Collections provides these static methods for searching, sorting and ordering (max, min) of List:

static <T> int binarySearch(List<? extends T> lst, T key, Comparator<? super T> comp)
static <T> int binarySearch(List<? extends Comparable<? super T>> lst, T key)
   

static <T> void sort(List<T> lst, Comparator<? super T> comp)
static <T extends Comparable<? super T>> void sort(List<T> lst)

static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)

Each of these algorithms has two versions:

  1. Requires a Comparator object with a compare() method to determine the order of the elements.
  2. Requires a List which implement Comparable interface, with a method compareTo() to determine the order of elements.

We shall elaborate in the next section.

List Ordering/Searching/Sorting with Comparable<T>/Comparator<T>

Ordering is needed in these two situations:

  1. To sort a Collection or an array (using the Collections.sort() or Arrays.sort() methods), an ordering specification is needed.
  2. Some Collections, in particular, SortedSet (TreeSet) and SortMap (TreeMap), are ordered. That is, the objects are stored according to a specified order.

There are two ways to specify the ordering of objects:

  1. Create a special java.util.Comparator<T> object, with a method compare() to specify the ordering of comparing two objects.
  2. Make the objects implement the java.lang.Comparable<T> interface, and override the compareTo() method to specify the ordering of comparing two objects.

Comparable<T> Interface

A java.lang.Comparable<T> interface specifies how two objects are to be compared for ordering. It defines one abstract method:

abstract int compareTo(T o)  

This ordering is referred to as the class's natural ordering.

It is strongly recommended that compareTo() be consistent with equals() and hashCode() (inherited from java.lang.Object):

  1. If compareTo() returns a zero, equals() should return true.
  2. If equals() returns true, hashCode() shall produce the same int.

All the eight primitive wrapper classes (Byte, Short, Integer, Long, Float, Double, Character and Boolean) implement Comparable<T> interface, with the compareTo() uses the numerical order.

The String class also implements Comparable<String> interface, which compares two strings lexicographically based on the Unicode value of each character in the strings. The uppercase letters are smaller than the lowercase counterparts.

Example 1: Searching/Sorting String and Primitive Wrapper Types, which implement Comparable<T>

The utility class java.util.Arrays and java.util.Collections provide many static method for the various algorithms such as sorting and searching. In this example, we use the Arrays.sort() and Collections.sort() methods to sort an array of Strings and a List of Integers, based on their Comparable<T>'s compareTo() method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class StringPrimitiveComparableTest {
   public static void main(String[] args) {
      
      
      String[] strArray = {"Hello", "hello", "Hi", "HI", "Hello"};  

      Arrays.sort(strArray);  
      System.out.println(Arrays.toString(strArray));  

      
      System.out.println(Arrays.binarySearch(strArray, "Hello")); 
      System.out.println(Arrays.binarySearch(strArray, "HELLO")); 

      
      List<Integer> lst = new ArrayList<>();
      lst.add(22);  
      lst.add(11);
      lst.add(44);
      lst.add(11);  
      Collections.sort(lst);    
      System.out.println(lst);  
      System.out.println(Collections.binarySearch(lst, 22)); 
      System.out.println(Collections.binarySearch(lst, 35)); 
   }
}
Example 2: Custom Implementation of Comparable<T>

Let's create a subclass of Person (see "Person.java" above), called ComparablePerson which implements Comparable<Person> interface, and try out the Collections.sort() and Collections.binarySearch() methods.

1
2
3
4
5
6
7
8
9
10
11
public class ComparablePerson extends Person implements Comparable<Person> {
   public ComparablePerson(String name, int age) {   
      super(name, age);
   }

   
   @Override
   public int compareTo(Person p) {
      return this.getName().compareToIgnoreCase(p.getName());  
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class ComparablePersonTest {
   public static void main(String[] args) {
      List<ComparablePerson> pLst = new ArrayList<>();
      pLst.add(new ComparablePerson("Peter", 21));
      pLst.add(new ComparablePerson("Paul", 18));
      pLst.add(new ComparablePerson("John", 60));
      System.out.println(pLst);  

      
      Collections.sort(pLst);    
      System.out.println(pLst);  

      
      System.out.println(Collections.binarySearch(pLst, new ComparablePerson("PAUL", 18)));  
      System.out.println(Collections.binarySearch(pLst, new ComparablePerson("PAUL", 16)));  
      System.out.println(Collections.binarySearch(pLst, new ComparablePerson("Kelly", 18))); 
   }
}

Comparator<T> Interface

Besides the java.lang.Comparable<T> for the natural ordering, you can pass a java.util.Comparator<T> object into the sorting methods (Collections.sort() or Arrays.sort()) to provide precise control over the ordering. The Comparator<T> will override the Comparable<T>, if available.

The Comparator<T> interface declares one abstract method (known as Functional Interface in JDK 8):

abstract int compare(T o1, T o2)  

Take note that you need to construct an instance of Comparator<T>, and invoke compare() to compare o1 and o2. [In the earlier Comparable<T>, the method is called compareTo() and it takes only one argument, i.e., this object compare to the given object.]

Example 3: Using Customized Comparator<T> for String and Integer

In this example, instead of using the natural Comparable<T>, we define our customized Comparator<T> for Strings and Integers. We can do this via any of the following ways:

  1. A named inner class
  2. An anonymous inner class
  3. Lambda Expressions (JDK 8)
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class StringPrimitiveComparatorTest {
   
   
   public static class StringComparator implements Comparator<String> {
      @Override
      public int compare(String s1, String s2) {
         return s1.compareToIgnoreCase(s2);
      }
   }

   public static void main(String[] args) {
      
      Comparator<String> strComp = new StringComparator();

      
      String[] array = {"Hello", "Hi", "HI", "hello", "Hello"};  
      Arrays.sort(array, strComp);
      System.out.println(Arrays.toString(array));  
      System.out.println(Arrays.binarySearch(array, "Hello", strComp)); 
      System.out.println(Arrays.binarySearch(array, "HELLO", strComp)); 

      
      Comparator<Integer> intComp = new Comparator<Integer>() {
         @Override
         public int compare(Integer i1, Integer i2) {
            return i1%10 - i2%10;
         }
      };

      
      List<Integer> lst = new ArrayList<Integer>();
      lst.add(42);  
      lst.add(21);
      lst.add(34);
      lst.add(13);
      Collections.sort(lst, intComp);
      System.out.println(lst);  
      System.out.println(Collections.binarySearch(lst, 22, intComp)); 
      System.out.println(Collections.binarySearch(lst, 35, intComp)); 
   }
}

Try: Modify the Comparator to sort in A, a ,B, b, C, c ... (uppercase letter before the lowercase).

Notes: You can use Lambda Expressions (JDK 8) to shorten this code, as follows:

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class StringPrimitiveComparatorJ8Test {  
   public static void main(String[] args) {
      
      Comparator<String> strComp = (s1, s2) -> s1.compareToIgnoreCase(s2);
         

      
      String[] array = {"Hello", "Hi", "HI", "hello", "Hello"};  
      Arrays.sort(array, strComp);
      System.out.println(Arrays.toString(array));  
      System.out.println(Arrays.binarySearch(array, "Hello", strComp)); 
      System.out.println(Arrays.binarySearch(array, "HELLO", strComp)); 

      
      Comparator<Integer> intComp = (i1, i2) -> i1%10 - i2%10;

      
      List<Integer> lst = new ArrayList<Integer>();
      lst.add(42);  
      lst.add(21);
      lst.add(34);
      lst.add(13);
      Collections.sort(lst, intComp);
      System.out.println(lst);  
      System.out.println(Collections.binarySearch(lst, 22, intComp)); 
      System.out.println(Collections.binarySearch(lst, 35, intComp)); 
   }
}

More example at "Example: Comparator Lambda".

Example 4: Using Customized Comparator<Person> for Person Objects

Person.java: See above

import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Collections;
public class ComparatorPersonTest {
   public static void main(String[] args) {
      List<Person> pLst = new ArrayList<>();
      pLst.add(new Person("Peter", 21));
      pLst.add(new Person("Paul", 18));
      pLst.add(new Person("John", 60));
      System.out.println(pLst);  

      
      Comparator<Person> comp = new Comparator<>() {
         @Override
         public int compare(Person p1, Person p2) {
            return p1.getName().compareToIgnoreCase(p2.getName());
         }
      };

      
      Collections.sort(pLst, comp);
      System.out.println(pLst);  

      
      System.out.println(Collections.binarySearch(pLst, new Person("PAUL", 18), comp));  
      System.out.println(Collections.binarySearch(pLst, new Person("PAUL", 16), comp));  
      System.out.println(Collections.binarySearch(pLst, new Person("Kelly", 18), comp)); 

      
      
      pLst.add(new Person("Janes", 30));
      System.out.println(pLst);  
      Collections.sort(pLst,
            (p1, p2) -> p1.getName().toLowerCase().compareTo(p2.getName().toLowerCase()));
      System.out.println(pLst);  
   }
}

Set<E> Interfaces, Implementations and Algorithms

The Set<E> interface models a mathematical set, where no duplicate elements are allowed (e.g., playing cards). It may contain a single null element.

Which of the following methods is / are available in collections class?

The Set<E> interface declares the following abstract methods. The insertion, deletion and inspection methods returns false if the operation fails, instead of throwing an exception.

abstract boolean add(E o)           
abstract boolean remove(Object o)   
abstract boolean contains(Object o) 
 

abstract boolean addAll(Collection<? extends E> c) 
abstract boolean retainAll(Collection<?> c)        

The implementations of Set<E> interface include:

  • HashSet<E>: Stores the elements in a hash table (hashed via the hashcode()). HashSet is the best all-round implementation for Set.
  • LinkedHashSet<E>: Stores the elements in a linked-list hash table for better efficiency in insertion and deletion. The element are hashed via the hashCode() and arranged in the linked list according to the insertion-order.
  • TreeSet<E>: Also implements sub-interfaces NavigableSet and SortedSet. Stores the elements in a red-black tree data structure, which are sorted and navigable. Efficient in search, add and remove operations (in O(log(n))).

HashSet<E> By Example

Let's write a Book class, and create a Set of Book objects.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Book {
   private int id;
   private String title;
 
   public Book(int id, String title) {  
      this.id = id;
      this.title = title;
   }
 
   @Override
   public String toString() {  
      return id + ": " + title;
   }
 
   
   @Override
   public boolean equals(Object o) {
      return o != null && o instanceof Book && this.id == ((Book)o).id;
   }
 
   
   @Override
   public int hashCode() {
      return id;
   }
}

We need to provide an equals() method, so that the Set implementation can test for equality and duplication. In this example, we choose the id as the distinguishing feature. We override equals() to return true if two books have the same id. We also override the hashCode() to be consistent with equals().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.HashSet;
import java.util.Set;
public class HashSetTest {
   public static void main(String[] args) {
      Book book1 = new Book(1, "Java for Dummies");
      Book book1Dup = new Book(1, "Java for the Dummies"); 
      Book book2 = new Book(2, "Java for more Dummies");
      Book book3 = new Book(3, "more Java for more Dummies");
 
      Set<Book> set1 = new HashSet<Book>();
      set1.add(book1);
      set1.add(book1Dup); 
      set1.add(book1);    
      set1.add(book3);
      set1.add(null);     
      set1.add(null);     
      set1.add(book2);
      System.out.println(set1);

 
      set1.remove(book1);
      set1.remove(book3);
      System.out.println(set1); [null, 2: Java for more Dummies]
 
      Set<Book> set2 = new HashSet<Book>();
      set2.add(book3);
      System.out.println(set2); [3: more Java for more Dummies]

      set2.addAll(set1);        
      System.out.println(set2); [null, 2: Java for more Dummies, 3: more Java for more Dummies]
 
      set2.remove(null);
      System.out.println(set2); [2: Java for more Dummies, 3: more Java for more Dummies]

      set2.retainAll(set1);     
      System.out.println(set2); [2: Java for more Dummies]
   }
}
  • A Set cannot hold duplicate element. The elements are check for duplication via the overridden equal().
  • A Set can hold a null value as its element (but no duplicate too).
  • The addAll() and retainAll() perform set union and set intersection operations, respectively.

Take note that the arrangement of the elements is arbitrary, and does not correspond to the order of add().

LinkedHashSet<E> By Example

Unlike HashSet, LinkedHashSet builds a link-list over the hash table for better efficiency in insertion and deletion (in the expense of more complex structure). It maintains its elements in the insertion-order (i.e., order of add()).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSetTest {
   public static void main(String[] args) {
      Book book1 = new Book(1, "Java for Dummies");
      Book book1Dup = new Book(1, "Java for the Dummies"); 
      Book book2 = new Book(2, "Java for more Dummies");
      Book book3 = new Book(3, "more Java for more Dummies");
 
      Set<Book> set = new LinkedHashSet<Book>();
      set.add(book1);
      set.add(book1Dup); 
      set.add(book1);    
      set.add(book3);
      set.add(null);     
      set.add(null);     
      set.add(book2);
      System.out.println(set);
     [1: Java for Dummies, 3: more Java for more Dummies, null, 2: Java for more Dummies]
   }
}

The output clearly shows that the set is ordered according to the order of add().

SortedSet<E> and NavigableSet<E> Interfaces

Elements in a SortedSet<E> are sorted during add(), either using the natural ordering in the Comparable<T>, or given a Comparator<T> object. Read "Ordering, Sorting and Searching" for details on Comparable<T> and Comparator<T>.

The NavigableSet<E> is a sub-interface of SortedSet<E>, which declares these additional navigation methods:

abstract Iterator<E> iterator()            
abstract Iterator<E> descendingIterator()  
abstract E floor(E e)    
abstract E ceiling(E e)  abstract E lower(E e)    abstract E higher(E e)    

abstract SortedSet<E> headSet(E toElement)   
abstract SortedSet<E> tailSet(E fromElement) 
abstract SortedSet<E> subSet(E fromElement, E toElement)  
         

TreeSet<E> by Example

TreeSet<E> is an implementation to NavigableSet<E> and SortedSet<E>.

Example - TreeSet with Comparable<E>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class AddressBookEntry implements Comparable<AddressBookEntry> {
   private String name, address, phone;
 
   public AddressBookEntry(String name) {  
      this.name = name;
   }
 
   @Override
   public String toString() {  
      return name;
   }
 
   @Override
   public int compareTo(AddressBookEntry other) {  
      return this.name.compareToIgnoreCase(other.name);
   }
 
   @Override
   public boolean equals(Object o) {
      return o != null && o instanceof AddressBookEntry && this.name.equalsIgnoreCase(((AddressBookEntry)o).name);
   }
 
   
   @Override
   public int hashCode() {
      return name.toLowerCase().hashCode();
   }
}

This AddressBookEntry class implements Comparable, in order to be used in TreeSet. It overrides compareTo() to compare the name in a case insensitive manner. It also overrides equals() and hashCode(), so as they are consistent with the compareTo().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.TreeSet;
 
public class TreeSetComparableTest {
   public static void main(String[] args) {
      AddressBookEntry addr1 = new AddressBookEntry("peter");
      AddressBookEntry addr2 = new AddressBookEntry("PAUL");
      AddressBookEntry addr3 = new AddressBookEntry("Patrick");
 
      TreeSet<AddressBookEntry> set = new TreeSet<>();
      set.add(addr1);
      set.add(addr2);
      set.add(addr3);
      System.out.println(set); [Patrick, PAUL, peter]
 
      System.out.println(set.floor(addr2));   
      System.out.println(set.lower(addr2));   Patrick
      System.out.println(set.headSet(addr2)); [Patrick]
      System.out.println(set.tailSet(addr2)); [PAUL, peter]
   }
}

Observe that the AddressBookEntry objects are sorted and stored in the order depicted by the Comparable<T> during add() operation.

Example - TreeSet with Comparator<T>

Let's rewrite the previous example to use a Comparator object instead of Comparable. We shall set the Comparator to order in descending order of name for illustration.

1
2
3
4
5
6
7
8
9
10
11
12
public class PhoneBookEntry {
   public String name, address, phone;
 
   public PhoneBookEntry(String name) {  
      this.name = name;
   }
 
   @Override
   public String toString() {
      return name;
   }
}

The PhoneBookEntry class does not implement Comparator. You cannot add() a PhoneBookEntry object into a TreeSet() as in the above example. Instead, we define a Comparator class, and use an instance of Comparator to construct a TreeSet.

The Comparator orders the PhoneBookEntry objects in descending name and case insensitive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;
 
public class TreeSetComparatorTest {
   
   public static class PhoneBookComparator implements Comparator<PhoneBookEntry> {
      @Override
      public int compare(PhoneBookEntry p1, PhoneBookEntry p2) {
         return p2.name.compareToIgnoreCase(p1.name);  
      }
   }
 
   public static void main(String[] args) {
      PhoneBookEntry addr1 = new PhoneBookEntry("peter");
      PhoneBookEntry addr2 = new PhoneBookEntry("PAUL");
      PhoneBookEntry addr3 = new PhoneBookEntry("Patrick");
 
      Comparator<PhoneBookEntry> comp = new PhoneBookComparator();
      TreeSet<PhoneBookEntry> set = new TreeSet<PhoneBookEntry>(comp);
      set.add(addr1);
      set.add(addr2);
      set.add(addr3);
      System.out.println(set);    [peter, PAUL, Patrick]
 
      Set<PhoneBookEntry> newSet = set.descendingSet();  
      System.out.println(newSet); [Patrick, PAUL, peter]
   }
}

In the test program, we construct a TreeSet with the BookComparator. We also tried the descendingSet() method to obtain a new Set in reverse order.

Queue<E> Interfaces, Implementations and Algorithms

A queue is a collection whose elements are added and removed in a specific order, typically in a first-in-first-out (FIFO) manner. A deque (pronounced "deck") is a double-ended queue that elements can be inserted and removed at both ends (head and tail) of the queue.

Which of the following methods is / are available in collections class?

Besides basic Collection<E> operations, Queue<E> provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operations). The latter form of the insert operation is designed specifically for use with capacity-restricted Queue implementations

abstract boolean add(E e)   
abstract boolean offer(E e) 
 

abstract E remove()         
abstract E poll()           
 

abstract E element()        
abstract E peek()           

Deque<E> declares additional methods to operate on both ends (head and tail) of the queue.

abstract void addFirst(E e)
abstract void addLast(E e)
abstract boolean offerFirst(E e)
abstract boolean offerLast(E e)
 

abstract E removeFirst()
abstract E removeLast()
abstract E pollFirst()
abstract E pollLast()
 

abstract E getFirst()
abstract E getLast()
abstract E peekFirst()
abstract E peekLast()

A Deque can be used as FIFO queue (via methods add(e), remove(), element(), offer(e), poll(), peek()) or LIFO queue (via methods push(e), pop(), peek()).

The Queue<E> and Deque<E> implementations include:

  • PriorityQueue<E>: A queue where the elements are ordered based on an ordering you specify, instead of FIFO.
  • ArrayDeque<E>: A queue and deque implemented as a dynamic array, similar to ArrayList<E>.
  • LinkedList<E>: The LinkedList<E> also implements the Queue<E> and Deque<E> interfaces, in additional to List<E> interface, providing a queue or deque that is implemented as a double- linked list data structure.

The basic operations of Queue<E> include adding an element, polling the queue to retrieve the next element, or peeking at the queue to see if there is an element available in the queue. The Deque<E> operations are similar except element can be added, polled, or peeked at both ends of the deque.

[TODO] Example

Map<K,V> Interfaces, Implementations and Algorithms

A map is a collection of key-value pairs (e.g., name-address, name-phone, isbn-title, word-count). Each key maps to one and only value. Duplicate keys are not allowed, but duplicate values are allowed. Maps are similar to linear arrays, except that an array uses an integer key to index and access its elements; whereas a map uses any arbitrary key (such as Strings or any objects).

Which of the following methods is / are available in collections class?

The implementations of Map<K,V> interface include:

  • HashMap<K,V>: Hash table implementation of the Map<K,V> interface. The best all-around implementation. Methods in HashMap is not synchronized.
  • TreeMap<K,V>: Red-black tree implementation of the SortedMap<K,V> interface.
  • LinkedHashMap<K,V>: Hash table with link-list to facilitate insertion and deletion.
  • Hashtable<K,V>: Retrofitted legacy (JDK 1.0) implementations. A synchronized hash table implementation of the Map<K,V> interface that does not allow null key or values, with legacy methods.
Basic Operations

The Map<K,V> interface declares the following abstract methods for basic operations:

abstract int size()             
abstract boolean isEmpty()      
abstract V get(Object key)      
abstract V put(K key, V value)  
abstract boolean containsKey(Object key)     
abstract boolean containsValue(Object value) 
abstract void clear()              
abstract void V remove(object key) 
Collection Views

The map<K,V> provides these method to allow a map to be viewed as a Collection:

abstract Set<K> keySet()         
abstract Collection<V> values()  
abstract Set<Map.Entry<K,V>> entrySet()  

The nested class Map.Entry<K,V> contains these methods:

K getKey()     
V getValue()   
V setValue()   

The Map does not have List-like iterator. The Collection views provides the means to iterate over a map.

Example 1: Iterating through a Map using .entrySet() and .keySet()
import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

public class MapViewTest {
   public static void main(String[] args) {
      Map<String, Double> map = new HashMap<>();
      map.put("espresso", 1.1);
      map.put("latte", 2.2);
      map.put("cappuccino", 3.3);
      System.out.println(map);  

      
      for (Map.Entry<String, Double> e : map.entrySet()) {
         e.setValue(e.getValue() + 10.0);  
         System.out.println(e.getKey() + ":" + e.getValue());
      }
      
      
      

      
      
      System.out.println(map.keySet());  
      for (String key : map.keySet()) {
         System.out.println(key + "=" + map.get(key));
      }
      
      
      

      
      Iterator<String> iter = map.keySet().iterator();
      while (iter.hasNext()) {
         String key = iter.next();
         System.out.println(key + ":" + map.get(key));
      }
      
      
      

      
      System.out.println(map.values());  
   }
}
Example 2: Word Count using HashMap<String, Integer>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Map;
import java.util.HashMap;
import java.util.Scanner;
import java.io.File;
 
public class WordCount {
   public static void main(String[] args) throws Exception {
      Scanner in = new Scanner(new File(args[0]));
 
      Map<String, Integer> map = new HashMap<>();
      while (in.hasNext()) {
         String word = in.next();
         int freq = (map.get(word) == null) ? 1 : map.get(word) + 1;   
         map.put(word, freq);      
      }
      System.out.println(map);
   }
}

Utilities Class java.util.Arrays

The Collection Framework provides two utility classes: java.util.Arrays and java.util.Collections, which provide some useful algorithms, such as sort, shuffle, reverse, and search, on arrays and Collections.

Array is a reference type in Java. It can hold primitives, as well as objects. On the other hand, a Collection holds only object.

Array Sorting/Searching: Arrays.sort() and Arrays.binarySearch()

Sorting of Primitive and Object Arrays

There is a pair of sort() methods for each of the primitive types (except boolean) and Object.

For example, for int[]:

static sort(int[] a) -> void
static sort(int[] a, int fromIdx, int toIdx) -> void



static sort(Object[] a) -> void
static sort(Object[] a, int fromIdx, int toIdx) -> void

Similar sort() methods are available for primitive arrays byte[], short[], long[], float[], double[], char[] (except boolean[]), and Object[]. For Object[], the objects must implement Comparable<T> interface so that the ordering can be determined via the compareTo() method.

Soriting for Generic Arrays

A pair of methods is also defined for generic, to be sorted based on the given Comparator (instead of Comparable).

static sort(T[] a, Comparator<Ts> c) -> void
static sort(T[] a, int fromIdx, int toIdx, Comparator<? super T> c) -> void

Note: Suppose that you wish to sort an array of Integer (where T is Integer), you could use a Comparator<Integer>. You can also use Comparator<Number> or Comparator<Object>, as Object and Number are superclass of Integer.

Seaching of Primitive, Object and Generic Arrays

Similarly, there is a pair of searching method for each of the primitive arrays (except boolean[]) and Object. The arrays must be sorted before you can apply the binarySearch() method.

static binarySearch(int[] a, int key) -> int
static binarySearch(int[] a, int fromIdx, int toIdx, int key) -> int

 

static binarySearch(Object[] a, Object key) -> int
static binarySearch(Object[] a, int fromIdx, int toIdx, Object key) -> int


static binarySearch(T[] a, T key, Comparator<? super T> c) -> int
static binarySearch(T[] a, T key, int fromIdx, int toIdx, Comparator<? super T> c) -> int
Examples

See "List Ordering/Searching/Sorting".

Equality Comparison: Arrays.equals()

static equals(int[] a, int[] b) -> boolean

Copying: Arrays.copyOf() and Arrays.copyOfRange()

static copyOf(int[] src, int length) -> int[]
  
static copyOfRange(int[] src, int fromIdx, int toIdx) -> int[]


static copyOf(T[] src, int length) -> T[]
static copyOfRange(T[] src, int fromIdx, int toIdx) -> T[]
static copyOf(U[] src, int length, Class<? extends T[]> newType) -> T[]
static copyOfRange(U[] src, int fromIdx, int toIdx, Class<? extends T[]> newType) -> T[]

Filling: Arrays.fill()

static fill(int[] a, int value) -> void
static fill(int[] a, int fromIdx, int toIdx, int value) -> void

Description: Arrays.toString()

static toString(int[] a) -> String

Converting to List: Arrays.asList()

static asList(T[] a) -> List<T>

Utilities Class java.util.Collections

The Collection Framework provides two utility classes: java.util.Arrays and java.util.Collections, which provide some useful algorithms, such as sort, shuffle, reverse, and search, on arrays and Collections. Take note that the interface is called Collection, while the utility class is called Collections with a 's'.

List Searching/Sorting: Collations.sort()/binarySearch()

static sort(List<T> list) -> void

static sort(List<T> list, Comparator<? super T> c) -> void

static binarySearch(List<? extends Comparable<? super T>> list, T key) -> int
static binarySearch(List<? extends T> list, T key, Comparator<? super T> c) -> int

See "List Algorithms".

Maximum and Minimum: Collections.max()|min()

static max(Collection<? extends T> c) -> T
static min(Collection<? extends T> c) -> T
 

static max(Collection<? extends T> c, Comparator<? super T> comp) -> T
static min(Collection<? extends T> c, Comparator<? super T> comp) -> T

Synchronized Wrapper: Collections.synchronizedXxx()

Most of the Collection implementations such as ArrayList, HashSet and HashMap are NOT synchronized for multi-threading, except the legacy Vector and HashTable, which are retrofitted to conform to the Collection Framework and synchronized. Instead of using the synchronized Vector and HastTable, you can create a synchronized Collection, List, Set, SortedSet, Map and SortedMap, via the static Collections.synchronizedXxx() methods:

static synchronizedCollection(Collection<T> c) -> Collection<T>
static synchronizedList(List<T> list) -> List<T>
static synchronizedSet(Set<T> set) -> Set<T>
static synchronizedSortedSet(SortedSet<T> set) -> SortedSet<T>
static synchronizedMap(Map<K,V> map) -> Map<K,V>
static synchronizedSortedMap(SortedMap<K,V> map) -> SortedMap<K,V>

According to the JDK API specification, "to guarantee serial access, it is critical that all access to the backing list is accomplished through the returned list, and that user manually synchronize on the returned list when iterating over it". For example,

List lst = Collections.synchronizedList(new ArrayList());
   ......
synchronized(lst) {  
   Iterator iter = lst.iterator(); 
   while (iter.hasNext())
     iter.next();
     ......
}

Unmodifiable Wrappers: Collections.unmodifiableXxx()

Unmodifiable wrappers prevent modification of the collection by intercepting all the operations that would modify the collection and throwing an UnsupportedOperationException.

The Collections class provides six static methods to wrap the interfaces Collection, List, Set, SortedSet, Map and SortedMap.

static unmodifiableCollection(Collection<? extends T> c) -> Collection<T>
static unmodifiableList(List<? extends T> list) -> List<T>
static unmodifiableSet(Set<? extends T> s) -> Set<T>
static unmodifiableSortedSet(SortedSet<? extends T> s) -> SortedSet<T>
static unmodifiableMap(Map<? extends K, ? extends V> m) -> Map<K,V>
static unmodifiableSortedMap(SortedMap<K, ? extends V> m) -> SortedMap<K,V>

Utility Class java.util.Objects (JDK 7)

Note: By JDK convention, Object is a regular class modeling objects, and Objects is an utility class containing static methods for Object.

The utility class java.util.Objects contains static methods for operating on Objects (such as comparing two objects and computing hash code), and checking certain conditions (such as checking for null, checking if indexes are out of bounds) before operations.

static compare(T a, T b, Comparator<T> c) -> int
static equals(Object a, Object b) -> boolean
static deepEquals(Object a, Object b) -> boolean
static hashCode(Object o) -> int
static hash(Object... values) -> int
static toString(Object o) -> String
static toString(Object o, String nullDefault) -> String


static checkIndex(int idx, int length) -> int
static checkFromToIndex(int fromIdx, int toIdx, int length) -> int
static checkFromIndexSize(int fromIdx, int size, int length) -> int


static isNull(Object o) -> boolean
static nonNull(Object o) -> boolean
static requireNonNull(T obj) -> T
static requireNonNull(T obj, String errmsg) -> T
static requireNonNull(T obj, Supplier<String> msgSupplier) -> T
static requireNonNullElse(T obj, T defaultObj) -> T
static requireNonNullElseGet(T obj, Supplier<T> supplier) -> T

Examples [TODO]

LINK TO JAVA REFERENCES & RESOURCES

More References

  1. Java Online Tutorial on "Generics" @ http://docs.oracle.com/javase/tutorial/extra/generics/index.html.
  2. Java Online Tutorial on "Collections" @ http://docs.oracle.com/javase/tutorial/collections/index.html.

What are the three types of collections?

Collection types represent different ways to collect data, such as hash tables, queues, stacks, bags, dictionaries, and lists..
Array..
ArrayList..
List<T>.
Queue..
ConcurrentQueue<T>.
Stack..
ConcurrentStack<T>.
LinkedList<T>.

Which of the following are available in collections class?

Collections in Java..
Collections Class in Java..
List Interface in Java with Examples..
ArrayList in Java..
Vector Class in Java..
Stack Class in Java..
LinkedList in Java..
Queue Interface In Java..

Which of the following methods are in the collection interface?

The Collection interface contains methods that perform basic operations, such as int size() , boolean isEmpty() , boolean contains(Object element) , boolean add(E element) , boolean remove(Object element) , and Iterator<E> iterator() .

Which of the following methods is are available in collections?

Some of the methods of Collection interface are Boolean add ( Object obj), Boolean addAll ( Collection c), void clear(), etc. which are implemented by all the subclasses of Collection interface.