Time Complexity of Java Collections | Code Factory

Donate : Link

Medium Blog : Link

Applications : Link

Usually, when we talk about time complexity, we refer to Big-O notation. Simply put, the notation describes how the time to perform the algorithm grows with the input size.

1. List

1.1 ArrayList

• add() – takes O(1) time; however, worst-case scenario, when a new array has to be created and all the elements copied to it, it’s O(n)
• add(index, element) – on average runs in O(n) time
• get() – is always a constant time O(1) operation
• remove() – runs in linear O(n) time. We have to iterate the entire array to find the element qualifying for removal.
• indexOf() – also runs in linear time. It iterates through the internal array and checks 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’ll also run in O(n) time.

3.2. 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)

3.3. LinkedList

• add() – appends an element to the end of the list. It only updates a tail, and therefore, it’s O(1) constant-time complexity.
• add(index, element) – on average runs in O(n) time
• get() – searching for an element takes O(n) time.
• remove(element) – to remove an element, we first need to find it. This operation is O(n).
• remove(index) – to remove an element by index, we first need to follow the links from the beginning; therefore, the overall complexity is O(n).
• contains() – also has O(n) time complexity

Map

• With the latest JDK versions, we’re witnessing significant performance improvement for Map implementations, such as replacing the LinkedList with the balanced tree node structure in HashMap, and LinkedHashMap internal implementations. This shortens the element lookup worst-case scenario from O(n) to O(log(n)) time during the HashMap collisions.
• Storing and retrieving elements from the HashMap takes constant O(1) time.
• For containsKey, get, put and remove methods, we have O(1) for HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap and ConcurrentHashMap.

Set

• For HashSet, LinkedHashSet, and EnumSet, the add(), remove() and contains() operations cost constant O(1) time thanks to the internal HashMap implementation.
• Likewise, the TreeSet has O(log(n)) time complexity for the add(), remove() and contains(). This is because of the TreeMap implementation. The time complexity for ConcurrentSkipListSet is also O(log(n)) time, as it’s based in skip list data structure.
• For CopyOnWriteArraySet, the add(), remove() and contains() methods have O(n) average time complexity.