Collections in Java

The Java Collections Framework is a collection of interfaces(Set, List, Queue, Deque) and classes(ArrayList, Vector, LinkedList) which helps in storing and processing the data efficiently. This framework has several useful classes which have tons of useful functions which makes a programmer task very easy.

Hierarchy of Collection Framework

We can perform all operations such as insertion, deletion, searching, sorting, manipulation, etc., on Java collections just like we do it in array. Let’s discuss all the terms in detail:

ArrayList

• Its like an array, but has no size limit.
• Its size increases dynamically if the elements are added more than the initial size.
• It can store duplicate elements.
• It maintains the insertion order.

From the above example, we can see add() is used to add an element in an arraylist. This method is defined in List interface and is implemented by arraylist (by default). Time taken to add/remove an element is O(n), where n is size of list. Why O(n)??

This the worst case scenerio, where an element will be inserted at index 0. In this case, all the other elements will first shift by one place, then only an element can be inserted at index 0. Thus, shifting of each element will take O(n) time.

In worst case, it will take O(n) time to search an element if the element is not found in the list.

LinkedList

• It uses a doubly linked list to store the elements.
• It can contain duplicate elements.
• It maintains insertion order.
• Its manipulation is fast in comparison to ArrayList, because no shifting needs to occur.

LinkedList is mainly used for efficiency purpose. This takes less time to insert or delete any element from the linkedlist. Here, all the elements are pointing to its next successive element. Insertion is quite fast in linkedlist compared to arraylist. In linkedlist, insertion/deletion of any element will take O(1) time

Simple linkedlist having 3 elements

Insertion of element “3" at position 2 in linkedlist

It will take more time while searching any element in comparision to Linedlist, as we have to iterate through all the elements in linkedlist if we search for any unfound element. Time complexity for searching an element will be O(n) in worst case, where n is size of linkedlist.

Stack

It follows LIFO approach i.i., it orders the element is Last In First Out manner. Insertion or deletion can only be possible from one end only. The last element will be removed first and the first element will be removed in the end. It will take O(1) time to either add or delete an element in Stack. push() and pop() methods are used to insert or delete an element respectively in stack.

A good real-life example of a stack is the pile of dinner plates that you encounter when you eat at the local cafeteria: When you remove a plate from the pile, you take the plate on the top of the pile. But this is exactly the plate that was added (``inserted’’) most recently to the pile by the dishwasher. If you want the plate at the bottom of the pile, you must remove all the plates on top of it to reach it.

Let’s push 20, 13, 89, 90, 11, 45, 18, respectively into the stack.

Push operation

Let’s remove (pop) 18, 45, and 11 from the stack.

Pop operation

HashSet

• It stores the elements by using a mechanism called hashing. Its neither be in insertion order nor in sorted order.
• It contains unique elements only.
• It doesn’t maintain the insertion order.
• add, remove, and contains methods has constant time complexity O(1).

LinkedHashSet

• contains unique elements only like HashSet.
• The only reason to use LinkedHashSet over HashSet is that LinkedHashSet maintains insertion order.
• Obviously, it will take more time to search any element i.e, O(n) in worst case. It needs to traverse to each and every element to search an element that is not found in the LinkedHashSet.

TreeSet

• It contains unique elements only like HashSet.
• Its access and retrieval times are quiet fast.
• It doesn’t allow null element.
• It maintains ascending order.
• The elements in a set are sorted, but the add, remove, and contains methods has time complexity of O(log (n)).

Queue

Queue in Java follows a FIFO approach i.e. it orders the elements in First In First Out manner. Insertion or deletion can only be possible from one end only. The first element will be removed first and the last element will be removed in the end. It will take O(1) time to either add or remove an element.

Java Map Interface

• A map contains values on the basis of key, i.e. key and value pair. Each of these pair is known as an entry.
• It contains unique keys.
• It s useful if you have to search, update or delete elements on the basis of a key.
• It doesn’t allow duplicate keys, but can have duplicate values.
• A Map can’t be traversed, so it need to convert into Set using keySet() or entrySet() method.

Java Map Hierarchy