Time complexity analysis wrt Collection API in Java.

5 min readNov 16, 2020

In this article, we’ll talk about the performance of different collections from the Java Collection API. When we talk about collections, we usually think about the List, Map, and Set data structures and their common implementations.

Let’s look at Big-O complexity insights for common operations. I preferred writing the average case and the best case complexities in this article.

1. List

Let’s start with a simple list — which is an ordered collection.

Here, we’ll have a look at a performance overview of the ArrayList, LinkedList, and CopyOnWriteArrayList implementations.

1.1. ArrayList:

The ArrayList in Java — Preserves insertion order.

So, let’s first focus on the time complexity of the common operations, at a high level:

add() — takes O(1) time.
add(index, element) — on average runs in O(n) time.
get() — is always a constant time O(1) operation, also ArrayList being a class implementing RandomAccess interface have a large advantage in fetching elements.
remove(int index) — runs in linear O(n) time. We have to iterate the entire array to find the element for removal.
indexOf() — also runs in linear time. It iterates through the internal array and checking each element one by one. So the time complexity for this operation always requires O(n) time.
contains() — implementation is based on indexOf(). So it will also run in O(n) time.

1.2. LinkedList:

LinkedList — uses a doubly-linked list as its underlying data structure.

Let’s present the average estimate of the time we need to perform some basic operations:

add() — supports O(1) constant-time insertion at any position.
get() — searching for an element takes O(n) time.
remove() — removing an element also takes O(1) operation, as we provide the position of the element.
contains() — also has O(n) time complexity.

1.3. CopyOnWriteArrayList

CopyOnWriteArrayList — very useful when working with multi-threaded applications and is a threadsafe version of ArrayList.

Here’s the performance Big-O notation overview for CopyOnWriteArrayList:

add() — depends on the position we add value, so the complexity is O(n).
get() — is O(1) constant-time operation.
remove() — takes O(n) time.
contains() — likewise, the complexity is O(n).

As we can see, using this collection is very expensive because of the performance characteristics of the add() method.

2. Set

Let’s move onto the Set — which is a collection of unique elements.

2.1. HashSet

HashSet — uses a Hash table as its underlying data structure and doesn’t preserve insertion order due to the insertion based on the hashcode of objects.

add() —insertion takes O(1) constant-time.
contains() — searching for an element takes O(1) time.
next() — fetching an element takes O(h/n) time, where ‘h’ is table capacity.

2.2. LinkedHashSet

LinkedHashSet — uses a Hash table as its underlying data structure and preserves insertion order.

add() — insertion takes O(1) constant-time.
contains() — searching for an element takes O(1) time.
next() — fetching an element takes O(1) time.

2.3. CopyOnWriteArraySet:

CopyOnWriteArraySet— very useful when working with multi-threaded applications and is a threadsafe version of Set which also preserves insertion order.

add() — insertion takes O(n) constant-time.
contains() — searching for an element takes O(n) time.
next() — fetching each element takes O(1) time.

2.4. TreeSet:

TreeSet — which uses default natural sorting order by default.

add() — insertion takes O(log n) constant-time.
contains() — searching for an element takes O(log n) time.
next() — fetching each element takes O(log n) time.

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
TreeSet               O(log n) O(log n) O(log n)

3. Map

Let’s move onto the Map— which is a collection of key-value pairs.

3.1. HashMap

HashMap — uses a Hash table as its underlying data structure.

get() — retrieving value takes O(1) constant-time.
containsKey() — searching for an element takes O(1) time.
next() — fetching an element takes O(h/n) time, where ‘h’ is table capacity.

3.2. LinkedHashMap

LinkedHashMap— uses a Hash table as its underlying data structure and preserves insertion order.

get() — retrieving takes O(1) constant-time
containsKey() — searching for an element takes O(1) time
next() — fetching an element takes O(1) time.

3.3. IdentityHashMap

IdentityHashMap — uses a Hash table as its underlying data structure.

get() — retrieving takes O(1) constant-time
containsKey() — searching for an element takes O(1) time
next() — fetching an element takes O(h/n) time, where ‘h’ is table capacity.

3.4. ConcurrentHashMap:

ConcurrentHashMap— very useful when working with multi-threaded applications and is a threadsafe version of Map which uses HashMap.

get() —retrieving takes O(1) constant-time.
containsKey() — searching for an element takes O(1) time.
next() — fetching each element takes O(h/n), where ‘h’ is table capacity.

3.5. TreeMap:

TreeMap— which uses default natural sorting order, by default based on keys.

get() — retrieving takes O(log n) constant-time.
containsKey() — searching for an element takes O(log n) time.
next() — fetching each element takes O(log n) time.

                      get      containsKey next    
HashMap               O(1)     O(1)        O(h/n)   
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)  
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)

4. Queue:

4.1. PriorityQueue:

PriorityQueue— which uses the priority heap data structure.

offer() —Insertion takes O(log n) constant-time, due to the usage of heap data structure.
peek() — fetching head element takes O(1) time.
poll() — fetch and delete each head element takes O(log n) time.
size() — Calculating, size of the queue takes O(1) time.

4.2. ArrayBlockingQueue:

ArrayBlockingQueue class — it is a bounded blocking queue backed by an array. By bounded, it means that the size of the Queue is fixed.

offer() — Insertion takes O(1) constant-time, due to the usage of the Array internally.
peek() — fetching head element takes O(1) time.
poll() — fetch and delete each head element takes O(1) time.
size() — Calculating, size of the queue takes O(1) time.

4.3. LinkedBlockingQueue:

LinkedBlockingQueue — optionally-bounded blocking queue based on linked nodes.

offer() — Insertion takes O(1) constant-time, due to insertion at the tail.
peek() — fetching head element takes O(1) time.
poll() — fetch and delete each head element takes O(1) time.
size() — Calculating, size of the queue takes O(1) time.

4.4. PriorityBlockingQueue:

PriorityQueue —is an unbounded blocking queue that uses the same ordering rules as class PriorityQueue and supplies blocking retrieval operations.

offer() — Insertion takes O(log n) constant-time, due to the usage of heap data structure.
peek() — fetching head element takes O(1) time.
poll() — fetch and delete each head element takes O(log n) time.
size() — Calculating, size of the queue takes O(1) time.

4.5. ArrayDeque:

ArrayDeque — provides a way to apply resizable-array in addition to the implementation of the Deque interface. This is a special kind of array that grows and allows users to add or remove an element from both sides of the queue!

offer() — Insertion takes O(1) constant-time, due to the usage of the Array internally.
peek() — fetching head element takes O(1) time.
poll() — fetch and delete each head element takes O(1) time.
size() — Calculating, size of the queue takes O(1) time.

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)

You have reached the end, catch you guys in the next article!