Java Collections Framework

Collection

A collection is a grouping of multiple objects. A collection can be used to store and manipulate any type of objects e.g Student, Person, Organization etc.
Various collections utility classes are available in java to store objects and perform various operations on them.

Interfaces

Collection interface

    int size()

    boolean isEmpty()

    boolean contains(Object element) 

    boolean add(E element)

    boolean remove(Object element) 

    Iterator iterator()

    boolean containsAll(Collection c)

    boolean addAll(Collection c) 

    boolean removeAll(Collection c)

    boolean retainAll(Collection c)

    void clear()

Set interface

All classes which are child of Set interface can manage single set of elements but no duplicate values allowed.
Set is like a mathematical set that can not have duplicate elements. Set is a Collection and hence inherits the methods from the Collection interface and put a restriction on the duplicity of the
elements. Objects being added to a set must overwrite the hashcode method if they are overwriting the equals methods as
it is necessary to make work the no-duplicacy nature of the objects being added to any Set implimentation.

Set Implementation Classes

• HashSet: Internally uses a hash table to store the elements. It does not make any guarantee of the ordering of the
  elements as traversal can give you a different order than the oreder of insertion but provides the best performance in all
  the implementations of set. So when the ordering of the elements does not matter, it is the best set implementation for use.
• TreeSet: Intyernally uses a red-black tree to store the elements. TreeSet orders its elements on the baisis of a
  natural sorting order or any sorting order passed to Comparable.
• LinkedHashSet: Internally uses a hash table with a linked list implementation. Maintains the order of the elements
  on the baisis of the insertion order. Lateral traversal will give you the order as the order of insertion. So if you need to maintain the order of insertion then it saves you from the unexpected ordering of the HashSet.

Set Interface Basic Operations

• size()- returns the cardinality(number of elements in the Set) .
• isEmpty()- returns¬¬ true if it is empty.
• add() - adds the specified element if it is not present in the set.
• remove()- removes the passed element from the Set.
• Iterator() - returns an Iterator for the Set.

Following program creates a set of Strings using HashSet implementation class and perform basic operations add(), remove(), isEmpty(),
size() and iterates over it using an iterator.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class SetTest {

	public static void main(String[] args) {
		
		Set<String> strSet=new HashSet<String>();
		
		System.out.println("As of now Set is empty so result for isEmpty() is : "+strSet.isEmpty());
		System.out.println("Size of the Set is Zero so result for size() is : "+strSet.size());
		
		strSet.add("Ram");
		strSet.add("Ajit");
		strSet.add("Bhanu");
		strSet.add("Ram");//Trying to add duplicate element
		
		System.out.println();
		System.out.println("Added elements");
		System.out.println();
		
		System.out.println("After adding elements, result for isEmpty() is : "+strSet.isEmpty());
		System.out.println("After adding elements, result for size() is : "+strSet.size());

		System.out.println("Tried to add 4 elements but size is 3 because we tried to add a duplicate element");
		
		
		System.out.println();
		System.out.println("Printing elements :");
		
		Iterator<String> itr = strSet.iterator();
		//Printing all the Set elements
		while (itr.hasNext()) {
			String string = (String) itr.next();
			System.out.println(string);
			if (string.equals("Ajit")) {
				itr.remove();//Removing "Ajit" from the Set
			}
		}

		System.out.println();
		System.out.println("Printing the below strings from Set after removal of \"Ajit\" :");
		//After removal of the string printing the set strings using for-each construct
		for (String string : strSet) {
			System.out.println(string);
		}
	}
	
}

We can traverse a Set using following three ways -

• for-each construct
• Iterators.
• Aggregate Operations

For-each allows to traverse a Set using a loop. Using for-each we can go through each element and perform some operation like
printing the value for the element as shown in the below code snippet. In the below code, a Set to hold string has been prepared which uses a HashSet implementation Using for-each construct traversing
and printing the Set values.

import java.util.HashSet;
import java.util.Set;

public class TraversalTestForEach {
	
	public static void main(String[] args) {
		Set<String> strSet=new HashSet<String>();
		
		strSet.add("Ram");
		strSet.add("Ajit");
		strSet.add("Bhanu");
		strSet.add("Ram");
		
		for (String string : strSet) {
			System.out.println(string);
		}
			
	}
		
}

An Iterator object enables us to traverse through a Set. Using iterator we can also remove the elements from the Set.
Using iterator() method from collection we can get the iterator for the Set and we can traverse through the Set. Iterator interface.

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove(); //optional
}

Interator interface has got the following methods:

1. boolean hasNext() – returns true if iterator has more elements to be traversed
2. next() – returns the next element in the iteration
3. remove() – removes the last element from the Set that was returned by the next. It can be called ony once after the next()
   has been called otherwise throws exception. Interator is the only safe way to modify the Set during iteration. In any other
   case unexpected events can happen.

Following is the code snippet to traverse Set using iterator.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class TraversalTestIterator {
	public static void main(String[] args) {
		Set<String> strSet = new HashSet<String>();

		strSet.add("Ram");
		strSet.add("Ajit");
		strSet.add("Bhanu");
		strSet.add("Ram");

		Iterator<String> itr = strSet.iterator();

		while (itr.hasNext()) {
			String string = (String) itr.next();
			System.out.println(string);
		}
	}
}

JDK 8 release has introduced a new method which is also preferred method to traverse that is to obtain a stream over the collection(Set) and perform aggregate operations on it. Some of the aggregate operations are provided with the capability to use lambda expressions with them. Lambda expressions
provides the capability to pass the code as parameters in the form of functional interfaces. Lambda expressions make the
code short(lesser lines of code) and expressive.
The following code iterates through the Set and prints the values:

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class TraversalUsingAggregateFun {

	public static void main(String[] args) {

		Set<String> strSet = new HashSet<String>();

		strSet.add("Ram");
		strSet.add("Ajit");
		strSet.add("Bhanu");
		strSet.add("Ram");

		/*
		 * JDK 8 release has introduced a new method which is also preferred
		 * method to traverse that is to obtain a stream over the collection and
		 * perform aggregate operations on it. Aggregate operations are provided
		 * with the capability to use lambda expressions with them. Lambda
		 * expressions provides the capability to pass the code as param,eters
		 * in the form of functional interfaces. Lambda expressions make the
		 * code short(lesser lines of code) and expressive. The following code
		 * iterates through the collection and prints the values:
		 */

		/*
		 * In the below code, first we are getting the stream on the collection
		 * and traversing using the forEach() function and within the function
		 * paasing a Lambda Expression to print each element.
		 */

		System.out.println("Printing using stream along with a filter operation :");
		strSet.stream()
		.filter(e -> e.length() == 4)
		.forEach(e -> System.out.println(e));

		System.out.println();
		System.out.println("Printing all the elements using stream :");
		strSet.stream()
		.forEach(s -> System.out.println(s));

		/*
		 * Stream API also provides a parallel stream which will work
		 * efficiently with a large collection if computer system got multiple
		 * cores.
		 */

		System.out.println();
		System.out.println("Printing using parallel stream along with a filter operation :");
		strSet.parallelStream()
		.filter(e -> e.length() == 4)
		.forEach(e -> System.out.println(e));

		System.out.println();
		System.out.println("Printing all the elements using parallel stream :");
		strSet.parallelStream()
		.forEach(e -> System.out.println(e));

		/*
		 * There are other methods provided as part of the stream API using
		 * which we can collect data and perform operations. For example, having
		 * a collection of string and want to join them using comma as shown in
		 * the below code
		 */

		System.out.println();
		System.out.println("Performing an aggregate operation over stream : ");
		String joined = strSet.stream()
				.collect(Collectors.joining(", "));
		System.out.println("Joined String --> " + joined);

	}

}

List interface

All classes which are child of List interface can also manage single set of elements like Set but unlike List allows duplicate
elements. List is an ordered collections as it stores the elements in a sequential order. List is a Collection and hence inherits the
methods from the Collection interface and allows to add, remove or traverse on the elements.

List Implementation Classes

• ArrayList : ArrayList is a dynamic array which store the objects in a sequential manner and in the contiguous memory locations.
  Internally uses an array to store the elements. ArrayList is the Most commonly used List implementation class.
  It can grow dynamically and can have duplicate elements. Like Array, ArrayList is also a random access data structure which can access the elements using index in O(1).
  Insertion and deletion worst time complexity is also like Array – O(n) as elements needs to be shifted.
• LinkedList : Like ArrayList, LinkedList also stores elements sequentially but elements are stored in the nodes that are scattered
  in the memory and may not be contiguous but are linked through references. LinkedList is not a random access data structure. To find an element, whole LinkedList need to traversed that makes the time
  complexity as O(n). Insertion and deletion operations are easier to perform than ArrayList.
  Java LinkedList can also be used as a Queue as it provides Queue data structure operations.
  LinkedList supports below operations for queue :
  add() - To add at the front of the LinkedList same as enqueue in Queue.
  poll() - To remove from the rear of the LinkedList same as the dequeue as in Queue.

Out of the above two List implementations. ArrayList is usually considered as the better performing implementation but
there are situations in which LinkedList can provided better performance. So which one to use depends on the type of the operations which we are going to perform on the list frequently.

List Interface Basic Operations

• size()- returns the cardinality(number of elements in the List) .
• isEmpty()- returns¬¬ true if it is empty.
• add() - adds the specified element if it is not present in the List.
• remove()- removes the passed element from the List.
• Iterator() - returns an Iterator for the List.

Apart from the operations provided from the Collection interface, List interface also provides the additional operations.
Some of them are below:
• Positional access or Index based access — List provides operations like get, set, add, addAll, and remove which can
operate on the basis of the position provided in the. i.e can add element at a particular position.
• Search — Search for the particular object in the list and in return get the index position of the element.
• Iteration — get the list specific iterator and traverse over the list.
• Range-view — The sublist method performs arbitrary range operations on the list.

Following program creates a List of Strings using ArrayList implementation class and perform basic operations add(), remove(),
isEmpty(), size() and iterates over it using an iterator.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ListTest {

	public static void main(String[] args) {
		
		List<String> strList=new ArrayList<String>();
		
		System.out.println("As of now List is empty so result for isEmpty() is : "+strList.isEmpty());
		System.out.println("Size of the List is Zero so result for size() is : "+strList.size());
		
		strList.add("Ram");
		strList.add("Ajit");
		strList.add("Bhanu");
		strList.add("Ram");//Adding duplicate element
		
		System.out.println();
		System.out.println("Added elements");
		System.out.println();
		
		System.out.println("After adding elements, result for isEmpty() is : "+strList.isEmpty());
		System.out.println("After adding elements, result for size() is : "+strList.size());

		System.out.println();
		System.out.println("Printing elements :");
		
		Iterator<String> itr = strList.iterator();
		//Printing all the List elements
		while (itr.hasNext()) {
			String string = (String) itr.next();
			System.out.println(string);
			if (string.equals("Ajit")) {
				itr.remove();//Removing "Ajit" from the list
			}
		}

		System.out.println();
		System.out.println("Printing the below strings from List after removal of \"Ajit\" :");
		//After removal of the string printing the List strings using for-each construct
		for (String string : strList) {
			System.out.println(string);
		}
	}
	
}

Traversing Through a List :

We can traverse a List using following three ways -

• for-each construct
• Iterators.
• Aggregate Operations

For-each allows to traverse an array or List using a loop. Using for-each we can go through each element and perform some
operation like printing the value for the element as shown in the below code snippet. In the below code, a collection to hold string has been prepared which uses an array list and using for-each construct traversing
and printing the array list values.

import java.util.ArrayList;
import java.util.List;

public class TraversalTestForEach {

	public static void main(String[] args) {
		List<String> strList=new ArrayList<String>();
		
		strList.add("Ram");
		strList.add("Ajit");
		strList.add("Bhanu");
		strList.add("Ram");
		
		for (String string : strList) {
			System.out.println(string);
		}	
	}
	
}

An Iterator object enables us to traverse through a List. Using iterator we can also remove the elements from the List. Using iterator() method from collection we can get the iterator for the collection and we can traverse through the collection.

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove(); //optional
}

Interator interface has got the following methods:

1. boolean hasNext() – returns true if iterator has more elements to be traversed
2. next() – returns the next element in the iteration
3. remove() – removes the last element from the List that was returned by the next. It can be called ony once after the next()
   has been called otherwise throws exception. Interator is the only safe way to modify the List(or any other collection)
   during iteration. In any other case unexpected events can happen.

Following is the code snippet to traverse List using iterator.

import java.util.Iterator;
import java.util.ArrayList;
import java.util.List;

public class TraversalTestIterator {
	public static void main(String[] args) {
		List<String> strList = new ArrayList<String>();
		strList.add("Ram");
		strList.add("Ajit");
		strList.add("Bhanu");
		strList.add("Ram");

		Iterator<String> itr = strList.iterator();

		while (itr.hasNext()) {
			String string = (String) itr.next();
			System.out.println(string);
		}
	}
}

JDK 8 release has introduced a new method which is also preferred method to traverse that is to obtain a stream over the List/collection and perform aggregate operations on it. Some of the aggregate operations are provided with the capability to use lambda expressions with them. Lambda expressions
provides the capability to pass the code as parameters in the form of functional interfaces. Lambda expressions make the
code short(lesser lines of code) and expressive.
The following code iterates through the List and prints the values:

import java.util.stream.Collectors;
import java.util.ArrayList;
import java.util.List;

public class TraversalUsingAggregateFun {

	public static void main(String[] args) {

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

		strList.add("Ram");
		strList.add("Ajit");
		strList.add("Bhanu");
		strList.add("Ram");

		/*
		 * JDK 8 release has introduced a new method which is also preferred
		 * method to traverse that is to obtain a stream over the collection and
		 * perform aggregate operations on it. Aggregate operations are provided
		 * with the capability to use lambda expressions with them. Lambda
		 * expressions provides the capability to pass the code as param,eters
		 * in the form of functional interfaces. Lambda expressions make the
		 * code short(lesser lines of code) and expressive. The following code
		 * iterates through the collection and prints the values:
		 */

		/*
		 * In the below code, first we are getting the stream on the collection
		 * and traversing using the forEach() function and within the function
		 * paasing a Lambda Expression to print each element.
		 */

		System.out.println("Printing using stream along with a filter operation :");
		strList.stream()
		.filter(e -> e.length() == 4)
		.forEach(e -> System.out.println(e));

		System.out.println();
		System.out.println("Printing all the elements using stream :");
		strList.stream()
		.forEach(s -> System.out.println(s));

		/*
		 * Stream API also provides a parallel stream which will work
		 * efficiently with a large collection if computer system got multiple
		 * cores.
		 */

		System.out.println();
		System.out.println("Printing using parallel stream along with a filter operation :");
		strList.parallelStream()
		.filter(e -> e.length() == 4)
		.forEach(e -> System.out.println(e));

		System.out.println();
		System.out.println("Printing all the elements using parallel stream :");
		strList.parallelStream()
		.forEach(e -> System.out.println(e));

		/*
		 * There are other methods provided as part of the stream API using
		 * which we can collect data and perform operations. For example, having
		 * a collection of string and want to join them using comma as shown in
		 * the below code
		 */

		System.out.println();
		System.out.println("Performing an aggregate operation over stream : ");
		String joined = strList.stream()
				.collect(Collectors.joining(", "));
		System.out.println("Joined String --> " + joined);

	}

}

Map interface

A Map is a collection that keeps key-value pairs. Using a map we can map keys to values.
A map cannot have have duplicate keys and a key can map to only one value.

Map implementation classes :

Map has implementation classes - HashMap, TreeMap and LinkedHashMap.
In HashMap oredering of the elements is not preserved, while in LinkedHashMap oredering of the elements is preserved on the basis of the inserson. In TreeMap, key-value pair is maintained in the ascending sorting order of the key. To add an object as a key to the
TreeMap that class should implement Comparable interface which in turn forces to implement compareTo() method
which in turn contains the sorting order definition.
We also have Thread Safe implementations for HashMap - SynchronizedHashMap and ConcurrentHashMap

Map Interface Basic Operations

• put() - To add the key-value pair in the Map.
• get() – To get the value corresponding to the key. Key is passed to this method and value is returned.
• containsKey() – To check if the given key exits in the Map.
• containsValue() – To check if the given value exists in the Map.
• size() – To check the size of the Map i.e how many key-value pair exists in the Map.
• isEmpty() – To check if the Map is empty.

In the below sample program, using a map to store "name" and "country" values pairs. "name" is the key to the map and "country" is the value. After storing, printing the values corresponding to the keys one by one.

import java.util.HashMap;
import java.util.Map;


public class MapTest {

	
	
	public static void main(String[] args) {
	
		Map<String, String> nameCountryMap = new HashMap<String, String>();
		
		//using put() method to store name(key) and country(value) values 
		nameCountryMap.put("Ram", "India");
		nameCountryMap.put("John", "Jermany");
		nameCountryMap.put("Nick", "USA");
		
		String country = nameCountryMap.get("Ram");
		System.out.println("Ram's country is "+country);
		
		country = nameCountryMap.get("John");
		System.out.println("John's country is "+country);
		
		country = nameCountryMap.get("Nick");
		System.out.println("Nick's country is "+country);
		
	}
	
}

Traversing Through a Map :

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;

public class TraverseMapUsingEntrySet {
	public static void main(String args[]) {
		// creating hash map
		HashMap<Integer, String> map = new HashMap<Integer, String>();

		// Adding key-value pairs to the HashMap
		map.put(1, "India");
		map.put(2, "US");
		map.put(3, "UK");
		map.put(4, "China");

		Set<Entry<Integer, String>> entrySet = map.entrySet();
		//Using entrySet we can iterate over key-value pairs using 
		//for-each construct or iterator or aggregate functions
		
		//Iterating using for-each construct
		for (Entry<Integer, String> entry : entrySet) {
			System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
		}

		System.out.println();
		
		//Traversing using iterator
		Iterator<Entry<Integer, String>> itr=entrySet.iterator();
		while (itr.hasNext()) {
			Entry<Integer,String> entry = (Entry<Integer,String>) itr.next();
			System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
		}
		
	}
}

import java.util.HashMap;
import java.util.Set;
public class TraversalUsingKeySet {
	public static void main(String args[]) {
		// creating hash map
		HashMap<Integer, String> map = new HashMap<Integer, String>();

		// Adding key-value pairs to the HashMap
		map.put(1, "India");
		map.put(2, "US");
		map.put(3, "UK");
		map.put(4, "China");

		Set<Integer> keySet = map.keySet();
		for (Integer key : keySet) {
			
			System.out.println("Key = "+key+", Value = "+map.get(key));
		}
	}
}

Collection Implementation Classes

Set implementation classes.

• HashSet: Internally uses a hash table to store the elements. It does not make any guarantee of the ordering of the
  elements as traversal can give you a different order than the oreder of insertion but provides the best performance in all
  the implementations of set. So when the ordering of the elements does not matter, it is the best set implementation for use.
• TreeSet: Intyernally uses a red-black tree to store the elements. TreeSet orders its elements on the baisis of a
  natural sorting order or any sorting order passed to Comparable.
• LinkedHashSet: Internally uses a hash table with a linked list implementation. Maintains the order of the elements
  on the baisis of the insertion order. Lateral traversal will give you the order as the order of insertion. So if you need to maintain the order of insertion then it saves you from the unexpected ordering of the HashSet.

List implementation classes.

• ArrayList : ArrayList is a dynamic array which store the objects in a sequential manner and in the contiguous memory locations.
  Internally uses an array to store the elements. ArrayList is the Most commonly used List implementation class.
  It can grow dynamically and can have duplicate elements. Like Array, ArrayList is also a random access data structure which can access the elements using index in O(1).
  Insertion and deletion worst time complexity is also like Array – O(n) as elements needs to be shifted.
• LinkedList : Like ArrayList, LinkedList also stores elements sequentially but elements are stored in the nodes that are scattered
  in the memory and may not be contiguous but are linked through references. LinkedList is not a random access data structure. To find an element, whole LinkedList need to traversed that makes the time
  complexity as O(n). Insertion and deletion operations are easier to perform than ArrayList.
  Java LinkedList can also be used as a Queue as it provides Queue data structure operations.
  LinkedList supports below operations for queue :
  add() - To add at the front of the LinkedList same as enqueue in Queue.
  poll() - To remove from the rear of the LinkedList same as the dequeue as in Queue.

Map implementation classes.

In HashMap oredering of the elements is not preserved, while in LinkedHashMap oredering of the elements is preserved on the basis of the inserson. In TreeMap, key-value pair is maintained in the ascending sorting order of the key. To add an object as a key to the
TreeMap that class should implement Comparable interface which in turn forces to implement compareTo() method
which in turn contains the sorting order definition.
We also have Thread Safe implementations for HashMap - SynchronizedHashMap and ConcurrentHashMap