# Time complexity of collection classes

The Java collection classes have different time complexity for each of the operations. While ArrayList can given you index based access in order, HashMap can give you key value pair storage without any ordering. TreeSet and TreeMap provide sorted order of elements present in them. Similarly for remove operation, one collection class may work better than the other due to the underlying structure of the class. Here is a ready reference for O(n) complexity of various commonly used Java collection classes.

Please note that for some of the collections which are ordered, time complexity has been shown for insertion/deletion in the beginning, middle and at the end. The complexity can be used as a criteria for using a collection class when multiple classes deem suitable for a purpose.

**Java ArrayList time complexity :**

Read/Search any element O(n). If you know the index then the complexity is O(1)

Update : O(n)

Delete at beginning: O(n)

Delete in middle: O(n)

Delete at end: O(n)

Add at beginning: O(n)

Add in middle: O(n)

Add at end: O(n)

**Linked List time complexity :** It has elements linked in one direction so as to provide ordered iteration of elements.

Read/Search any element O(n)

Update : O(n)

Delete at beginning: O(1)

Delete in middle: O(n)

Delete at end: O(n)

Add at beginning: O(1)

Add in middle: O(n)

Add at end: O(n)

**HashMap time complexity :** The elements are placed randomly as per the hashcode. Here the assumption is that a good implementation of hashcode has been provided.

Read/Search any element O(1)

Update : O(1)

Delete : O(1)

Add : O(1)

**LinkedHashMap time complexity :** The elements are placed randomly as with HashMap but are linked together to provide ordered iteration of elements.

Read/Search any element O(1)

Update : O(1)

Delete : O(1)

Add at beginning: O(1)

Add in middle: O(n)

Add at end: O(n)

**HashSet time complexity :** The elements are distributed randomly in memory using their hashcode. Here also the assumption is that good hashcode which generated unique hashcode for different objects has been provided.

Read/Search any element O(1)

Update : O(1)

Delete : O(1)

Add : O(1)

**LinkedHashSet time complexity :** It is same as HashSet with the addition of links between the elements of the Set.

Read/Search any element O(1)

Update : O(1)

Delete : O(1)

Add at beginning: O(1)

Add in middle: O(n)

Add at end: O(n)

**TreeMap time complexity :** Provides natural sorting of elements. Uses equals, compare and compareTo methods to determine the sorting order.

Read/Search any element O(log n)

Update : O(log n)

Delete : O(log n)

Add : O(log n)

**TreeSet time complexity :** Internally used an instances of TreeMap with the elements as key and a dummy value for all entries in the TreeMap.

Time complexity of collection classeshttp://www.javaexperience.com/time-complexity-of-collection-classes/ Core JavaRead/Search any element O(log n)

Update : O(log n)

Delete : O(log n)

Add : O(log n)