Before coming to the topic Collections in java, you should know about the packages in java. Java offers a wide variety of packages and one of them is java.util and this package contains java’s most powerful subsystem i.e., Collection.

The Collection in java is an advanced way to manage a group of interfaces and classes into a single entity.

Collections were not the part of original java but then added after. Java collections provide set, queue, list as interfaces and HashSet, LinkedHashSet, TreeSet, ArrayList, Vector, LinkedList as classes.

The Collection consist of the following

• Interfaces
• Classes
• Algorithm

Interfaces in java

Interfaces are similar to classes when we consider by the syntax, but the difference is they lack the instance variable, and their methods are declared without anybody.

They referred to as abstract data type in Java  Iterable is the root of the Collection framework is at the head of the hierarchy.

Classes in java

Classes are used to create different types of collections in java. The class can implement more than one interface. java offers classes such as ArrayList, Vector, LinkedList, HashSet, LinkedHashSet, TreeSet, TreeMap (explained in detail).

Most of the programmers use them as fundamental but can extend or customize them according to their needs.

A simplified general form of a class definition is shown here:

<access specifier>class<class name>

{

}

Algorithm

The algorithm defines a set of rules or particular ways of calculation to reach for a special purpose, for example, Bubble Sort, Selection Sort, Compare and Swap algorithm and many more.

Collection Interface in Java

The Collection interface in java that is implemented by all the classes in the collection framework. It also declares the methods that every collection will have follow.

In other words, we can say that the Collection interface mainly builds the foundation on which the collection framework depends.

Some main methods of Collection interface in java are Boolean add ( Object obj), Boolean addAll ( Collection c), void clear(), etc. which are mainly implemented by all the subclasses of Collection interface.

Methods of Collection interface in Java

• public boolean add(E e): It is mainly used to insert an element in the collection.
• public boolean addAll(Collection<? extends E> c): It is mainly used to insert the specified collection elements in the invoking collection.
•  public int hashCode(): It only returns the hash code number of the collection.
•  public boolean equals(Object element): It only matches two collections.
• public boolean isEmpty(): It helps to checks if the collection is empty or not.
• public void clear(): It mainly removes the total number of elements from the collection.
• public int size(): It mainly returns the total number of elements in the collection.
• public Object[] toArray() : It only converts collection into array.

List Interface in Java

List interface is the child interface of the Collection interface. It mainly inherits a list type data structure in which we can store the ordered collection of objects.

List interface is only implemented by the classes ArrayList, LinkedList, Vector, and Stack.

For instantiate the List interface, we must use :

List <datatype> list1= new ArrayList();  
List <datatype> list2 = new LinkedList();  
List <datatype> list3 = new Vector();  
List <datatype> list4 = new Stack();

ArrayList Class in Java

The ArrayList class in java mainly implements the List interface. For a dynamic array to store the duplicate element of different data types.

The ArrayList class maintains all the insertion order and is non-synchronized. The particular elements stored in the ArrayList class can be randomly accessed. Let consider the following example.

import java.util.*;  

public class TestJavaCollectionArrayList{  
ublic static void main(String args[]){  
ArrayList<String> list=new ArrayList<String>();//Creating an arraylist  

list.add("Ram");//Adding some object in arraylist  
list.add("Shyam");  
list.add("Ravi");  
list.add("Kalki");  
  
//Traversing list through Iterator  
Iterator itr=list.iterator();  
while(itr.hasNext()){  
System.out.println(itr.next());  
}}}  

Output: Ram Shyam Ravi Kalki

LinkedList class in Java

LinkedList implements only the Collection interface. It mainly uses doubly-linked lists internally to store the elements. It can also store the duplicate elements.

It also maintains the insertion order and is not synchronized. In the LinkedList, the manipulation is very fast because no shifting is required. Let consider the following example.

import java.util.*;  
    
public class TestJavaCollectionLinkedList{  
public static void main(String args[]){  
    
LinkedList<String> al=new LinkedList<String>();  
    
al.add("Ram");  
al.add("Shyam");  
al.add("Kalki");  
al.add("Ajay");  
    
Iterator<String> itr=al.iterator();  
while(itr.hasNext()){  
System.out.println(itr.next());  
}}  
}  

Output: Ram Shyam Kalki Ajay

Vector

Vector uses mainly a dynamic array to store the data elements. It is just similar to ArrayList. However, It is basically synchronized and contains many methods that are not the part of Collection framework.

Let consider the following example.

import java.util.*;  
    
public class TestJavaCollectionVector{  
public static void main(String args[]){  
    
Vector<String> v=new Vector<String>();  
    v.add("Ram");  
    v.add("Shyam");  
    v.add("Kalki");  
    v.add("Garima");  
    
Iterator<String> itr=v.iterator();  
while(itr.hasNext()){  
System.out.println(itr.next());  
}}  
}  

Output : Ram
         Shyam
         Kalki
         Garima

Stack

The stack mainly a subclass of Vector. It only implements the last-in-first-out data structure, i.e., Stack. The stack contains basically all the methods of Vector class and provides its methods just like boolean push(), boolean peek(), boolean push(Object o), which defines its properties.

Let consider the following example.

import java.util.*;  
    
public class TestJavaCollectionStack{  
public static void main(String args[]){  

Stack<String> stack = new Stack<String>();  
    
stack.push("Ram");  
stack.push("Garvit");  
stack.push("Shyam");  
stack.push("Kalki");  
stack.push("Garima");  
stack.pop();  
    
Iterator<String> itr=stack.iterator();  
while(itr.hasNext()){  
System.out.println(itr.next());  
    
    
}}}  

Output: Ram Garvit Shyam Kalki

Queue Interface

Queue interface mainly maintains the first-in-first-out order. It also defined as an ordered list that is used to hold the elements which are about to be processed.

There are some various classes like PriorityQueue, Deque, and ArrayDeque which implements the Queue interface also be instantiated as:

Queue<String> queue1 = new PriorityQueue();  
Queue<String> queue2 = new ArrayDeque();

Collections Class in Java

In Java, Collections class basically consists of some exclusively of static methods that operate on or return collections. There are some important points about Collections −

•  It mainly contains a basic algorithm named polymorphic that operates only on collections which we can say wrappers that only return a new collection backed by a specified collection that’s it.
•  Some methods of this class all throw a NullPointerException only if the collections or class objects provided to them are null.

Class declaration

Following is the declaration for Collections class in java just like that −

public class Collections
   extends Object

Important Method of Collections Class

Collection Algorithms with all sorting examples

Sorting means arranging it in a certain order, often in an array-like data structure.  If you’re interested in how sorting works, we’ll cover various algorithms, from inefficient but intuitive solutions to efficient algorithms that are actually implemented in Java.

There are some various sorting algorithms, and they’re not all equally efficient. But we are trying to analyze their time complexity in order to compare them and see which ones perform the best.

Here we learn some list of algorithms which most common and most efficient ones to help you get started:

• Bubble Sort
• Insertion Sort
• Selection Sort
• Merge Sort

Bubble Sort in java

Bubble sort only works by swapping adjacent elements if they’re not in the desired order. And this process repeats from the beginning of the array until all elements are in order. For example :

public class BubbleSortExample
{ 
  void bubbleSort(int arr[]) 
  { 
    int s = arr.length; 
    for (int i = 0; i < s-1; i++) 
      for (int j = 0; j < s-i-1; j++) 
        if (arr[j] > arr[j+1]) 
        { 
          // swap arr[j+1] and arr[i] 
          int temp = arr[j]; 
          arr[j] = arr[j+1]; 
          arr[j+1] = temp; 
        } 
  } 

  /* Prints the array */
  void printArray(int arr[]) 
  { 
    int s = arr.length; 
    for (int i=0; i<s; ++i) 
      System.out.print(arr[i] + " "); 
    System.out.println(); 
  } 

  // Driver method to test above 
  public static void main(String args[]) 
  { 
    BubbleSortExample ob = new BubbleSortExample(); 
    int arr[] = {174, 314, 215, 112, 212, 111, 901}; 
    ob.bubbleSort(arr); 
    ob.printArray(arr); 
  } 
} 

Output: 111 112 174 212 215 314 901

Insertion Sort in java

The idea behind the Insertion Sort is dividing the array into the sorted and unsorted subarrays. The sorted part is mainly length 1 at the beginning and is corresponding to the first (left-most) element in the array. We just iterate through the array and during each iteration, we expand the sorted portion of the array by one element. For example 

public class InsertionSortExample { 
  /*Function to sort array using insertion sort*/
  void sort(int arr[]) 
  { 
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
      int key = arr[i]; 
      int j = i - 1; 

      /* Move elements of arr[0..i-1], that are 
      greater than key, to one position ahead 
      of their current position */
      while (j >= 0 && arr[j] > key) { 
        arr[j + 1] = arr[j]; 
        j = j - 1; 
      } 
      arr[j + 1] = key; 
    } 
  } 

  static void printArray(int arr[]) 
  { 
    int n = arr.length; 
    for (int i = 0; i < n; ++i) 
      System.out.print(arr[i] + " "); 

    System.out.println(); 
  } 

  // Driver method 
  public static void main(String args[]) 
  { 
    int arr[] = { 19, 119, 143, 54, 64 }; 

    InsertionSortExample ob = new InsertionSortExample(); 
    ob.sort(arr); 

    printArray(arr); 
  } 
} 

Output: 19 54 64 119 143

Selection Sort in java

Selection Sort basically divides the array into a sorted and unsorted subarray. Though, this time, the sorted subarray which is formed by inserting some minimum element of the unsorted subarray at the end of the sorted array, by swapping:

For Example:

public class SelectionSortExample 
{ 
  void sort(int arr[]) 
  { 
    int n = arr.length; 

    for (int i = 0; i < n-1; i++) 
    { 

      int min_idx = i; 
      for (int j = i+1; j < n; j++) 
        if (arr[j] < arr[min_idx]) 
          min_idx = j; 

      // Swap the found minimum elements with the first 
      // element 
      int temp = arr[min_idx]; 
      arr[min_idx] = arr[i]; 
      arr[i] = temp; 
    } 
  } 

  // Prints the array 
  void printArray(int arr[]) 
  { 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
      System.out.print(arr[i]+" "); 
    System.out.println(); 
  } 

  // Driver code to test above 
  public static void main(String args[]) 
  { 
    SelectionSortExample  ob = new SelectionSortExample(); 
    int arr[] = {614,252,132,252,116}; 
    ob.sort(arr); 
    ob.printArray(arr); 
  } 
} 

Output: 116 132 252 252 614

Merge Sort in Java

Merge Sort is mainly used for recursion to solve the problem of sorting more efficiently than algorithms previously presented, and in particular, it uses a divide and conquers approach.

For Example :

/* Java program for Merge Sort */
public class MergeSortExample 
{ 
  // Merges two subarrays of arr[]. 
 
  void merge(int arr[], int n, int m, int r) 
  { 
   
    int n1 = m - n + 1; 
    int n2 = r - m; 

    /* Create temp arrays */
    int L[] = new int [n1]; 
    int R[] = new int [n2]; 

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i) 
      L[i] = arr[n + i]; 
    for (int j=0; j<n2; ++j) 
      R[j] = arr[m + 1+ j]; 


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays 
    int i = 0, j = 0; 

    // Initial index of merged subarry array 
    int k = n; 
    while (i < n1 && j < n2) 
    { 
      if (L[i] <= R[j]) 
      { 
        arr[k] = L[i]; 
        i++; 
      } 
      else
      { 
        arr[k] = R[j]; 
        j++; 
      } 
      k++; 
    } 

    /* Copy remaining elements of L[] if any */
    while (i < n1) 
    { 
      arr[k] = L[i]; 
      i++; 
      k++; 
    } 

    /* Copy remaining elements of R[] if any */
    while (j < n2) 
    { 
      arr[k] = R[j]; 
      j++; 
      k++; 
    } 
  } 

  // Main function that sorts arr[l..r] using 
  // merge() 
  void sort(int arr[], int n, int r) 
  { 
    if (n < r) 
    { 
      // Find the middle point 
      int m = (n+r)/2; 

      // Sort first and second halves 
      sort(arr, n, m); 
      sort(arr , m+1, r); 

      // Merge the sorted halves 
      merge(arr, n, m, r); 
    } 
  } 

  /* A utility function to print array of size n */
  static void printArray(int arr[]) 
  { 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
      System.out.print(arr[i] + " "); 
    System.out.println(); 
  } 

  // Driver method 
  public static void main(String args[]) 
  { 
    int arr[] = {182, 911, 143, 415, 614, 417}; 

    printArray(arr); 

    MergeSortExample  ob = new MergeSortExample (); 
    ob.sort(arr, 0, arr.length-1); 
    printArray(arr); 
  } 
} 

Output: 182 911 143 415 614 417 143 182 415 417 614 911