How to Apply Common Algorithms to Java Collections

The Collection Framework is perhaps the most used library among the entire core API group in Java. A Collection is basically a container to store objects as an element of that collection. The thing that sets it apart from other primitive repositories such as simple arrays is the safety and convenience of many of its utilities. A programmer would find the complimentary services of this framework quite useful. The Collection Framework also provides features to apply different algorithms on all or a few elements of a collection, such as searching through a collection, sorting or shuffling elements of a collection, fetch a read only view of a collection, and so forth. This article focuses on some of its common algorithmic application to collection elements in Java.

Collection and Collections

The algorithms that are typically applied to a collection are provided in a class named Collections. To allay confusion, remember that the names Collection and Collections are distinct; one is an interface and another is a pure class defined both within the java.util package.

A collection is an interface that is the parent of most of the collection interfaces defined in the collection framework. This interface implements Iterable, another interface primary used for traversing through the collection elements. There are many sub interfaces and sub classes that extend and implement the Collection interface respectively. These inherited sub classes and sub interfaces add a few for specialized mechanisms to serve a specific purpose. For example, Collection extended by the Set interface ensures that the collection elements do not contain any duplicates; similarly, List maintains an ordered collection of elements that can be referred to by their positional indexes.

Collections, on the other hand, is a class with an exclusive collection of static methods and fields. This means that these methods can be directly referred to as and when required by the class name itself (without creating an object instance of the Collections class). These methods are polymorphic implementation of some common algorithms frequently required by the programmer, such as sorting, searching, swapping, shuffling, and so on. The methods are invoked to operate on the elements of Collection. However, they are defined in such a manner that they do not to change the actual data, but operate on the collection wrappers that return a new collection backed by a specified collection. This keeps your original collection safe.

Let’s check out some common usages.

Sorting

Suppose we want to sort a list of data. We can use one of two methods:

• static <T extends Comparable<? super T>> void sort(List<T> list)
• static <T> void sort(List<T> list, Comparator<? super T> c)<T> void sort

By default, sorting follows a natural order (ascending). The natural order is defined by the Comparable interface. Java relies on a (modified) Merge Sort algorithm because of its stability and performance (time required to sort a given list of elements) in even the worst case scenario. The performance can be measured in O(n log n), where n is the number of elements in the list. What it does internally is copy all the elements of the list into an array, apply the sorting technique, and then copy back to the List. So, any exception that occurred during sorting does not really affect the actual data.

package org.algo.example;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

   public static void main(String[] args) {

      List<String> list = new ArrayList<>();
      list.add("Cumin");
      list.add("Raisin");
      list.add("Chickpeas");
      list.add("Strawberry");
      list.add("Fenugreek");
      list.add("Nutmeg");
      list.add("Cloves");
      list.add("Parsley");
      list.add("Corriander");
      list.add("Fennel");
      System.out.println("Before sorting: "+list);
      Collections.sort(list);
      System.out.println("After sorting: "+list);
   }
}

The List<E> interface, however, has its own sort method called:

sort(Comparator<? super E> c)

This method is introduced in Java 8. This method can be applied conveniently without the need to use a sort method from the Collections class.

package org.algo.example;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {

   public static void main(String[] args) {
      List<String> list = new ArrayList<>();
      list.add("Cumin");
      // ...
      list.add("Fennel");
      System.out.println("Before sorting: "+list);
      list.sort(Comparator.comparing(String::length));
      System.out.println("After sorting: "+list);
   }
}

Searching

Similarly, there are two methods to search an element from the list, such as

• static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
• static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

The binary search algorithm is the fastest searching technique known to man, but it can be applied only in a sorted list. According to the Java documentation, the list must be sorted in ascending order according to the natural ordering of the elements before calling this method. Otherwise, the result of a binary search method applied to an unsorted list is undefined. It normally takes Order of, O(log n) on random access list; also, it may take Order O(n), time depending upon how large the list is or whether the list implements a RandomAccess interface or not. In this case, the method uses an iterative based binary search. Iterative based binary searching is done on links that take O(n) time whereas the actual element comparison takes O(log n) as we know. So, O(n) + O(log n) = O(n) time, according to big O. Let’s see a quick example.

package org.algo.example;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

   public static void main(String[] args) {

      List<String> list = new ArrayList<>();
      list.add("Cumin");
      // ...
      list.add("Fennel");

      Collections.sort(list);
      int index=Collections.binarySearch(list,
         "Parsley");

      System.out.println("After searching: "
         +list.get(index));
   }
}

If the searched element is found, the method returns the index; otherwise, it returns a negative value defined by ( – (insertion_point) – 1 ). The insertion point is the point at which the key would be inserted into the list, meaning that, by the negative number returned, you’ll know exactly where the (not found) value would be inserted (if you insert it into the list subsequently). If the returned negative value is -7, the value will be inserted at the 6^th index; similarly for -3, at the index 2^nd, and so on.

Some Other Algorithms

Shuffling provides a random permutation of elements in the List. This can be applied with the help of two methods, one with default sources of randomness and another where a custom random source can be supplied.

• public static void shuffle(List<?> list)
• public static void shuffle(List<?> list, Random rnd)

Internally, what it does is traverse the list backward from the last element to the second and swap the randomly selected element into the current position, inclusively. Let’s see an example:

package org.algo.example;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

   public static void main(String[] args) {

      List<String> list = new ArrayList<>();
      list.add("Cumin");
      // ...
      list.add("Fennel");

      System.out.println("Before shuffle: "+list);
      Collections.shuffle(list);
      System.out.println("After shuffle: "+list);
   }
}

Similarly, we can reverse a list.

public static void reverse(List<?> list)

System.out.println("Before Reverse "+list);
Collections.reverse(list);
System.out.println("After Reverse "+list);

Swap elements at list index.

public static void swap(List<?> list, int i, int j)

System.out.println("Before swap "+list);
Collections.swap(list,4,5);
System.out.println("After swap "+list);

Rotating elements in the list.

The rotations will be done in a manner where the element at index say, i, will be the element previously at ( i – distance) mod list.size() for all values 0 to list.size()-1, inclusive. The method signature is as follows.

public static void rotate(List<?> list,int distance)

And can be implemented in the following manner:

System.out.println("Before rotate "+list);
Collections.rotate(list,3);

System.out.println("After rotate "+list);

This will make the third element from the end of the list as the first element, the last second element will be the second element, and the last element will be the first element.

Conclusion

The java.util package contains utility classes that form the base of the Java Collection Framework. Java.util.Collections is one of the utility classes that contains only static methods. These methods define many common algorithms, such as shuffling elements in a collection, rotating its elements, sorting elements of a list, and the like. The Collections class also contains methods to obtain different views of collections, such as read-only view, synchronized view, un-modifiable view, and so forth.