JAVA Collections and Time Complexities

A Collection is a group of objects. Java collection framework helps us with storing and manipulating collections. We can have a collection of students, cars, players,etc. The various interfaces and their implementation classes can be seen below in the image.

Image source : chercher.tech

Important interfaces in the framework :

1. List : Its preserves the order and can store duplicate values.
2. Set : It doesn’t preserve the order and duplicate values are not stored.
3. Queue : It preserves the order and follows the FIFO principle.
4. Map : It stores the objects as Key, Value pairs in the form of entries.

All these interfaces provide us with implementation classes and methods that we can use to make a collection. But how to choose one?

Which INTERFACE to choose?

Image Source : javatutorial.net

Simply put, if you want to want to store key, value pairs then go for Map. If you want to store duplicate values then go for List otherwise go for Set interface. If you want sequential access to the data then go for Queue interface.

Which IMPLEMENTATION class to choose?

Choosing a class for our collection is dependent on the developer’s purpose. The several operations like addition, deletion, search ,etc, they all are performed in different ways by the various implementation classes. For eg, Search operation in an ArrayList is faster as compared to a LinkedList whereas LinkedList would be preferred over ArrayList if deletion is frequent and at any position in the collection. This leaves us a question How to choose one?

To help you with this question i think we should first get comfortable with the Big O notation. It tells us how the runtime of a program grows with the size of the input. It gives the Worst Case scenario means it will tell us the maximum time our program is gonna take for any operation. If an opeartion is done in constant time, its Big O notation would be O(1) whereas O(n) simply means that the runtime is directly proportional to the size of the input linearly.

The below graph depicts the time complexities for the various operations of the implentation classes.

List                 get  add  contains next remove 
ArrayList            O(1) O(1) O(n)     O(1) O(n)    
LinkedList           O(n) O(1) O(n)     O(1) O(1)      

Set                   add      contains next     
HashSet               O(1)     O(1)     O(h/n)   h -> table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)

Map                   get      containsKey next     
HashMap               O(1)     O(1)        O(h/n) h - > table                    capacity  
LinkedHashMap         O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 

Queue                 offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)


                     Image source : stack overflow

With the help of above diagram we can compare the time complexities of the various operations and then depending on our purpose can choose the implementation class for collection in our program.