Collections in Java

In this article, we are going to discuss collections in Java. We will discuss the basics of collections framework in Java, different collections classes, collections interfaces, etc. Also, we will discuss a lot of collection programs in Java. So, let us start by understanding what the collections framework is.

What are Collections in Java?

The word ‘collections’ denotes something relating to a collection or a group. So, the collections are the storing units or containers that group multiple items.

In Java, we have a collections framework to use, manipulate and play around with collections. It was provided by Java 1.2. The Java collection framework has various interfaces, classes, and algorithms. So, let us learn a few things about each one of them.

Interfaces in Collections in Java

Interfaces are the blueprint of classes in Java. Interfaces provide a basic structure for a class in Java. They are like abstract classes but with complete or total abstraction. This means that all the methods in an interface are abstract and all the data members are final and static by default.

The root interface i.e. the root of the hierarchy tree of the collections framework is java.util.collection.

This means that the methods that this interface contains, will be present in every class as every class implements this interface. Some of these methods are size(), add(), remove(), etc.

There are many other interfaces in the collections framework. We will learn some of them in detail in the later sections.

Implementation Classes in Collections in Java

The classes in Java collections framework provide the implementation for the interfaces of the collections in Java. Thus these classes are often called implementation classes.

We can use these classes and the methods of the interfaces that have been overridden in them to use in our programs. There are multiple important classes in the collections framework. We will learn about some of the most important classes in later sections.

Algorithms in Collections in Java

These are some of the methods that can be directly implemented for the implementation classes. For instance, we can directly sort the collection or shuffle it, etc.

So, these are the 3 main entities of the collections framework in Java. Now, let us also see the Class Diagram of the collections framework.

Class Diagram of Collections in Java

This diagram is not for memorizing. This is just helpful when you get stuck somewhere so that you can take help from it and analyze the hierarchy of the classes and interfaces in Java.

Now, let us understand some of the most important interfaces of the Java collections framework.

Interfaces that Extend collection Interface in Java

The iterable interface and collection interface, both are considered the root interfaces. Now, let us clarify the concept that which interface extends which interface and who is the root among them.

Iterable Interface:

So, the iterable interface is the root interface of the collections framework. This interface, as the name suggests, provides the functionality to iterate over the collection. So, it provides iterators for the collections in Java. This interface has only one abstract method i.e. iterator.

Collection Interface:

Often there is a misconception regarding the “collections class in Java”. There is no class named collections, but rather an interface named collection. All the classes that extend this interface are called collections in Java. The collection interface extends the Iterable interface i.e. inherits from it. Also, all the classes implement the collection interface. So, since all the classes implement the collection interface and the collection interface extends the Iterable interface, this means that all the collection classes in Java have an iterator for them.

Since this interface is implemented by all the collection classes, this interface contains those methods that are common to every collection. For instance, adding the data, removing the data, etc. Every class implements its version of these methods.

Some of the methods of the collection interface are as follows.

1. add(Object): This method is used to add an object to the collection. Now, a list might add an object in a different way than a priority queue or a HashSet. So, every class will have its own version of this method.

2. addAll(collection c): This method is used to add all the elements of a collection c to our collection.

3. clear(): This method removes all the elements present in our collection.

4. contains(Object o): This is a boolean method. It returns true if the Object o is present in our collection, else returns false.

5. containsAll(collection c): This is also a boolean method. This method returns true if all the elements of collection c are present in our collection, else returns false.

6. equals(Object o): This method compares the object o with our collection for equality. This is also a boolean method. It returns true if they are equal, else returns false.

7. hashCode(): This method returns the hash code of the collection in Java.

8. isEmpty(): This method is used to check if the collection is empty or not. This is also a boolean method, It returns true if the collection is empty and false otherwise.

9. iterator(): This method is used to return an iterator for the collection.

10. size(): This method is used to return the size of the collection i.e. the number of elements in the collection.

11. remove(Object o): This method is used to remove the given object o from the collection, In case of duplicates, this method removes the first occurrence of that object in the collection.

12. removeAll(collection c): This method is used to remove all the elements of collection c from our collection.

So, these are some of the most important methods of the collection interface in Java.

List Interface:

It is a child interface of the collection interface. This interface provides the structure for the classes storing the list type of data like Stack, ArrayList, Vector, etc. Duplicate elements can be present in a List. All the classes that implement the List interface can be instantiated by the reference of the List interface.

Queue Interface:

The Queue interface represents the Queue data structure. This means that it represents the FIFO (First in First Out) ordering of the elements. This is shown in the image below.

The Queue interface is implemented by various classes. 2 of them are ArrayDeque and PriorityQueue. All the classes that implement the Queue interface can be instantiated by the reference of the Queue interface.

Deque Interface:

This interface represents the DE-Queue data structure i.e. the double-ended queue data structure. We saw above in Queue that the insertion is performed from the rear end and the deletion from the front end. However, in the DE-Queue data structure, both insertion and deletion can be performed from both ends.

This interface extends the Queue interface and the class that implements this interface is ArrayDeque. Since the ArrayDeque class implements the Deque interface, the ArrayDeque object can be instantiated using the Deque reference.

Set Interface:

The set is an unordered collection, unlike the ones that we have discussed above. This means that the order in which you enter the elements may not be the same as the order in which they get stored within this collection. This interface is used to store unique objects. They are stored based on some hashing techniques. The classes that implement this interface are HashSet, TreeSet, and LinkedHashSet. All the classes that implement the Set interface can be instantiated using the Set reference.

Sorted Set Interface:

This interface is also aimed at storing the unique object. However, it is ordered, unlike the Set interface. This means that the ordering of the elements will be maintained. It extends the set interface. This interface is used in situations where we need the data to be sorted. The class implementing this interface is TreeSet. So, TreeSet is the ordered set in Java. Since TreeSet implements the Sorted Set interface, it can be instantiated using the reference of Sorted Set.

Map Interface:

The map interface is used to store the key-value pairs. This data structure supports unique keys. The classes, TreeMap and HashMap implement this interface. TreeMap will maintain the sorted order whereas HashMap will not. Since these classes implement the Map interface, they can be instantiated using Map reference.

So, these are the interfaces in Java collections framework. Now, let us study the Classes in collections in Java that implement these interfaces.

Classes Implementing List Interface

1. ArrayList: ArrayLists are dynamic arrays in Java. They are a little slow as compared to arrays because of increasing the memory size a lot of time. This means that they are slow amortized time complexity-wise. The asymptotic time complexity remains the same. They grow and shrink their size automatically. All the other features are similar to an array. The program for using an ArrayList is shown below.

ArrayList Program

import java.util.*;
public class Main {   
    public static void main(String[] args) {
        ArrayList<Integer> al = new ArrayList<>();
        al.add(1);
        al.add(2);
        al.add(3);       
        System.out.println(al);
        System.out.println(al.size());       
        al.remove(1); //removes the element at index 1       
        System.out.println(al);
        System.out.println(al.size());
    }
}

2. LinkedList: In a linked list, the elements are not stored in contiguous order i.e. they are not side-by-side in the memory. They can be present in different fragments of the memory at any random location. They are however connected by the self-referential next pointer. Every element and its next pointer combined forms an entity known as a node. An example linked list with data 10,2,30,40, and 50 are shown below.

LinkedList Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();        
        for(int i=1;i<=5;i++) list.add(i);        
        System.out.println(list);
        System.out.println(list.size());        
        list.remove(2); //removes an element at index 2
        System.out.println(list);
        System.out.println(list.size());
    }
}

3. Vector: A vector is the same as an ArrayList. The only difference comes in multi-threading. A vector is synchronized whereas an ArrayList is not synchronized.

4. Stack: A stack is a LIFO (Last in First out) based data structure. The basic operations of the stack are push and pop. Push means adding an element to the top of the stack and pop means removing the topmost element of the stack.

Stack Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        Stack<Integer> stk = new Stack<>();        
        for(int i=5;i>=1;i--) {
            stk.push(i);
        }        
        System.out.println(stk);        
        stk.pop();        
        System.out.println(stk);
    }
}

So, these were the classes that implement the List Interface. Let us now look at the classes implementing the Queue interface.

Classes Implementing Queue Interface

There are 2 classes that implement the Queue interface namely ArrayDeque and PriorityQueue. Let us learn about PriorityQueue here.

PriorityQueue:

This is a data structure that keeps the values ordered on the basis of priority. The elements are ordered naturally by the priority as per the Comparator provided by Queue at the time of construction of a PriorityQueue.However, we can change the priority according to our own needs by writing our own comparator. By default, min-heap is implemented for the priority queue in Java.

Priority Queue Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(10);
        pq.add(30);
        pq.add(20);        
        System.out.println(pq);
        System.out.println(pq.peek());        
        pq.remove();        
        System.out.println(pq);
        System.out.println(pq.peek());
    }
}

The method collections.reverseOrder() can be used to reverse the default behavior of PriorityQueue i.e. make it a max-heap.

Classes Implementing Deque Interface

We know that ArrayDeque implements Queue as well as the Deque interface. So, let us now study about ArrayDeque class.

ArrayDeque:

This is used to implement the DE-Queue data structure i.e. a dynamically sized array that can have the addition and removal of elements from both ends. Let us see an example program to understand ArrayDeque.

ArrayDeque Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();        
        dq.addFirst(10);
        dq.addFirst(20);
        dq.addLast(30);
        dq.addLast(40);        
        System.out.println(dq);        
        dq.removeFirst();
        dq.removeLast();        
        System.out.println(dq);
    }
}

So, we have learned ArrayDeque. Now, let us move to the Set interface.

Classes Implementing Set Interface

There are 3 classes that implement the Set interface namely HashSet, TreeSet, and LinkedHashSet. Let us learn about HashSet and LinkedHashSet first.

HashSet:

The HashSet is the implementation of the HashTable data structure where we insert the values into the data structure and they get inserted on a specific position automatically generated by the specific hash function. The insertion of NULL elements is allowed in HashSet. However, this is an unordered data structure. Let us see an example program for the HashSet class.

HashSet Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        HashSet<Integer> hs = new HashSet<>();        
        hs.add(10);
        hs.add(20);
        hs.add(30);        
        for(int i=1;i<=30;i++) {
            if(hs.contains(i)) {
                System.out.println(i + " is already present in the hashset");
            }
            hs.add(i);
        }    
        System.out.println(hs);
    }
}

LinkedHashSet:

This is the same as HashSet. The difference between HashSet and LinkedHashSet is that the LinkeHashSet uses Linked List to store data and LinkedHashSet also maintains the elements in sorted order.

Let us now learn about the SortedSet.

Classes Implementing SortedSet Interface

TreeSet class implements this interface. Let us learn the TreeSet class.

TreeSet:

It uses a Tree for storing the data. This is an ordered set i.e. the ordering is maintained using the set’s natural ordering. However, we can give our own ordering using a Comparator.

Tree Set Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        TreeSet<Integer> ts= new TreeSet<>();
        ts.add(10);
        ts.add(30);
        ts.add(20);
        ts.add(5);
        ts.add(100);        
        System.out.println(ts); //sorted order
        ts.add(100);
        ts.add(100);        
        //100 wont be added again
        System.out.println(ts);
    }
}

Classes Implementing the Map Interface

So, HashMap and TreeMap are the 2 classes that implement the Map interface. We know that the Map interface has key-value pairs.

HashMap:

A hashmap is an unordered map. Various hashing techniques can be used to store data in a hashmap. The hashmap is explained with the help of an example program given below.

HashMap Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        HashMap<String,Integer> hm = new HashMap<>();        
        hm.put("Guneet",1);
        hm.put("Abhishek",2);
        hm.put("Abheesh",3);        
        System.out.println(hm);        
        hm.put("Guneet",4); //will not be added        
        System.out.println(hm);
    }
}

TreeMap:

A treemap will maintain the ordering in sorted order and is constructed using a tree. Rest, it is the same as a hashmap.

TreeMap Program

import java.util.*;
public class Main {    
    public static void main(String[] args) {
        TreeMap<String,Integer> tm = new TreeMap<>();        
        tm.put("Guneet",1);
        tm.put("Abhishek",2);
        tm.put("Abheesh",3);        
        System.out.println(tm); // strings are the keys
        //they are ordered lexicographically        
        tm.put("Guneet",4); //will not be added        
        System.out.println(tm);
    }
}

So, we have learned about the collection framework, its different interfaces, and all the different classes implementing those interfaces. As already discussed, apart from classes and interfaces, algorithms are also a part of collections. For instance, we can sort some collections, shuffle them, or find the minimum or maximum value.

However, these operations can be specific to certain collections. So, just knowing that these operations exist is enough. We can use them whenever we have the need.

We hope that you liked the discussion and understood the concept of collections in Java. See you again at PrepBytes.

Leave a Reply

Your email address will not be published. Required fields are marked *