Which Java Collection to Use?

Whenever a person starts using Collection framework, the first thing that comes in his mind is “which collection to use?”. So, in this blog we are gonna understand, when to use a particular collection.

So, the first thing we need to consider is :- do you want a list, a set or a map, because those are the three main groupings of collections in java.

List

1. They store lists of objects, you can think of it like a shopping list.
2. Duplicates are allowed at lists you can have the same item down twice, just like you can in a a shopping list.
3. The objects remain in the order that you add them in the list(unless you sort them).
4. Elements in a list are indexed via an integer.
5. If you want to check for a particular item in a list using the item name, that is pretty slow because for checking if that item exist or not, it would have to iterate through the whole list.
6. Looking on the item up by index is fast.
7. Iterating through lists is relatively fast.
8. Remember you can sort the list if you want to.
9. The most common list to use is the ArrayList, it is only good if you want to add or remove thinks at the end of the list. But what if you want to add or remove items anywhere else in the list, that’s where LinkedList comes into picture.

Lets just take a view at both of its distinctive methods:-

First, lets take a look at ArrayList, which can only add items at the end of the list.

public class ArrayListDemo {
public static void main(String[] args) {
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(10);
al.add(20);
al.add(30);
System.out.println(al);
}
}
Output = [10, 20, 30]

Lets also look at the Big O notation for some of the operations of ArrayList.

Inserting : - If we think about the insertion operation, it is fairly simple, as the list keeps a variable for storing the size (number of the element in the list): we just have to insert the element in the cell with the index equal to the size. This is an O(1) operation.

Deleting :- At first look, it looks easy to calculate its complexity for example if we want to delete the element which is at the 4th index, we just have to remove it and that’s it which is like O(1), but what if we want to delete the element at 0th index, we will end up with empty cell before the occupied cells, so the arraylist will shift all the elements, so that there is no empty space in the beginning. So, clearly this shifting time will depend on the number of elements present and hence the Big O will be O(n), where n is the number of elements.

Searching :- For searching an element in a ArrayList, you have to traverse through the whole list which will depend on the number of elements(n) in the arraylist, and if we take the worst case scenario in which the elements in the last index then the Big O will be O(n).

Now, lets take a look at LinkedList, which can add objects at both sides of the list.

public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(10);
ll.addLast(40);
ll.addFirst(20);
System.out.println(ll);
}
}
Output = [20, 10, 40]

Lets also look at the Big O notation for some of the operations of LinkedList.

Inserting :- In linkedlist we can add the elements from both the ends, but luckily linkedlist holds the reference for both the ends of the list so inserting elements in it is almost like arraylist so the Big O for this is also O(1).

Deleting :- To delete an element we have to find it first, so we have to traverse the list, unless the element is the first or last element as we have special methods to delete them, but we have to look for the worst case scenario, so the Big O for this Operation clearly depends on the number of elements which can be represented by O(n).

Searching :- As we have seen in the deleting, that searching depends upon the number of elements present in the linkedlist, so the Big O for this operation is O(n).

Sets

1. Only store unique values.
2. Great for removing duplicates.
3. Not indexed, unlike lists.
4. Very fast to check if a particular object exists.
5. If you want to use your own objects, you must implement hashCode() and equals() method.

With sets there are three main types to choose from, HashSet is the default one but HashSet is not ordered, it stores objects in no particular order and the order is subject to changing seemingly at random.

public class HashSetDemo {
public static void main(String[] args) {
HashSet<Integer> hs = new HashSet<Integer>();
hs.add(10);
hs.add(20);
hs.add(30);
System.out.println(hs);
}
}
Output = [20, 10, 30]

Lets also look at the Big O notation for some of the operations of HashSet.

Inserting :- The insertion is same as that of the list, so its Big O is also constant O(1).

Searching :- Unlike list, we don’t have to iterate through the HashSet to find an element, instead of it hashSet uses hashCode(), which takes you the bin to find the element, which is constant time consuming process, so the Big O for this operation is O(1).

Deleting :- As searching takes O(1), so deletes also gonna take that much only because to delete an element we have to search it first and just remove it afterwards.

So, if you need a sorted map then use TreeSet or LinkedSet. TreeSet sort things in natural order(ascending), but if you want to sort them in a different way then you would have to implement Comparable.

public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<Integer>();
ts.add(70);
ts.add(20);
ts.add(90);
System.out.println(ts);
}
}
Output = [20, 70, 90]

Lets also look at the Big O notation for some of the operations of TreeSet.

Inserting :- In treeset the elements are in sorted order so when we add an element, it will go at its sorted place, but finding that place will not be that hard as the Set will be already in sorted order, so the Big O for inserting will be O(log n).

Searching :- The TreeSet internally uses TreeMap, which uses binary tree for searching the elements, which takes the complexity of O(log n).

Deleting :- As searching takes O(log n ), the deleting also takes only that much as to delete an element you have to find it first that where it is located in the set.

Linked set stores objects in the order that you add them in initially, so If you want the set to remember the order that you add them in for the purposes of iteration and traversal, then use a LinkedHashSet.

public class LinkedHashSetDemo {
public static void main(String[] args) {
LinkedHashSet<Integer> lhs = new LinkedHashSet<Integer>();
lhs.add(70);
lhs.add(20);
lhs.add(90);
System.out.println(lhs);
}
}
Output = [70, 20, 90]

As LinkedHashMap has LinkedList running through inside it, all the basic operations have same complexities as that of LinkedList.

Maps

1. When you want to store key-value pairs.
2. Retrieving the value by key is fast.
3. Iterating over map values is very slow.
4. If you want to use your own objects as keys, you must implement hashCode() and equals() method.

The map also has three main types and the most lightweight type is the HashMap which does not retain the order of insertion.

public class HashMapDemo {
public static void main(String[] args) {
HashMap<String,Integer> hm = new HashMap<String,Integer>();
hm.put("a", 100);
hm.put("z",5);
hm.put("b", 20);
hm.put("c", 3);
System.out.println(hm);
}
}
Output = {a=100, b=20, c=3, z=5}

Lets also look at the Big O notation for some of the operations of HashMap.

Insertion :- As HashMap uses hashCode() to distribute elements, it takes the constant comlexity of O(1).

Searching :- As HashMap does not store elements in the sorted order, so searching depends on the number of elements present in the map and the Big O for searching will be O(n).

Deleting :- As discussed earlier, for deleting we first have to find the element and then remove it, so its complexity will also be equal to O(n).

So,if you want to store the keys of the map in natural order or alphabetical order or numerical order then we use TreeMap, and if you are using your own custom object then you have to implement comparable to tell the map how to sort it.

public class TreeMapDemo {
public static void main(String[] args) {
TreeMap<String, Integer> tm = new TreeMap<String,Integer>();
tm.put("d",4);
tm.put("a",6);
tm.put("c",7);
tm.put("b",9);
System.out.println(tm);
}
}
Output = {a=6, b=9, c=7, d=4}

As we discussed above that TreeSet uses TreeMap internally, so the basic operations of inserting, searching and deleting have the same Big O as that of TreeSet.

Now, LinkedHashMap internally uses LinkedList to keep the items in order, so LinkedHashMap just keep things in the order that you added them to the map initially.

public class LinkedHashMapDemo {
public static void main(String[] args) {
LinkedHashMap<String, Integer> lhm = new LinkedHashMap<String,Integer>();
lhm.put("c",40);
lhm.put("e",40);
lhm.put("a",40);
lhm.put("d",40);
System.out.println(lhm);
}
}
Output = {c=40, e=40, a=40, d=40}

Lets also look at the Big O notation for some of the operations of LinkedHashMap.

Insertion :- It takes the same complexity as that of the HashMap which is O(1).

Searching :- As LinkedHashMap retains the order of insertion, its search operation depends on the number of elements present in the Map, so Big O for this will be O(n).

Deleting :- As searching takes O(n), so to delete an element, we need to find it first and delete it, so deleting also takes complexity of O(n).