Side note: Correct me if I'm wrong...

Hello everyone!

So recently I’ve been doing a lot of those code challenges to prepare for coding interviews and normally the language I choose to work with is Java, being the one I’m most comfortable and all (because of Android). And sometimes when you’re programming, in the heat of moment, in the zone, you forget to think about how the use of a certain data structure will influence the performance of your code. If you deal with small amounts of data that’s not quite relevant, but if you want to get serious about the amount of data points you’re working with, time complexity of a certain data structure class needed to be considered. So I dig up online a little table with the most used Data structure classes and their time complexities for adding elements, searching elements and removing elements. But first, let me clarify some terms:

  • Set, a collection of elements, of the same type, that does not contain duplicates.
  • List, an order sequence of elements, of the same type. It might contain duplicates.
  • Queue, as the name says it normally organizes elements in a FIFO manner.
  • Map, a data structure that maps keys to values.

Let’s start with lists (not all kinds of Java Class that implement the List interface are listed(pun not intended) here, only those I find more interesting:

Java Class Insert time Remove Time Search Time
ArrayList O(1) O(n) O(n)
LinkedList O(1) O(1) O(n)

 

Now with sets, once again not all of them are here:

Java Class Insert time Remove Time Search Time
HashSet O(1) O(1) O(1)
LinkedHashSet O(1) O(1) O(1)

 

Maps and queues:

Java Class Insert time Remove Time Search Time
HashMap O(1) O(1) O(1)

 

Java Class Insert time Remove Time Search Time
PriorityQueue O(logn) O(logn) O(1)

That’s it guys, next time you handle a lot of data keep an eye open for the best data structure to use. Stay wise 🙂

Categories: programming

Leave a Reply

Your email address will not be published. Required fields are marked *