As you all know that Java is one of the most recommended language used for Competitive Programming. Java Collection Framework has many containers that are used for different Purposes. Here we will be discussing about some of the important Collections that are useful for Competitive Programming as well as for the Interview Purpose.
Array List:- Array List is a part of collection framework and is present in java.util package. It provides us with dynamic arrays in Java. Though, it may be slower than standard arrays but can be helpful in programs where lots of manipulation in the array is needed. This class is found in java.util package.
Queue:- Queue interface present in the java.util package and extends the Collection interface is used to hold the elements about to be processed in FIFO (First In First Out) order. It is an ordered list of objects with its use limited to insert elements at the end of the list and deleting elements from the start of the list as it follows the FIFO or First-In-First-Out principle.
Stack:- Java Collection framework provides a Stack class which models and implements Stack data structure. The class is based on the basic principle of Last-in-First-out. In addition to the basic push and pop operations, the class provides three more functions of empty, search and peek. The class can also be said to extend Vector and treats the class as a stack with the five mentioned functions. The class can also be referred to as the subclass of Vector.
Deque:- The Deque interface present in java.util package is a subtype of the queue interface. The Deque is related to the double-ended queue that supports addition or removal of elements from either end of the data structure. It can either be used as a queue(first-in-first-out/FIFO) or as a stack(last-in-first-out/LIFO). Deque is the acronym for double ended queue.
TreeSet and TreeMap:- Both of these implement self balancing binary search tree (Red Black Tree in particular). Useful in situations where we wish to maintain sorted items with moderate (better than array and worse than hashing) search, insert and delete query time. Example problems are, Closest greater or same value on left side, Find closest value for every element in array, etc. We use TreeSet when we wish to store only keys and TreeMap when we wish to store key value pairs.
HashSet and HashMap:- Both of these implement hashing with chaining. Useful when we wish to have fast search, insert and delete (all three operations are O(1)). This is one of the most used data structures in the industry and most underrated in academics. There are many popular problems, count distinct elements, frequencies of array items, subarray with 0 sum and union and intersection of two unsorted arrays. Please refer Hashing Practice Problems for more practice.
LinkedHashSet and LinkedHashMap:- Implement hashing with chaining, but additionally also maintain insertion order. HashSet and HashMap do not maintain any order. So if we wish to print distinct elements in same order as they appear in input, we need to use LinkedHashSet and if we wish to print items and their frequencies in same order as they appear, we need to used LinkedHashMap.
Priority Queues:- Implement Min Heap by default. We can create a Max Heap also by passing Collections.reverseOrder() as a parameter. Priority Queue is used whenever we wish to efficiently find minimum or maximum element. It is used to implement popular algorithms like Prim’s Algorithm, Dijkstra’s shortest Path, Huffman Coding, K Largest Elements, Maximum Toys to Purchase and Merge K Sorted Arrays, Median of a Stream. Please refer Heap Practice Problems for more practice.
There are many more Java Collections available but these are the mostly used Collections for Competitive Programming and Interviews. Checkout some programs here. Please share your views if you have anything to share in the comment section.