Java Collections Framework…
The collection framework provides a well-designed set of interfaces and classes for storing and manipulating a group of data as a single unit or collection.
The Collection interface and Map interface are the two main “root” interfaces of Java collection classes.
The Collection Interfaces
The Collections Framework defines several core interfaces as shown below table:
Collection Interface
The Collection interface is the foundation upon which the Collections Framework is built. There are three interfaces that extend the collection interface.
- List
- Set
- Queue
Let’s discuss them in detail:
List Interface
The List Interface extends the collection interface. It is an ordered collection of elements that may contain duplicate elements.
List interface is further implemented into the following classes:
- ArrayList
- LinkedList
- Vector
1.ArrayList
The ArrayList class implements the List interface. It uses a dynamic array to store the elements of different data types. The insertion order is preserved in ArrayList. It can store duplicates and supports dynamic arrays that can grow as needed.
Let’s see the performance of the ArrayList while accessing, deleting, and inserting elements in ArrayList.
Consider the above example here we have an empty ArrayList of size 10. Now if we want to add a value in the last ( al.add(1)) it will take one step so the time complexity is O(1). But if our ArrayList is full and we want to add an element at the start of it then it requires 10 shifts to add the element at the start of the ArrayList so the time complexity is O(length of ArrayList) which is the worst case. So the time complexity of insertion in ArrayList is O(n).
Similarly to insertion the time complexity of the deletion of an element in ArrayList is O(n).
To access an element if we know the index of the element we can access it by using the get() method in one step doesn’t matter the location of the element in the ArrayList so the time complexity of accessing is O(1) in ArrayList.
When the capacity of the ArrayList reached then if we add an element its increases the size of the ArrayList by 50% more than the current size i.e for a given example it will be 15. So assume if the size of ArrayList is very big and its capacity is reached then insertion of a single element will increase the 50% of the current size which leads to a big amount of memory loss. So ArrayList is not good for storing a large number of data.
2.LinkedList
The LinkedList class implements the List interface. It uses a doubly linked list internally to store the elements. It provides a linked-list data structure.
Let’s see with an example:
If we want to add a value in the start it will take one step so the time complexity is O(1). If we want to add an element at any position of the LinkedList then we can do it in one step by breaking the link and establish a link with the new element. So the time complexity of insertion in LinkedList is O(1).
Similarly to insertion the time complexity of the deletion of an element in LinkedList is O(1). We can break the link of an element in one step.
To access or search an element in LinkedList we need to traverse through each element of the LinkedList till getting the desired element so it takes n step to access an element so the time complexity of accessing is O(n) in LinkedList.
As uses a doubly linked list internally to store the elements So every node of the LinkedList contains an extra pointer to store the reference of previous and next element which results in more memory consumption. So LinkedList is not for storing a small amounts of data. As ArrayList space complexity increases with an increase in the size of the ArrayList size So the LinkedList will have less space complexity compare to ArrayList for Storing a large amounts of data.
3.Vector
Vector uses a dynamic array to store the data elements. It is similar to ArrayList. However, It is synchronized and contains many methods that are not the part of Collection framework.
The time complexity of insertion, Deletion, and Searching of an element in the vector is the same as ArrayList.
But for Space Complexity, When the capacity of the Vector reached then if we add an element its increases the size of the Vector by twice the current size of the Vector. This leads to more space complexity and not suitable for a large number of data storage.
Set Interface
Set Interface extends the Collection interface. It represents the unordered set of elements which doesn’t allow us to store the duplicate items. We can store at most one null value in Set. Set is implemented by HashSet, LinkedHashSet, and TreeSet.
HashSet
HashSet class implements Set Interface. It represents the collection that uses a hash table for storage. Hashing is used to store the elements in the HashSet. It contains unique items. It doesn't preserve the insertion order.
Let’s see the insertion and deletion of elements in HashSet.
From the above diagram, we can see that HashSet internally uses HashMap to store the data. So whenever we create an object of HashSet it’s internally creates an object of HashMap and whenever we perform an add() operation it’s internally perform put() operation on internal HashMap.
As the HashSet uses HashMap internally so the insertion and deletion of an element will be done in one step. Hence the time complexity of the inserting and deleting of an element in HashSet is O(1).
LinkedHashSet
LinkedHashSet class extends the HashSet class and implements Set interface. LinkedHashSet maintains a linked list of the entries in the set, in the order in which they were inserted. So it represents the LinkedList implementation of Set Interface.
As LinkedHashSet extends the HashSet So the time complexity of insertion and deletion is the same as for HashSet i.e O(1).
SortedSet Interface
The SortedSet interface extends the Set interface and declares the behavior of a set sorted in ascending order. The SortedSet provides additional methods that inhibit the natural ordering of the elements.
SortedSet<data-type> set = new TreeSet();
NavigableSet Interface
The NavigableSet interface extends the SortedSet interface and declares the behavior of a collection that supports the retrieval of elements based on the closest match to a given value or values. It provides methods for navigation in a sorted list of elements.
TreeSet
Java TreeSet class implements the NavigableSet interface. It creates a collection that uses a tree for storage. Objects are stored in sorted, ascending order. Like HashSet, TreeSet also contains unique elements.
As TreeSet uses the tree data structure to store the data so the time complexity of insertion and deletion in TreeSet is O(log(n)).
Access and retrieval times are quite fast, which makes TreeSet an excellent choice when storing large amounts of sorted information that must be found quickly.
Queue Interface
The Queue interface extends the Collection interface and declares the behavior of a queue, which is often a first-in, first-out list. There are various classes like PriorityQueue, Deque, and ArrayDeque which implements the Queue interface.
PriorityQueue
PriorityQueue class implements the Queue interface. It holds the elements or objects which are to be processed by their priorities. PriorityQueue doesn’t allow null values to be stored in the queue.
Queue<String> q = new PriorityQueue();
The internal working of the PriorityQueue is based on the Binary Heap.To insert elements in PriorityQueue, Offer() and add() methods are used. And to delete elements in PriorityQueue,
As Priority Queue is implemented using Heap Data Structures so the time complexity to insert and delete element is O(log(n)).
peek() and element() are the methods that are used to retrieve elements from the head of the queue and its time complexity is O(1).
Deque Interface
The Deque interface extends the Queue interface and declares the behavior of a double-ended queue. Unlike queue, we can add or delete the elements from both ends.
ArrayDeque
ArrayDeque class implements the Deque interface. ArrayDeque creates a dynamic array and has no capacity restrictions. Unlike queue, we can add or delete the elements from both ends.
The time complexity to insert and delete element is O(1).
peek() and element() are the methods that are used to retrieve elements from the head of the queue and its time complexity is O(1).
ArrayDeque is faster than ArrayList and Stack and has no capacity restrictions.
Map
The Map interface present in java.util package represents a mapping between a key and a value. The Map interface is not a child interface of the Collection interface but it’s included in the collection framework. Therefore it behaves a bit differently from the rest of the collection types.
Maps In Java
A map is an object that stores associations between keys and values, or key/value pairs. Each key and value pair is known as an entry. Both keys and values are objects. The keys must be unique, but the values may be duplicated. Some maps can accept a null key and null values, others cannot.
The Map Interfaces
Map interfaces define the character and nature of maps. The following interfaces support maps:
The Map Interface
A Map is an object that maps keys to values. A map cannot contain duplicate keys but can contain duplicate values, Each key can map to at most one value. The Map interface includes methods for basic operations (such as put, get, remove, contains key, contains value, size, and empty), bulk operations (such as putAll and clear), and collection views (such as keySet, entrySet, and values). Map is generic and is declared as shown here:
interface Map<K, V>
Here, K specifies the type of keys, and V specifies the type of values.
The SortedMap Interface
The SortedMap interface is the child interface of the Map interface. Whenever a group of key-value pairs needs to be sorted in some sorted order we use SortedMap. It ensures that the entries are maintained in ascending order based on the keys. SortedMap is generic and is declared as shown here:
interface SortedMap<K, V>
Here, k specifies the type of keys, and V specifies the type of values.
Some methods declared by SortedMap are summarized below:
The NavigableMap Interface
The NavigableMap interface is a child interface of the SortedMap. It provides several utility methods to navigate in SortedMap and declares the behavior of a map that supports the retrieval of entries based on the closest match to a given key or keys.
declaration:
interface NavigableMap<K,V>
The Map.Entry Interface
The Map.Entry is the inner interface of the Map which enables us to work with a map entry(key-value pair).
declaration:
interface Map.Entry<K, V>
Methods Of Map.Entry:
- public object getKey(): is used to obtain a key.
- public Object getValue(): is used to obtain the value of a key.
The Map Classes
List of classes which implements Map interface are mention below:
The HashMap Class
The HashMap class extends AbstractMap and implements the Map interface. It contains the values based on the key. HashMap uses the hash table data structure to store the map. It contains only unique values and may have one null key and multiple null values.
declaration:
class HashMap<K, V>
Take an example:
Methods of HashMap:
- public int size(): Return the number of key-value mappings in the map.
- public boolean isEmpty(): Returns true if the map contains no key-value mapping.
- public V get(object Key): Returns the value to which the specified key is mapped or null if this map contains no mapping for that key.
Hashmap works on the principle of hashing and internally uses hashcode as a base, for storing key-value pairs.
get(), put(),containsKey() operations are O(1) in average case but it is not always O(1) since it also depends on how much time does it take to compute the hash.
The LinkedHashMap class
LinkedHashMap class is the subclass of the HashMap class. It uses the hybrid data structure(i.e Doubly linked list and Hash table) to maintain the entries in the map hence the order of insertion is preserved in LinkedHashMap class.
declaration:
class LinkedHashMap<K, V>
get(),put(),containsKey() operations are O(1) in average case.
The TreeMap class
The TreeMap is the subclass of AbstractMap and implements the Navigable interface. It creates maps stored in a tree structure and sorted order is maintained. The map is sorted according to the natural ordering of its keys or by a comparator provides at map creation time, depending on which constructor is used.
declaration:
class TreeMap<K, V>
operations like add, remove, containsKey, the time complexity is O(log(n)).
Conclusion
In this blog, we learned about Collection and Map Interface in Java collection framework. We saw how the Collection and Map and their other child interfaces and classes are used to store and manipulate the data. We also saw the methods provided by some interfaces and classes to perform the operation on the store data. That’s it for this blog.
