A common pattern in an interview is to ask for a data structure that would store a collection of items. In Java, there are three types of objects that holds collection of data - Map, Set and List.
Here is a tip that would make sure that you choose an appropriate data type: Set should be your default choice. A choice for a List should be based on you reasoning yourself out of using a Set.
Why?
Set has this data structure called HashSet. It is super efficient. Let us see this table for CURD operations.
As you can see, HashSet is super-efficient in all cases.
When should I not use Set?
1. If your collection can allow duplicates
2. If you need to maintain an ordering of some kind.
Always use a Set by default. Set is wonderful.
Here is a tip that would make sure that you choose an appropriate data type: Set should be your default choice. A choice for a List should be based on you reasoning yourself out of using a Set.
Why?
Set has this data structure called HashSet. It is super efficient. Let us see this table for CURD operations.
| HashSet | ArrayList | LinkedList | |
|---|---|---|---|
| C - Add to Collection |
1
|
n
|
1
|
| R - Find in Collection |
1
|
lg n if sorted
n otherwise
|
n
|
| D - Remove from Collection |
1
|
n remove and move all elements
|
1 (finding will take n. but removing will be 1)
|
As you can see, HashSet is super-efficient in all cases.
When should I not use Set?
1. If your collection can allow duplicates
2. If you need to maintain an ordering of some kind.
Always use a Set by default. Set is wonderful.
No comments:
Post a Comment