Make the best choice for application performance by learning Java Collections Framework

Bad programmers worry about the code. Good programmers worry about data structures and their relationships. — Linus Torvalds

The Java collections framework is a set of classes and interfaces for implementing a commonly used collection data structure. Examples include lists, queues, etc.

Because these collections are well tested, we do not have to implement every algorithm and data structure from scratch.

Almost all collections except the map can be derived from the java.util.Collection interface. The toArray() method converts any Collection into a one-dimensional array. We can use the for-each loop because the Collection interface extends the java.lang.Iterable interface.

The data structure allows us to store and manipulate data efficiently. With proper data structure selection, we can make algorithms faster. Without the proper data structure (PriorityQueue) , we cannot solve Dijkstra’s shortest path problem in O((E+V)LogV) rather it will take O(V2) when List is used.

Therefore, data structures have a significant impact on the final performance of the software. Let’s examine them in more detail.

List

• The List interface is an ordered collection that allows us to store and access items in a sequential manner.
• It extends the Collection interface which extends the Iterable interface.
• Lists can include duplicate elements.
• It gives the user full visibility and control over the ordering of its elements.

ArrayList

• Resizable-array implementation of the List interface.
• This class is roughly equivalent to Vector, except that it is unsynchronized.
• Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. As elements are added to an ArrayList, its capacity grows automatically.
• Random access with index takes O(1) time complexity.
• Insertion/deletion at the given index takes O(N) time complexity.

package com.democollections;
	

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

public class MyArrayList {
	

	public static void main(String[] args) {
		List<String> animals = new ArrayList<>();
		animals.add("Elephant");
		animals.add("Lion");
		animals.add("Tiger");
			
		// Random access - O(1)
		System.out.println(animals.get(2));
			
		// Insert item into a given index - O(N)
		animals.add(0,"Monkey");
			
		// Delete item into a given index - O(N)
		animals.remove(0);
			
		//NOTE: Insertion/Deletion at the end is faster compared to other index
			
		// Because of the Iterable interface
		for(String animal: animals) {
			System.out.println(animal);
		}
	

	}
	

}        

LinkedList

• Doubly-linked list implementation of the List and Deque interfaces.
• This implementation is not synchronized
• Since the items are not stored next to each other in the memory, so there is no random access.
• Manipulation (insertion/deletion) of the first & last item will take O(1) time complexity.
• Manipulating an arbitrary item will O(N) time complexity.

package com.democollections;
	

import java.util.LinkedList;
	

public class MyLinkedList {
	

	public static void main(String[] args) {
		LinkedList<String> animals = new LinkedList<>();
		animals.add("Horse");
		animals.add("deer");
		animals.add("snake");
	

		// Access item - O(N)
		System.out.println(animals.get(1));
	

		// Insert/Delete item at start/end - O(1)
		animals.addFirst("Lion");
		animals.addLast("Elephant");
		animals.removeFirst();
		animals.removeLast();
	

		// Insert/Delete item at a given index - O(N)
		animals.remove(2);
		animals.add(2, "Rhino");
	

		// Because of the Iterable interface
		for (String animal : animals) {
			System.out.println(animal);
		}
	

	}
	

}        

ArrayList vs LinkedList Performance

Let’s see the performance of ArrayList and LinkedList when insertion happens at the start of the list.

package com.democollections;
	

import java.util.ArrayList;
import java.util.LinkedList;
	

public class ArrayListLinkedListPerformance {
	

	public static void main(String[] args) {
		ArrayList<Integer> array = new ArrayList<>();
		long before = System.currentTimeMillis();
		for (int i = 0; i < 100000; i++) {
			array.add(0, i);
		}
		long after = System.currentTimeMillis();
		System.out.println("Time taken by ArrayList : " + (after - before));
	

		LinkedList<Integer> llist = new LinkedList<>();
		before = System.currentTimeMillis();
		for (int i = 0; i < 100000; i++) {
			llist.addFirst(i);
		}
		after = System.currentTimeMillis();
		System.out.println("Time taken by LinkedList : " + (after - before));
	}
	

}
        

// Output on my system
Time taken by ArrayList : 519
Time taken by LinkedList : 4        

LinkedList performance is way better than ArrayList as no data shift happened.

Vector

• Vector is similar to ArrayList but it's synchronized.
• If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.

Stack

• The Stack class represents a last-in-first-out (LIFO) stack of objects.
• It is an abstract data type and it can be implemented either with an ArrayList or with a LinkedList.
• Basic operations are push(), pop() and peek().
• A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.
• Graph algorithms rely heavily on stacks such as depth-first search.
• Finding Eulerial cycles in a G(V, E) graph.
• Finding strongly connected components in a given G(V, E) graph.
• Processing function call.

package com.democollections;
	

import java.util.Stack;
	

public class MyStack {
	

   public static void main(String[] args) {
		Stack<String> animals = new Stack<>();
		// LIFO
		animals.push("Elephant");
		animals.push("Lion");
		animals.push("Tiger");
			
		System.out.println("Size: " + animals.size());
		System.out.println("Peek Element: " + animals.peek());
		System.out.println("Size: " + animals.size());
		System.out.println("Pop Element: " + animals.pop());
		System.out.println("Size: " + animals.size());
			
		while(!animals.isEmpty()) {
		   System.out.println(animals.pop());
		}
	

	}
	

}        

// Output
Size: 3
Peek Element: Tiger
Size: 3
Pop Element: Tiger
Size: 2
Lion
Elephant        

Stack extends the Vector class which means that stacks are inherently synchronized. However, if synchronization is not needed, in that case, prefer using ArrayDeque.

Queues

• A collection designed for holding elements prior to processing.
• It is an abstract data type and it can be implemented either with an ArrayList or a LinkedList.
• Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements natural ordering.
• Graph algorithm breadth-first search use queue as an underlying abstract data type.
• Threads are stored in queues.
• CPU scheduling uses queues.
• Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, and the other returns a special value.

package com.democollections;
	

import java.util.LinkedList;
import java.util.Queue;
	

public class MyQueue {
	

	public static void main(String[] args) {
		Queue<String> animals = new LinkedList<>();
	    // FIFO
		animals.add("Elephant");
		animals.add("Lion");
		animals.add("Tiger");
	

		System.out.println("Size: " + animals.size());
		System.out.println("Check Element: " + animals.element());
		System.out.println("Size: " + animals.size());
		System.out.println("Remove Element: " + animals.remove());
		System.out.println("Size: " + animals.size());
	

		for (String animal : animals) {
			System.out.println(animal);
		}
	

	}
	

}        

//Output
Size: 3
Check Element: Elephant
Size: 3
Remove Element: Elephant
Size: 2
Lion
Tiger        

PriorityQueue

• A priority queue is based on a priority heap.
• The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
• A priority queue does not permit null elements.

package com.democollections;
	

import java.util.PriorityQueue;
import java.util.Queue;
	

public class MyPriorityQueue {
	

	public static void main(String[] args) {
		Queue<String> animals = new PriorityQueue<>();
		
		animals.add("Panda");
		animals.add("Deer");
		animals.add("Monkey");
	

		for (String animal : animals) {
			System.out.println(animal);
		}
	

	}
	

}        

// Output
Deer
Panda
Monkey        

Deque

• A linear collection that supports element insertion and removal at both ends. The name deque is short for “double-ended queue”.
• This interface defines methods to access the elements at both ends of the deque.
• This interface extends the Queue interface. When a deque is used as a queue, FIFO (First-In-First-Out) behavior results. Elements are added at the end of the deque and removed from the beginning.
• Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque.

ArrayDeque

• Resizable-array implementation of the Deque interface.
• They are not thread-safe.
• Null elements are prohibited.
• This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

package com.democollections;
	

import java.util.ArrayDeque;
import java.util.Deque;
	

public class MyArrayDequeQueue {
	

	public static void main(String[] args) {
		// Double ended queue - Deque
			
		// FIFO - Queue
		Deque<String> animalsQueue = new ArrayDeque<>();
	

		animalsQueue.addLast("Panda");
		animalsQueue.addLast("Deer");
		animalsQueue.addLast("Monkey");
	

		while (!animalsQueue.isEmpty()) {
			System.out.println(animalsQueue.removeFirst());
		}
	

	}
	

}        

// Output
Panda
Deer
Monkey
        

package com.democollections;
	

import java.util.ArrayDeque;
import java.util.Deque;
	

public class MyArrayDequeStack {
	

	public static void main(String[] args) {
	    // Double ended queue - Deque
			
		// LIFO - Stack
		Deque<String> animalsStack = new ArrayDeque<>();
	

		animalsStack.addFirst("Panda");
		animalsStack.addFirst("Deer");
		animalsStack.addFirst("Monkey");
	

		while (!animalsStack.isEmpty()) {
			System.out.println(animalsStack.removeFirst());
		}
	

	}
	

}        

// Output
Monkey
Deer
Panda        

ArrayDeque vs Stack Performance

Because Stack is synchronized as it extends the Vector class this is why it is going to be slower than the ArrayDequeue. So it's advisable to use ArrayDeque if we want a LIFO structure.

package com.democollections;
	

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
	

public class MyArrayDequeStackPerformance {
	

	public static void main(String[] args) {
		Deque<Integer> stack = new ArrayDeque<>();
		long before = System.currentTimeMillis();
		for (int i = 0; i < 100000; i++) {
			stack.push(i);
		}
	

		while (!stack.isEmpty()) {
			stack.pop();
		}
	

		long after = System.currentTimeMillis();
		System.out.println("Time taken with ArrayDeque: " + (after - before) + "ms");
	

		Stack<Integer> stackObj = new Stack<>();
		before = System.currentTimeMillis();
		for (int i = 0; i < 100000; i++) {
			stackObj.push(i);
		}
	

		while (!stackObj.isEmpty()) {
			stackObj.pop();
		}
		after = System.currentTimeMillis();
		System.out.println("Time taken with Stack: " + (after - before) + "ms");
	

	}
	

}        

// Output on my system
Time taken with ArrayDeque: 9ms
Time taken with Stack: 14ms        

Set

• Set are abstract data types that can store certain values without any particular order.
• Set contains no repeated values or duplicates.

HashSet

• This class implements the Set interface, backed by a hash table (actually a HashMap instance).
• It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.
• This class permits the null element.

package com.democollections;
	

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

public class MyHashSet {
	

	public static void main(String[] args) {
		// O(1), in case of collision - O(logN)
		Set<String> animals = new HashSet<>();
		animals.add("Elephant");
		animals.add("Tiger");
		animals.add("Lion");
		animals.add("Tiger");
	

		for (String animal : animals) {
			System.out.println(animal);
		}
	

	}
	

}        

// Output
Elephant
Lion
Tiger        

LinkedHashSet

• Hash table and linked list implementation of the Set interface, with predictable iteration order.
• This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries.
• A linked hash set has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashSet.

package com.democollections;
	

import java.util.LinkedHashSet;
import java.util.Set;
	

public class MyLinkedHashSet {
	

	public static void main(String[] args) {
		// LinkedHashSet maintains the insertion order
		// Doubly linked list is used
		Set<String> animals = new LinkedHashSet<>();
		animals.add("Elephant");
		animals.add("Tiger");
		animals.add("Lion");
		animals.add("Tiger");
	

		for (String animal : animals) {
			System.out.println(animal);
		}
	

	}
	

}        

// Output
Elephant
Tiger
Lion        

SortedSet

• A Set that further provides a total ordering of its elements.
• The elements are ordered using their natural ordering, or by a Comparator typically provided at a sorted set creation time.
• All elements inserted into a sorted set must implement the Comparable interface

TreeSet

• A NavigableSet implementation based on a TreeMap.
• The elements are ordered using their natural ordering, or by a Comparator provided at a set creation time, depending on which constructor is used.
• This implementation provides guaranteed log(n) time cost for the basic operations (add, remove, and contains).

package com.democollections;
	

import java.util.SortedSet;
import java.util.TreeSet;
	

public class MyTreeSet {
	

	public static void main(String[] args) {
	

		// O(logN) - Underlying data structure is Red-Black tree
		SortedSet<String> animals = new TreeSet<>();
		animals.add("Elephant");
		animals.add("Tiger");
		animals.add("Lion");
		animals.add("Monkey");
	

		for (String animal : animals) {
			System.out.println(animal);
		}
	

	}
	

}        

// Output
Elephant
Lion
Monkey
Tiger        

HashSet vs LinkedHashSet vs TreeSet

• HashSet and LinkedHashSet rely heavily on a one-dimensional array and a hash function.
• HashSet and LinkedHashSet have an average time complexity of O(1) but on collision, it can be O(N).
• HashSet and LinkedHashSet can store null keys as well.
• LinkedHashSet uses a doubly-linked list data structure in addition to maintaining insertion order.
• TreeSet uses a balanced binary search tree and its time complexity is O(logN).
• TreeSet cannot store null keys.
• TreeSet uses less memory compared to HashSet/LinkedHashSet.

Map

• An object that maps keys to values.
• A map cannot contain duplicate keys; each key can map to at most one value.
• This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.

Hashtable

• This class implements a hash table, which maps keys to values.
• Any non-null object can be used as a key or as a value.
• To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.
• An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.
• Hashtable is similar to HashMap but it’s synchronized so it’s thread-safe.

HashMap

• Hash table based implementation of the Map interface.
• The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.
• An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.
• The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

package com.democollections;
	

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

public class MyHashMap {
	

	public static void main(String[] args) {
	

		Map<Integer, String> animalsMap = new HashMap<>();
		// Insert takes O(1) if there are no collision
		animalsMap.put(1, "Elephant");
		animalsMap.put(10, "Tiger");
		animalsMap.put(25, "Lion");
			
		// Removes takes O(1)
		animalsMap.remove(25);
			
		// Retrieve value based on key takes O(1)
		System.out.println(animalsMap.get(10));
	

		for (Map.Entry<Integer, String> entry : animalsMap.entrySet()) {
			System.out.println(entry.getKey() + ":" + entry.getValue());
		}
	}
	

}        

// Output
Tiger
1:Elephant
10:Tiger        

LinkedHashMap

• Hash table and linked list implementation of the Map interface, with predictable iteration order.
• This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.
• This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
• A linked hash map has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashMap.

package com.democollections;
	

import java.util.LinkedHashMap;
import java.util.Map;
	

public class MyLinkedHashMap {
	

	public static void main(String[] args) {
		// There is doubly linked list connecting the inserted items
		Map<Integer, String> animalsMap = new LinkedHashMap<>();
		// Insertion order is preserved 
		animalsMap.put(1, "Elephant");
		animalsMap.put(20, "Tiger");
		animalsMap.put(3, "Lion");
		animalsMap.put(40, "Deer");
		animalsMap.put(5, "Monkey");
		animalsMap.put(60, "Panda");
	

		for (Map.Entry<Integer, String> entry : animalsMap.entrySet()) {
			System.out.println(entry.getKey() + ":" + entry.getValue());
		}
	}
	

}        

// Output
1:Elephant
20:Tiger
3:Lion
40:Deer
5:Monkey
60:Panda        

TreeMap

Before we talk about TreeMap let's first understand the binary search trees.

• ArrayList can manipulate the last item in O(1) constant time complexity.
• LinkedList can manipulate the first item of the data structure fast.
• Searching for an arbitrary item takes O(N) linear running time for both ArrayList and LinkedList.

What if the array data structure is sorted?

We can search for an arbitrary item in O(logN) time complexity, which is the concept behind the binary search.

Binary Search Trees

• Every node in the tree can have at most 2 children (left and right)
• The left child is smaller than the parent node.
• The right child is greater than the parent node.
• We can access the root node exclusively and all other nodes can be accessed via the root node.

Red-Black Trees

• It is a balanced data structure that has a guaranteed O(logN) time complexity.
• The time complexity of binary search trees depends on the height of the binary search tree.
• AVL trees are faster than red-black trees because they are more rigidly balanced but need more work.
• It’s faster to construct a red-black tree and many operating systems rely on it.

TreeMap

• A Red-Black tree-based NavigableMap implementation.
• The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
• This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

package com.democollections;
	

import java.util.Map;
import java.util.TreeMap;
	

public class MyTreeMap {
	

	public static void main(String[] args) {
	

		Map<Integer, String> animalsMap = new TreeMap<>();
	    // Items will inserted in sorted order based on key
		animalsMap.put(1, "Elephant");
		animalsMap.put(20, "Tiger");
		animalsMap.put(3, "Lion");
		animalsMap.put(40, "Deer");
		animalsMap.put(5, "Monkey");
		animalsMap.put(60, "Panda");
	

		for (Map.Entry<Integer, String> entry : animalsMap.entrySet()) {
			System.out.println(entry.getKey() + ":" + entry.getValue());
		}
	}
	

}        

// Output
1:Elephant
3:Lion
5:Monkey
20:Tiger
40:Deer
60:Panda        

HashMap vs TreeMap performance

package com.democollections;
	

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

public class MyHashMapTreeMapPerformance {
	

	public static void main(String[] args) {
		// O(logN)
		Map<Integer, Integer> treemap = new TreeMap<>();
	

		long before = System.currentTimeMillis();
		for (int i = 0; i < 100000; i++) {
			treemap.put(i, i);
		}
		for (int i = 0; i < 100000; i++) {
			treemap.get(i);
		}
		long after = System.currentTimeMillis();
		System.out.println("Time taken with TreeMap: " + (after - before) + "ms");
	

		// O(1)
		Map<Integer, Integer> hashmap = new HashMap<>();
	

		before = System.currentTimeMillis();
		for (int i = 0; i < 100000; i++) {
			hashmap.put(i, i);
		}
		for (int i = 0; i < 100000; i++) {
			hashmap.get(i);
		}
		after = System.currentTimeMillis();
		System.out.println("Time taken with HashMap: " + (after - before) + "ms");
	}
	

}        

// Output on my system
Time taken with TreeMap: 53ms
Time taken with HashMap: 22ms        

HashMap vs LinkedHashMap vs TreeMap

• HashMap and LinkedHashMap rely on a one-dimensional array and a hash function.
• So they have average-case time complexity of O(1) that can be O(N) because of collisions.
• LinkedHashMap uses a doubly-linked list data structure to maintain insertion order.
• TreeMap uses a balanced binary search tree and there are no collisions at all with the time complexity of O(logN).
• HashMap and LinkedHashMap can store null keys whereas TreeMap cannot store null keys.