Time and Space Complexity of Collections

The Java platform includes a collections framework. A collection is an object that represents a group of objects (such as the classic Vector class). A collections framework is a unified architecture for representing and manipulating collections, enabling collections to be manipulated independently of implementation details.

Following are the time complexities of different data structures and their implementations in the Collections framework.

List

LinkedList

Time

Linked lists have most of their benefit when it comes to the insertion and deletion of nodes in the list. Unlike the dynamic array, insertion and deletion at any part of the list takes constant time.

However, unlike dynamic arrays, accessing the data in these nodes takes linear time because of the need to search through the entire list via pointers. It’s also important to note that there is no way of optimizing search in linked lists. In the array, we could at least keep the array sorted. However, since we don’t know how long the linked list is, there is no way of performing a binary search

Insertion — O(1),Search — O(n).​Deletion — O(1),Indexing — O(n),

Space

Linked lists hold two main pieces of information (the value and pointer) per node. This means that the amount of data stored increases linearly with the number of nodes in the list. Therefore, the space complexity of the linked list is linear:

​Space — O(n)​.

ArrayList

Time

Inserting value at last or given index due to the added steps of creating a new array in ArrayList its worst-case complexity reaches to order of N, that is why we prefer using LinkedList where multiple inserts are required.

Searching : we have to iterate through all elements. This operation has O(N) time complexity.

Searching by indexing: ArrayList can give you any element in O(1) complexity as the array has random access property. You can access any index directly without iterating through the whole array.

Remove by value: To remove an element by value in ArrayList and LinkedList we need to iterate through each element to reach that index and then remove that value. This operation is of O(N) complexity.

Remove by index: To remove by index, ArrayList find that index using random access in O(1) complexity, but after removing the element, shifting the rest of the elements causes overall O(N) time complexity.

Set

HashSet, LinkedHashSet and TreeSet

time

Hashset is implemented using a hash table. elements are not ordered. the add, remove, and contains methods has constant time complexity o(1).

Treeset is implemented using a tree structure(red-black tree in algorithm book). the elements in a set are sorted, but the add, remove, and contains methods has time complexity of o(log (n)). it offers several methods to deal with the ordered set like first(), last(), headset(), tailset(), etc.

Linkedhashset is between hashset and treeset. it is implemented as a hash table with a linked list running through it, so it provides the order of insertion. the time complexity of basic methods is o(1).

Queue

Priority Deque

time

• Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)) time complexity to insert and delete element.
• Offer() and add() methods are used to insert the element in the in the priority queue java program.
• Poll() and remove() is used to delete the element from the queue.
• Element retrieval methods i.e. peek() and element(), that are used to retrieve elements from the head of the queue is constant time i.e. O(1).
• contains(Object)method that is used to check if a particular element is present in the queue, have leaner time complexity i.e. O(n).

Array Deque

time

In a doubly-linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).

Map

LinkedHashMap

time

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.

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.

TreeMap:

Java TreeMap class is a red-black tree based implementation. It provides an efficient means of storing key-value pairs in sorted order.

• 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.