All you need to know about Java Collections Framework
What is a Collection framework?
Java programming language provides a lot of inbuilt data structures and algorithms so that we do not have to design a data structure from scratch every time. These data structures and algorithms are also optimized to a great extent. These optimised data structures and algorithms form the bulk of the Collections framework. They provide a means to perform operations like sorting, insertion, deletion, updating, and searching on data members and objects. The collection framework also provides interfaces and classes with defined methods to perform these functions.
Inside the Collection framework is the Collection interface, Map interface and Iterable interface. The Collection interface has three more interfaces, List, Set and Queue. These three interfaces are categorised based on the properties of data members that reside in them. If the user has to store a contiguous list of elements, then List will be used. If a data structure is required where only unique values are saved then Set will be used. If a data structure is required where priority of elements needs to be saved as to in which order the elements will be retrieved, then Queue interface will be used. Now these interfaces, List, Set, Queue are implemented by the classes contained in them.
Interfaces and Classes in a Collection Framework
The ArrayList class implements the List interface in the collection framework. Suppose there is an array of a number of students. It is of fixed length and if a new student joins the class, a new array will have to be created again to accommodate the new student's details. The ArrayList addresses such data algorithm issues by allowing for dynamic combinations. The following are the main features of ArrayList:
It allows addition of multiple elements to a given array list.
ArrayList allows for adding a whole new list to an existing array list.
We can obtain the value of an element at a specific index level in an ArrayList by using the an is the get function.
We can set the value of an element at a specific index by using the set function. It will change the previous value to the newly described value.
We can also check whether a specific element is present in an array or not by using the contains function which returns a Boolean value.
We can iterate over each element in an ArrayList by using the for loop. This can be done by using For loop, For each loop or the inbuilt Iterator function provided by the Collections framework.
We can remove an element at a specific index by using remove function. We can also specify the value of an element to be removed from the ArrayList. We can also remove all elements from an ArrayList by using the clear function.
Stack implements the List interface. It is a data structure where an element that has been pushed on the top can be removed first. e.g, consider a stack of cards. Using stack you can remove the card that is sitting in top of the pile first. Stack class is available in the java util package.
We use push function to add elements to the stack.
To check which element is at the top of the stack, we use the peek function. Notice that the output shows America and not the first element India. Since the first element was pushed first, so it is sitting at the bottom of the pile. When a user peeks from the top at the stack of elements, he/she will see the element put last as it is lying at the top of the pile. Hence, America.
We use pop function in Stack to remove the element lying at the top of the pile from the stack. Guess which element will peek now. Looking from the top we can now see Australia at the top of the pile.
The ArrayList and LinkedList implement similar methods in the List interface. LinkedList class implements both the List and Queue interfaces. However, there are some *differences between ArrayList and LinkedList:
Implements List interface
Implements List, Queue, and Dequeue interface
Stores a single value in a single position.
Stores 3 different values in a single position, previous address, data and next address.
Provides resizable array implementation
Provides doubly linked list implementation
When an element is added all elements after that position are shifted.
When an element is added, previous and next addresses are changed.
Can access any element using index.
Iteration needed from beginning of the List to access the element.
*Adapted from https://www.programiz.com/java-programming/linkedlist
The Queue interface is available in the java utils package and extends the Collection interface. It is used to hold elements in the FirstInFirstOut order. Consider a queue of students in a cafeteria picking up their lunch. New students will keep getting added at the end of the queue and those in the front will get their lunch and move out of the queue. So, the Queue is an ordered list of objects where elements are inserted at the end of the list and can be deleted from the start of the list. The most widely used classes in Queue are the PriorityQueue and LinkedList.
We use offer function to add elements in a queue.
To remove elements from a queue we use poll function.
To understand which element is next in queue we use peek function.
A few other common methods of Queue interface are:
add()-It inserts a specific element into the Queue. If it is successful, it returns true, if not, it throws an exception. Correspondingly, offer() method will return false if not successful.
element()-This method returns the value at the head of the queue. If the Queue is empty it returns an exception. Correspondingly, peek() method will return null if the queue is empty.
remove()-This method returns and removes the value at the head of the queue. if the queue is empty it throws an exception. Correspondingly, poll() method will return null if the queue is empty.
PriorityQueue is an important class of the Queue interface. It provides priority to elements stored in the list.
The same methods we used in LinkedList Queue can be used in PriorityQueue. We use offer function to add elements in a priority queue. But different priorities will be assigned to elements. the smallest element will be given the highest priority. This is coming from the min heap data structure implementation.
When we use the poll function, that element gets removed whose priority is the highest.
The peek function will show the next in line element to come out of the priority queue.
If we want to change the priority of the elements in a priority queue and assign it to the highest value, let’s say, then we need to pass a comparator parameter to the priority queue method.
ArrayDeque class implements the Queue interface and Deque interface. It is a double-ended queue. The elements can be inserted and deleted from the front and rear.
The offer function will add elements to an ArrayDeque. We can use first and last methods to add elements at the first or last position.
The peek method will show the next-in-line element in the ArrayDeque which is in the front. Peekfirst will also show the first element in the line, and peeklast will show the last element in line. The poll method will remove the element in front. Poll first will remove the element at the front. Poll last will remove the element at the end.
Set interface in Java is part f the Collections framework and exhibits similar properties to the mathematical Set concept. There are no duplicate elements in a set. The classes that implement the Set interface are HashSet, LinkedHashSet, EnumSet and TreeSet.
The add method adds elements to a HashSet. The remove method removes that element from the set. Contains function can check whether that element is present in the set. The size function will show the number of elements in the set.
For LinkedHashSet, all the methods will remain the same as in HashSet, except that the elements will not be random or hashed. Rather, they will appear in the order in which they were entered in the set.
The TreeSet class of Java implements the Set interface and provides the functionality of a Tree data structure. All the elements in a Tree Set will be unique and also in a sorted form. All the methods inherited by HashSet and Linked HashSet are also inherited by TreeSet class.
The Map interface of the Java collections framework provides the functionality of the map data structure. In List, Set and Queue the elements are stored in the form of values. Whereas in Map, the elements are stored in the form of key-value pair. A map cannot contain duplicate keys and each key has a unique value. The map interface maintains three different sets:
i. the set of keys
ii. the set of values
iii. the set of key/value associations mapping
The put function allows us to add key-value pairs in the HashMap. We can iterate over the HashMap to print all key-value pairs or all the keys or even all the values if so required.
The TreeMap class of the java collections framework provides the tree data structure implementation. The elements in the TreeMap are sorted naturally in ascending order based on the value of keys.
In conclusion, we see that the Java Collection framework provides a number of interfaces, like, Set, List, Queue, Deque and classes, like, ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, and TreeSet. These classes implement the interfaces and utilize the inbuilt data structure methods and algorithms to handle different functions in data members or objects. The collections framework is vast and extremely versatile to solve real-world complex scenarios.