Overview

A collections framework is a class library to handle groups of objects. It is present in java.util package. It allows us to store, retrieve, and update a group of objects.

Collections framework in Java supports two types of containers:

One for storing a collection of elements (objects), that is simply called a collection.
The other, for storing key/value pairs, which is called a map.

A collection in java is a container object that is used for storing multiple homogeneous and heterogeneous, duplicate, and unique elements without any size limitation.

Hierarchy

Collection

Map

e: extends, I: implements

Extends: Extends is a keyword that is used for developing inheritance between two classes and two interfaces.
Implements: Implements is a keyword used for developing inheritance between class and interface.

Collection Interface

The Collection interface extends the Iterable interface. The iterable interface has only one method called iterator(). The function of the iterator method is to return the iterator object. Using this iterator object, we can iterate over the elements of the collection.

The Collection interface consists of a total of fifteen methods for manipulating elements in the collection:

add(Object element): This method is used to add or insert an element in the collection.
addAll(Collection c): This method adds a collection of elements to the collection.
clear(): This method clears or removes all the elements from the collection.
contains(Object element): It checks that element is present or not in a collection.
containsAll(Collection c): This method checks that specified a collection of elements are present or not. It returns true if the calling collection contains all specified elements otherwise return false.
equals(Object element): It checks for equality with another object.
hashCode(): It returns the hash code number for the collection. Its return type is an integer.
isEmpty(): It returns true if a collection is empty.
iterator(): It returns an iterator.
remove(Object element): It removes a specified element from the collection.
removeAll(Collection c): The method removes all elements from the collection.
retainAll(Collection c): This method is used to remove all elements from the collection except the specified collection.
size(): The method returns the total number of elements in the collection.
toArray(): It returns the elements of a collection in the form of an array.
toArray(Object array[]): Returns an array that contains all the elements stored in the invoking collection.

List maintains an order of elements means the order is retained in which we add elements, and the same sequence we will get while retrieving elements.
Set represents a collection of elements that contains unique elements. It does not maintain any order while storing elements and while retrieving, we may not get the same order as we put elements. All the elements in a set can be in any order.
A queue is an ordered of the homogeneous group of elements in which new elements are added at one end(rear) and elements are removed from the other end(front).

List Interface

It is an ordered collection where elements are maintained by index positions because it uses an index-based structure. In the list interface, the order is retained in which we add elements. We will also get the same sequence while retrieving elements.

List interface in java has four concrete subclasses. They are ArrayList, LinkedList, Vector, and Stack.

List Initialization

There are four methods to initialize the list.

Using Arrays.asList
```
ArrayList<String> ar = new ArrayList<String>(Arrays.asList("A", "B", "C"));
```
Note that the list doesn't create a copy of the input array. Instead, it wraps the original array with the List interface. Therefore, changes to the array reflect on the list too.
Using List.of
```
ArrayList<String> ar = new ArrayList<String>(List.of("A", "B", "C"));
```
List.of() returns an immutable list that is a copy of the provided input array. For this reason, changes to the original array aren't reflected on the returned list.

Using Normal way

ArrayList<String> ar = new ArrayList<>();   
ar.add("A");
ar.add("B");

Using Anonymous Inner class

ArrayList<String> ar = new Arraylist<String>() {{   
add("A");
add("B");
add("C");
 }};

List specific methods

add(int index, Object o), addAll(int index, Collection c), remove(int index), get(int index):, indexOf(Object o), lastIndexOf(Object o), set(int index, Object o), listIterator(int)

Time Complexity

add(Object o): O(1)
add(int index, Object o): O(N)
get(int index): O(1) for ArrayList, and O(N) for LinkedList
remove(Object o): O(N)
contains(Object o): O(N)

Stack

The class is based on the basic principle of last-in-first-out.

Stack specific methods:

push(Object element): place the element at the top of the stack.
peek(): Returns the element on the top of the stack, but does not remove it.
pop(): Removes and returns the top element of the stack. An exception is thrown if we call pop() when the invoking stack is empty.
search(Object element): It determines whether an object exists in the stack. If the element is found, it returns the position of the element from the top of the stack. Else, it returns -1.
empty(): It returns true if nothing is on the top of the stack. Else, returns false.

Above operations have the time complexity of O(1) except for search(Object o) with O(N).

Set Interface

A set in Java is an unordered collection of unique elements or objects. In other words, a set is a collection of elements that are not stored in a particular order.

The SortedSet interface extends the Set interface to provide the sorted set of elements.

Three classes such as HashSet, LinkedHashSet, and TreeSet implement set interface:

HashSet is a concrete class that implements set interface. It uses a hash table mechanism to store its elements. It is the best-performing implementation.
TreeSet is a concrete class that implements SortedSet interface (a subinterface of set). It uses a binary search tree mechanism to store its elements. It orders its elements based on their values. It is considerably slower than HashSet. Exclusive functions contain, first(): return the first element in TreeSet if TreeSet is not null else it will throw NoSuchElementException; last(): return the last element in TreeSet if TreeSet is not null else it will throw NoSuchElementException; pollFirst(): retrieves and removes the first (lowest) element, or returns null if this set is empty; pollLast(): retrieves and removes the last (highest) element, or returns null if this set is empty.
LinkedHashSet is a concrete class that extends HashSet class. It stores its elements using hash table mechanism with a linked list implementation. It orders its elements based on the order in which they were inserted into the set. That is, elements in the HashSet are not ordered but elements in the LinkedHashSet can be retrieved in the order in which they were inserted into the set. Suppose we have LinkedHashSet<Integer> hashSet = new LinkedHashSet<Integer>();, to get the first element of a LinkedHashSet, 1. int first = hashSet.iterator().next();, 2. int first = hashSet.stream().findFirst().get();.

Time Complexity

HashSet and LinkedHashSet: O(1) for add, remove and contains operations.
TreeSet: O(log N) for add, remove and contains operations.

Set Initialization

Similar to the List Initialization. We can still use Arrays.asList() and Set.of.

Set specific methods

Set interface does not provide any get() method.

The only way to take out elements from the set can be by using Iterator() method but this method does not return elements from set in any particular order, or one can use Enhanced for loop.
Suppose s is a set, we can do:

Iterator<String> itr = s.iterator(); 
while(itr.hasNext())
{ 
  System.out.println(itr.next()); 
 }

 for(Integer it:s)
 { 
   System.out.println(it); 
 }

Queue Interface

A Queue in Java is a collection of elements that implements the “First-In-First-Out” order.

A Queue interface is implemented by several classes such as LinkedList, ArrayDeque, and PriorityQueue.

Queue specific methods

offer(E e): It is used to insert the specified element e to the queue.
peek(): The peek() method is used to retrieve the element at the head of queue, but the element is not removed. It returns null if the queue is empty.
poll(): The poll() method is used to retrieve the element at the head of queue and removes the element in the process. This method returns null if this queue is empty.

PriorityQueue

A PriorityQueue in Java is a queue or collection of elements in which elements are stored in order of their priority. When accessing elements, the element with the highest priority is removed first before the element with lower priority.

Priority is decided by Comparator provided in the constructor when the priority queue is instantiated. If no comparator is provided, PrirotyQueue orders its elements according to their natural ordering using the Comparable interface. The element at the head of the priority queue is the smallest element with respect to specified ordering. (To memorize, think we order elements by natural order, that is from small (left) to big (right), and the head of the queue is at the left.) That is, the element having the smallest value will be assigned with the highest priority and removed first from the queue.

The underlying data structure for implementing PriorityQueue in Java is Binary Heap.

It provides O(log(n)) time for enqueuing and dequeuing operations.

Example:

PriorityQueue<Integer> pq2 = new PriorityQueue<>(5, Collections.reverseOrder());
  pq2.offer(50);
  pq2.offer(100);

Simplper way to customize comparator using lambda function

Queue<List<Integer>> q = new PriorityQueue<>( (l1,l2) -> l1.get(1)-l2.get(1) );

or even:

 Map<Integer, Integer> count = new HashMap();
 for (int n: nums) {
     count.put(n, count.getOrDefault(n, 0) + 1);
 }

 // init heap 'the less frequent element first'
 Queue<Integer> heap = new PriorityQueue<>(
(n1, n2) -> count.get(n1) - count.get(n2));

note that we can use other variables inside the lambda function. For the comparator, if a negative number is returned, we order elements by: e1,e2; otherwise for a positive number, e2,e1.

Customize the comparator

Declare a class implementing the following interface

public interface Comparator<T> 
{
 // An abstract method declared in the interface
      int compare(Object obj1, Object obj2);

// Re-declaration of the equals() method of the Object class, optional
      boolean equals(Object obj);
}

Example:

public class Ascend implements Comparator<Integer>
{
@Override
public int compare(Integer i1, Integer i2) {      
   return i1.compareTo(i2);
  }
  // No need to override equals method.
}
import java.util.TreeSet;
public class CompTest {
public static void main(String[] args) 
{
// Create an object of Ascend class.    
   Ascend as = new Ascend();

// Create a tree set and pass the reference variable of Ascend class as a parameter.
  TreeSet<Integer> ts = new TreeSet<Integer>(as);    
  
// Adds elements into treeset.   
  ts.add(25);
  ts.add(15);
}
}

ArrayDeque

The Deque is related to the double-ended queue that supports the addition or removal of elements from either end of the data structure.

add an element at the head of the queue: addFirst(element), offerFirst(element)
add an element at the tail of the queue: addLast(element), offerLast(element)
retrieve, but not remove, the first element of this deque: getFirst(), peekFirst()
retrieve, but not remove, the last element of this deque: getLast(), peekLast()
retrieve and remove the element at the head of the deque: pollFirst()
retrieve and remove the element at the tail of the deque: pollLast()
remove an element from the head of the queue: removeFirst()
remove an element from the tail of the queue: removeLast()

Example:

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
int first = deque.removeFirst();
int last = deque.removeLast();

Map Interface

A map in Java is a container object that stores elements in the form of key and value pairs. A key is a unique element (object) that serves as an “index” in the map.

A SortedMap is a subinterface of Map interface that extends Map interface. The entries in the map are maintained in ascending order based on the keys.

Map Interface methods:

put(K key, V value): It is used to add an entry with specified key and value in the map.
putAll(Map m): It is used to add all entries from into this map.
putIfAbsent(K key, V value): It is used to add specified value with specified key in the map only if it is not already specified.
remove(Object key): This method is used to delete an entry for the specified key. It will return null if the key is not in the map.
remove(Object key, Object value): This method is used to remove the specified value associated with specified key from the map.
keySet(): This method returns a set consisting of the keys in the invoking map. It provides a set-view of the keys.
clear(): This method is used to remove all entries from the map.
get(Object key): This method returns the value for the specified key in this map.
hashCode(): It returns the hash code value for the invoking map.
isEmpty(): This method is used to check whether the map contains any entries.
size(): The size() method returns the number of entries (number of key/value pairs) in the map.
replace(K key, V value): This method is used to replace the specified value for a specified key.
replace(K key, V oldValue, V newValue): This method is used to replace old value with new value for a specified key.
values(): This method returns a collection view of the values in the map.
containsKey(Object key): This method is used to check whether the map contains an entry for the specified key.
containsValue(Object value): This method is used to check whether the map contains an entry for the specified value.
equals(Object obj): This method is used to compare the specified Object with map. If obj is a map and contains the same entries, it returns true otherwise, false.

HashMap: It is a concrete class that extends AbstractMap. It uses a hash table to store elements. It is mainly used for locating a value, inserting, and deleting an entry. It offers O(1) lookup and insertion. If you iterate through the keys, though, the ordering of the keys is essentially arbitrary.
TreeMap: It is a concrete class that extends AbstractMap and implements NavigableMap interface. It used a Red-Black tree for storing elements. It is used for traversing keys in sorted order. The keys can be sorted using the Comparable interface or Comparator interface. It offers O(log N). lookup and insertion. Keys are ordered by its value.
LinkedHashMap: It offers O(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.

Difference between Hashtable and HashMap

HashMap is non-synchronized. It is not thread-safe and can’t be shared between many threads without proper synchronization code whereas Hashtable is synchronized. It is thread-safe and can be shared with many threads.
HashMap allows one null key and multiple null values whereas Hashtable doesn’t allow any null key or value.
HashMap is generally preferred over HashTable if thread synchronization is not needed.

Map Initialization

Using Map.of() method

Map<String, String> map = new Map<>(Map.of("1", "GFG", "2", "Geek", "3", "GeeksForGeeks"));

Note a maximum of 10 pairs can be given.

Iterate Map

Map<Integer, String> map = new HashMap<>();
 
   map.put(101, " John");
   map.put(202, " Ricky");
   map.put(303, " Deep");
   map.put(404, " Mark");
   map.put(505, " Maya");
      
for (Integer rollNo : map.keySet()) // Iterating over keys of a map using keySet() method.
System.out.println("Roll No: " + rollNo);
       
for (String name : map.values()) // Iterating over values of a map using values() method.
System.out.println("Name: " + name); 

for (Map.Entry<Integer,String> entry : map.entrySet()) // Iterating over entries of a map using entrySet() method. 
{  
 System.out.println("Roll No: " + entry.getKey() + ", Name: " + entry.getValue());   
 }

Credits go to: https://www.scientecheasy.com/2020/09/java-collections-framework.html/

Java Collection Framework

Overview

Hierarchy

Collection

Map

Collection Interface

List Interface

List Initialization

List specific methods

Time Complexity

Stack

Set Interface

Time Complexity

Set Initialization

Set specific methods

Queue Interface

Queue specific methods

PriorityQueue

Simplper way to customize comparator using lambda function

Customize the comparator

ArrayDeque

Map Interface

Difference between Hashtable and HashMap

Map Initialization

Iterate Map

Comment

Latest

Recent Reply

Category

Tag

Archive

Others