Generic Bubble Sort Java Program

In this post we’ll see how to write a Bubble Sort program as a Generic class in Java which can be used with arrays of different data types.

Bubble Sort- Java Generic class

In the generic class used for Bubble Sort we use a bounded parameter to restrict the type to be of type Comparable. That is done as we do need to compare the elements for sorting for which compareTo() method of the Comparable is used.

import java.util.Arrays;

public class BubbleSortGeneric<T extends Comparable<? super T>> {
  T[] array;
  BubbleSortGeneric(T[] array){
    this.array = array;
  }
  
  private T[] bubbleSort(){
    for(int i = array.length; i > 1; i--){
      for(int j = 0; j < i - 1; j++){
        //if greater swap elements
        if(array[j].compareTo(array[j+1]) > 0){
          swapElements(j, array);
        }
      }            
    }
    return array;
  }
  private void swapElements(int index, T[] arr){
    T temp = arr[index];
    arr[index] = arr[index+1];
    arr[index+1] = temp;        
  }
  public static void main(String[] args) {
    Integer[] intArr = {47, 85, 62, 34, 7, 10, 92, 106, 2, 54};
    BubbleSortGeneric<Integer> bsg1 = new BubbleSortGeneric<Integer>(intArr);
    Integer[] sa1 = bsg1.bubbleSort();
    System.out.println("Sorted array- " + Arrays.toString(sa1)); 
    
    String[] strArr = {"Earl", "Robert", "Asha", "Arthur"};
    BubbleSortGeneric<String> bsg2 = new BubbleSortGeneric<>(strArr);
    String[] sa2 = bsg2.bubbleSort();
    System.out.println("Sorted array- " + Arrays.toString(sa2));
  }
}
Output
Sorted array- [2, 7, 10, 34, 47, 54, 62, 85, 92, 106]
Sorted array- [Arthur, Asha, Earl, Robert]

That's all for the topic Generic Bubble Sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

Insertion Sort Java Program

This tutorial shows how to write Insertion sort program in Java. Insertion sort is considered the best among the three simple sorting algorithms, the other two simple sorting algorithms are Bubble sort and Selection sort. Though the time complexity of Insertion sort is also O(n2) but it is considered much faster than bubble sort because of less number of swaps and faster than Selection sort in most scenarios.

Insertion sort algorithm

Insertion sort works on the concept of “partially sorted”, at any given point elements on the left hand side of the current index are considered sorted. Note that those elements are considered sorted among themselves as they are not yet at their final position that is why term “partially sorted”. Any remaining element (element at the current index or the remaining elements on the right side) may have to inserted in between the previously sorted elements which will require shifting of the elements to the right to make place for the inserted element.

For example if current index is 3 in an array then element at index 0..2 are considered sorted amongst themselves.

Insertion Sort Java Program

Now element at the current index has to be inserted as the leftmost element means shifting elements at index 0..2 to the right to make place for the insertion making the array as [1 3 5 7 12 10]

Insertion sort example

Here is an example with an array of length 4 to understand insertion sort algorithm. Suppose the passed array is [6, 4, 2, 9].

  1. In first iteration element at index 1 i.e. 4 is compared with element on its left which is 6. Since 4 is smaller so it has to be inserted at the index 0. To make place for it elements have to be shifted right which temporarily makes the array as [6, 6, 2, 9] then 4 is inserted to make the array as [4, 6, 2, 9] after first iteration.
  2. In second iteration element at index 2 is compared with elements on its left (index 1 and 0). Since 2 is smaller than 6 so shifting happens making the array temporarily as [4, 6, 6, 9], 2 is smaller then 4 too so again shifting happens making the array temporarily as [4, 4, 6, 9]. Now 2 is inserted to make the array as [2, 4, 6, 9] after second iteration.
  3. In third iteration element at index 3 is compared with elements on its left (index 2, 1 and 0). Since 9 is greater than all the elements so no swapping required in this iteration. Thus the sorted array is [2, 4, 6, 9].

Insertion sort Java Program

public class InsertionSort {
  public static void main(String[] args) {
    int[] arr = {25, 34, 10, 7, 15, 92, 53, 72, 39, 45};
    System.out.println("Original array- " + Arrays.toString(arr));
    int[] sortedArray = insertionSort(arr);      
    System.out.println("Sorted array- " + Arrays.toString(sortedArray));
  }
	
  private static int[] insertionSort(int[] arr){
    int j;
    for(int i = 1; i < arr.length; i++){
      int temp = arr[i];
      j = i;
      // from current index move left
      while(j > 0 && arr[j - 1] > temp){
        // shift elements to right
        arr[j] = arr[j - 1];
        --j;
      }
      // insert element at the new index position
      arr[j] = temp;
    }
    return arr;
  }
}
Output
Original array- [25, 34, 10, 7, 15, 92, 53, 72, 39, 45]
Sorted array- [7, 10, 15, 25, 34, 39, 45, 53, 72, 92]

Insertion sort space and time complexity

If you notice the algorithm in first iteration at most 1 comparison is required, in second 2 and for last element at most N-1 comparisons are required making the total number of comparisons as N*(N-1)/2

Thus the average and worst case time complexity for Insertion sort is O(n2).

Insertion sort is an in place sorting algorithm requiring no auxiliary space thus the space complexity of Insertion sort is O(1).

That's all for the topic Insertion Sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

Selection Sort Java Program

This post shows how to write Selection sort program in Java.

Selection sort is also an in place sorting algorithm like Bubble sort that works by comparing and swapping elements in each pass.

Selection sort algorithm

Selection sort works as follows-

  1. Start with the left most element (index 0) and compare it with the elements on the right side to see if there is any element smaller than that element. If yes then this new element becomes the lowest element for further comparisons in that iteration.
  2. By the end of the iteration you get the index of the lowest element.
  3. Swap the lowest element with the leftmost element. So, by the end of the first pass you have the lowest element at its proper place.
  4. In the next pass start with index 1 and again follow the same process.

For example if array is {5, 4, 7, 1, 8} then start with element at index 0 and compare it with adjacent element.

Selection sort Java

After first pass you have the index of the lowest element which is then swapped with the element at index 0. That ends the first pass.

In the second pass start with the 4 (element at index 1) and again compare the elements.

Selection sort Java Program

public class SelectionSort {
  public static void main(String[] args) {
    int[] arr = {25, 34, 10, 7, 15, 92, 53, 72, 39, 45};
    System.out.println("Original array- " + Arrays.toString(arr));
    int[] sortedArray = selectionSort(arr);
    System.out.println("Sorted array- " + Arrays.toString(sortedArray));
  }
	
  private static int[] selectionSort(int[] arr){
    int index;
    for(int i = 0; i < arr.length - 1; i++){
      index = i;
      for(int j = i+1; j < arr.length; j++){
        //if lower than the current lowest assign this index
        if(arr[j] < arr[index]){
          index = j;
        }
      }
      // swap so that smallest element in this pass
      // is at its proper place
      swapElements(i, index, arr);
    }
    return arr;
  }
    
  private static void swapElements(int index, int lowest, int[] arr){
    int temp = arr[index];
    arr[index] = arr[lowest];
    arr[lowest] = temp;
  }
}
Output
Original array- [25, 34, 10, 7, 15, 92, 53, 72, 39, 45]
Sorted array- [7, 10, 15, 25, 34, 39, 45, 53, 72, 92]

Selection sort space and time complexity

Time complexity of selection sort is O(N2) which is same as the time complexity of bubble sort but the number of swaps required are comparatively lesser in Selection sort than Bubble sort.

No extra space is required so the space complexity of Selection sort is O(1).

That's all for the topic Selection Sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

Bubble Sort Java Program

This tutorial shows how to write Bubble sort program in Java. Bubble sort is considered the simplest sorting algorithm out of the three simple sort algorithms, other two being Selection sort and Insertion sort, that work by comparing and swapping elements in each pass. Since there are a large number of comparisons and swaps Bubble sort is also considered the slowest sorting algorithm.

Bubble sort algorithm

Bubble sort works as follows-

You start from the left end and compare the first two elements (i.e. element at index 0 and index 1). If element on the left is greater than the element on right ( element at 0 > element at 1) you swap those two.

Move to next index and compare the two adjacent elements (i.e. element at index 1 and index 2). Again if element on the left is greater than the element on right you swap them.

This process is repeated until you reach the rightmost element. This is the first pass of the bubble sort and by the end of the first pass you have the greatest element at the rightmost end. In this sorting technique greatest elements bubble up to the higher indices of the array thus the name bubble sort.

In the next pass you start again from the first two elements (i.e. element at index 0 and index 1) and do the same comparing and swapping. Only difference is that in this pass iteration will be done for (N – 1) elements as element at the rightmost end is already at its sorted position.

For example if you have an array [6, 3, 10, 7, 1] then the first pass can be depicted as follows.

Bubble Sort in Java

In the first iteration first two elements (6 and 3) are compared, since 6 is greater than 3 so elements are swapped. Same way in the next iteration 6 and 10 are compared and so on. By the end of the first pass greatest element in the array (10) bubbles up to the top of the array.

In the next pass only (N – 1) elements are considered thus the part of the array used is [3, 6, 7, 1].

Bubble Sort Java program

public class BubbleSort {
  public static void main(String[] args) {
    int[] arr = {61, 34, 10, 0, 15, 112, 53, 78, 39, 45};
    System.out.println("Original Array " +  Arrays.toString(arr));
    int[] sortedArr = bubbleSort(arr);   
    System.out.println("Sorted Array " + Arrays.toString(sortedArr));
  }
  private static int[] bubbleSort(int[] arr){ 
    int n = arr.length;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < (n - i - 1); j++){
        if(arr[j] > arr[j+1]){
          swapElements(j, arr);
        }
      }  
    }       
    return arr;
  }
    
  private static void swapElements(int index, int[] arr){
    int temp = arr[index];
    arr[index] = arr[index+1];
    arr[index+1] = temp;        
  }
}
Output
Original Array [61, 34, 10, 0, 15, 112, 53, 78, 39, 45]
Sorted Array [0, 10, 15, 34, 39, 45, 53, 61, 78, 112]

Bubble sort space and time complexity

Time complexity of bubble sort is O(n2).

No extra space is required so the space complexity of bubble sort is O(1).

That's all for the topic Bubble Sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

Java Immutable List With Examples

In Java 9 Immutable collections were added in Java that makes it easy to create an immutable List, Set or Map. In this article we’ll see how to use Immutable List in Java.

Elements cannot be added, removed, or replaced once an immutable list is created. Calling any mutator method on the List will always cause UnsupportedOperationException to be thrown.

Creating Immutable List before Java 9

Before Java 9 only way to create an immutable list was to use Collections.unmodifiableList(List<? extends T> list) method.

Here is an example showing how to create unmodifiable list before Java 9. In the program you can see that original list can still be changed (a new element is added to it). On the other hand unmodifiable list instance can’t be mutated.

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

public class ImmutList {
  public static void main(String[] args) {
    List<String> numList = new ArrayList<>();
    numList.add("1");
    numList.add("2");
    numList.add("3");
    numList.add("4");
    // Creating Immutable List
    List<String> anotherList = Collections.unmodifiableList(numList);
    numList.add("5");
    System.out.println("Number List- " + numList);
    // This throws exception
    anotherList.add("6");
  }
}
Output
Number List- [1, 2, 3, 4, 5]
Exception in thread "main" java.lang.UnsupportedOperationException
	at java.base/java.util.Collections$UnmodifiableCollection.add(Collections.java:1058)
	at com.knpcode.proj.Programs.ImmutList.main(ImmutList.java:18)

Another way to do that is to use Arrays.asList() method, which is less verbose.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ImmutList {
  public static void main(String[] args) {
    List<String> numList = Arrays.asList("1", "2", "3", "4");
    // Creating Immutable List
    List<String> anotherList = Collections.unmodifiableList(numList);
    numList.add("5");
    System.out.println("Number List- " + numList);
    // This throws exception
    anotherList.add("6");
  }
}

Using this way even in the original list elements can’t be added.

Creating Immutable List Java 9 onward

Java 9 onward there are two static factory methods which provide a convenient way to create unmodifiable lists.

  1. List.of (Added in Java 9)
  2. List.copyOf (Added in Java 10)

The List instances created by these methods have the following characteristics:

  • They are unmodifiable. Elements cannot be added, removed, or replaced. Calling any mutator method on the List will always cause UnsupportedOperationException to be thrown. However, if the contained elements are themselves mutable, this may cause the List's contents to appear to change.
  • Null elements can't be added to immutable list. Attempts to create them with null elements result in NullPointerException.
  • They are serializable if all elements are serializable.
  • The order of elements in the list is the same as the order of the provided arguments, or of the elements in the provided array.
List.of method example

List.of() static method has both fixed-argument form and varargs form.

Fixed-argument form provides options to create list from 0 to 10 elements and the form of these method is as follows.

of()- Returns an unmodifiable list containing zero elements.
of(E e1)- Returns an unmodifiable list containing one element.
of(E e1, E e2)	Returns an unmodifiable list containing two elements.
..
..
of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9)- Returns an unmodifiable list containing nine elements.
of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10)- Returns an unmodifiable list containing ten elements.

Method to add arbitrary number of elements (varargs)

of(E... elements)- Returns an unmodifiable list containing an arbitrary number of elements.
import java.util.List;

public class ImmutList {
  public static void main(String[] args) {
    List<String> numList = List.of("1", "2", "3", "4");    
    System.out.println("Number List- " + numList);
    // Throws exception
    numList.add("5");
  }
}
List.copyOf method example

Using copyOf() method you can create an immutable list using an existing collection. If the Collection, used to create Immutable list, is subsequently modified, the returned List will not reflect such modifications.

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

public class ImmutList {
  public static void main(String[] args) {
    List<String> numList = new ArrayList<>();
    numList.add("1");
    numList.add("2");
    numList.add("3");
    numList.add("4");
    List<String> iList = List.copyOf(numList);    
    System.out.println("Immutable List- " + iList);
    // change original collection
    numList.add("5");
    System.out.println("Immutable List- " + iList);
  }
}
Output
Immutable List- [1, 2, 3, 4]
Immutable List- [1, 2, 3, 4]

As you can see numList which is used to create the immutable list is later changed but that change doesn’t get reflected in the immutable list.

That's all for the topic Java Immutable List With Examples. If something is missing or you have something to share about the topic please write a comment.


You may also like

ArrayList Vs LinkedList in Java

In Java Collections framework there are two general-purpose List implementations— ArrayList and LinkedList. In this post we'll see the differences between ArrayList and LinkedList in Java to understand these two implementations better. Knowing the differences between ArrayList and LinkedList will also help you to determine which implementation is better in which scenario.

ArrayList Vs LinkedList in Java

1- How they are internally implemented-

ArrayList internal implementation uses an array to store its element. The size of the array can be increased dynamically if needed that is why ArrayList is known as the resizeable array implementation.

LinkedList is internally implemented as a doubly linked list where elements are stored as object of type node. In the node object apart from the element, references of the previous and next nodes are also stored.

2- Initial capacity-

ArrayList has a constructor ArrayList(int initialCapacity) which can construct an ArrayList of the specified capacity. Even if no initial capacity is specified ArrayList is created with the default capacity of 10.

LinkedList in Java doesn’t have any initial capacity, as and when an element is added object of type Node is created.

3- Adding element-

ArrayList in Java has an array of size 10 created by default even if internal capacity is not specified. Since array is created as a contiguous memory block so adding element in an ArrayList is as simple as putting element in the next index but there are some complexities involved.
If array is full then the insertion of next element in the ArrayList would require resizing the array and moving all the existing element of the ArrayList to the new array.
If elements are frequently added to the beginning of the ArrayList then also there is added overhead of shifting all the elements of the array to make place for the new element. Same overhead is there of you add element using the add(int index, E element) method to add element at the specified position.
With all these possibilities while adding element to the ArrayList, add operation in ArrayList runs in amortized constant time, that is, adding n elements requires O(n) time.

LinkedList insertion is O(1) as adding element just requires to adjust references for previous and next nodes.

But one thing to note here is that the constant factor in ArrayList is low compared to that for the LinkedList implementation.

4- Removing element-

Removing element from an ArrayList requires less time reaching to the element that has to be removed (just accessing the array index) but requires shifting all the elements, after the element that has to be removed, backward to fill the space left by the removed element. So removing the last element of the ArrayList is O(1) where as for the first element is O(n).

In the case of LinkedList also performance is O(n) as reaching to the element that has to be removed is a linear operation. Again remove() and removeFirst() methods which remove the first element require O(1) time. Removing last element using removeLast() method will also be O(1) as reference to the last node is also stored.

5- Accessing element-

In ArrayList retrieving an element using get(int index) method is O(1) as it just need to access that array index.

In case of LinkedList get(int index) method is O(n) as it requires linear traversal to reach to that index.

6- Removing element when iterating-

In ArrayList deleting element while iterating over the List still has that overhead of shifting the elements.

In LinkedList deleting element while iterating over the List is O(1) as iterator is already positioned at the element that has to be removed.

7- Overall performance-

As per official JavaDocs also ArrayList should be preferred over LinkedList.

"If you think you want to use a LinkedList, measure the performance of your application with both LinkedList and ArrayList before making your choice; ArrayList is usually faster."

Reference: https://docs.oracle.com/javase/tutorial/collections/implementations/list.html

That's all for the topic ArrayList Vs LinkedList in Java. If something is missing or you have something to share about the topic please write a comment.


You may also like

Convert Array to ArrayList in Java

In the post How to Convert ArrayList to Array in Java we have already seen different ways of doing that conversion. This post is about the other way round how to convert array to ArrayList in Java.

Options for converting array to ArrayList in Java

  1. Using Arrays.asList() method. See example.
  2. Using Collections.addAll() method. See example.
  3. Java 8 onward you can use Java Stream API for converting array to ArrayList in Java. See example.
  4. Doing it manually without using any API methods. See example.

Using Arrays.asList() method

Using Arrays.asList() method you can convert array to ArrayList. The returned list by this method is backed by the array, thus any change in the List will be reflected in array too.

import java.util.Arrays;
import java.util.List;

public class ArrayToList {
  public static void main(String[] args) {
    String[] carArray = {"Audi", "Jaguar", "BMW", "Mini Cooper"};
    // Converting array to arraylist
    List<String> carList = Arrays.asList(carArray);
    System.out.println("List Elements- " + carList);
    // changing element in List
    carList.set(1, "Mercedes");
    System.out.println("Array Elements- " + Arrays.toString(carArray));
  }
}
Output
List Elements- [Audi, Jaguar, BMW, Mini Cooper]
Array Elements- [Audi, Mercedes, BMW, Mini Cooper]

As you can see from the output when an element at index 1 is changed in the ArrayList that change is reflected to the array too.

Another drawback of this method is that returned list is fixed you can’t add or remove element to the returned List. Any attempt to add or remove elements will throw java.lang.UnsupportedOperationException.

import java.util.Arrays;
import java.util.List;

public class ArrayToList {
  public static void main(String[] args) {
    String[] carArray = {"Audi", "Jaguar", "BMW", "Mini Cooper"};
    // Converting array to arraylist
    List<String> carList = Arrays.asList(carArray);
    System.out.println("List Elements- " + carList);
    // trying to remove element
    carList.remove("Audi");
    System.out.println("Array Elements- " + Arrays.toString(carArray));
  }
}
Output
List Elements- [Audi, Jaguar, BMW, Mini Cooper]
Exception in thread "main" java.lang.UnsupportedOperationException: remove
	at java.base/java.util.Iterator.remove(Iterator.java:102)
	at java.base/java.util.AbstractCollection.remove(AbstractCollection.java:299)
	at com.knpcode.ArrayToList.main(ArrayToList.java:14)

If you need to modify the list you get by converting array to ArrayList then you should create a new ArrayList using the returned list.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArrayToList {
  public static void main(String[] args) {
    String[] carArray = {"Audi", "Jaguar", "BMW", "Mini Cooper"};
    // Converting array to arraylist
    List<String> carList = new ArrayList<String>(Arrays.asList(carArray));
    System.out.println("List Elements- " + carList);
    // changing element in List
    carList.remove("Audi");
    System.out.println("Array Elements- " + Arrays.toString(carArray));
    System.out.println("List Elements- " + carList);
  }
}
Output
List Elements- [Audi, Jaguar, BMW, Mini Cooper]
Array Elements- [Audi, Jaguar, BMW, Mini Cooper]
List Elements- [Jaguar, BMW, Mini Cooper]

As you can see from the output by creating a new ArrayList you can structurally modify it and now changes are not reflected to the array too.

Using Collections.addAll() method

You can also use Collections.addAll() method to convert array to ArrayList in Java. You need to pass both List and array as arguments to this method.

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

public class ArrayToList {
  public static void main(String[] args) {
    String[] carArray = {"Audi", "Jaguar", "BMW", "Mini Cooper"};
    List<String> carList = new ArrayList<String>();
    Collections.addAll(carList, carArray);
    System.out.println("List Elements- " + carList);
  }
}
Output
List Elements- [Audi, Jaguar, BMW, Mini Cooper]

Java Stream API’s collect() method

Java 8 onward you can also use Collectors in Java Stream API for converting array to ArrayList in Java.

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class ArrayToList {
  public static void main(String[] args) {
    String[] carArray = {"Audi", "Jaguar", "BMW", "Mini Cooper"};
    List<String> carList = Stream.of(carArray).collect(Collectors.toList());
    System.out.println("List Elements- " + carList);
  }
}
Output
List Elements- [Audi, Jaguar, BMW, Mini Cooper]

Without using any API method

You can convert array to ArrayList by writing your own logic too rather than using any API method. It required just a simple for loop in which you need to add iterated element of array to ArrayList.

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

public class ArrayToList {
  public static void main(String[] args) {
    String[] carArray = {"Audi", "Jaguar", "BMW", "Mini Cooper"};
    List<String> carList = new ArrayList<String>();
    for(String car : carArray) {
      carList.add(car);
    }
    System.out.println("List Elements- " + carList);
  }
}
Output
List Elements- [Audi, Jaguar, BMW, Mini Cooper]

That's all for the topic Convert Array to ArrayList in Java. If something is missing or you have something to share about the topic please write a comment.


You may also like

How to Synchronize Java ArrayList

This post shows how to synchronize ArrayList in Java and what other thread safe alternatives are available to use.

ArrayList in Java is not thread safe as it is not synchronized by default. If you are using ArrayList in a multi-threaded environment where it is accessed by multiple threads concurrently and it is structurally modified too by even a single thread then it must be synchronized externally. A structural modification is defined as any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.

Options for thread-safe List

If you want to synchronize ArrayList in Java or looking for a thread-safe alternative of ArrayList then there are following options.

  1. Using Vector class- Vector is synchronized and a thread safe implementation of List. But the problem is all of its methods are synchronized on a single lock so at any time only one thread can use Vector even if it is get() method. That makes Vector very slow to use.
  2. Using Collections.synchronizedList() method- Using this method you can synchronize ArrayList.
  3. Using CopyOnWriteArrayList- Another option is to use CopyOnWriteArrayList which is a thread-safe variant of ArrayList. In CopyOnWriteArrayList all mutative operations (add, set) are implemented by making a fresh copy of the underlying array. Since a new copy is made every time List is changed that is why using CopyOnWriteArrayList is ordinarily too costly. It may be more efficient if you have more traversal operations than mutations and you don't want to synchronize traversals.

Using Collections.synchronizedList() method

Before seeing an example of synchronizing ArrayList in Java using Collections.synchronizedList() method let’s see what may happen if you use ArrayList in a multi-threaded environment with out synchronizing it.

In the Java program four threads are created, each of these thread adds 5 elements to the list. After all the threads are done list size should be 20.

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

public class ListSynchro implements Runnable{    
  private List<Integer> normalList;    
  public ListSynchro(List<Integer> normalList){
    this.normalList = normalList;
  }
    
  public static void main(String[] args) {
    List<Integer> normalList = new ArrayList<Integer>();
    Thread t1 = new Thread(new ListSynchro(normalList));
    Thread t2 = new Thread(new ListSynchro(normalList));
    Thread t3 = new Thread(new ListSynchro(normalList));
    Thread t4 = new Thread(new ListSynchro(normalList));
        
    t1.start();
    t2.start();
    t3.start();
    t4.start();
        
    try {
      t1.join();
      t2.join();
      t3.join();
      t4.join();
    } catch (InterruptedException e) {    
      e.printStackTrace();
    }
    System.out.println("Size of list is " + normalList.size());
  }

  @Override
  public void run() {
    System.out.println("in run method" + Thread.currentThread().getName());
    for(int i = 0; i < 5; i++){
      normalList.add(i);
      try {
        // delay to verify thread interference
        Thread.sleep(500);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  }
}
Output
in run methodThread-0
in run methodThread-2
in run methodThread-3
Size of list is 15

As you can see in one of the run size of the list is 15 because of the thread interference.

Here is the same example again where ArrayList is synchronized to make it thread safe.

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

public class ListSynchro implements Runnable{    
  private List<Integer> normalList;   
  public ListSynchro(List<Integer> normalList){
    this.normalList = normalList;
  }
    
  public static void main(String[] args) {
    // Synchronized ArrayList
    List<Integer> normalList = Collections.synchronizedList(new ArrayList<Integer>());
    Thread t1 = new Thread(new ListSynchro(normalList));
    Thread t2 = new Thread(new ListSynchro(normalList));
    Thread t3 = new Thread(new ListSynchro(normalList));
    Thread t4 = new Thread(new ListSynchro(normalList));
        
    t1.start();
    t2.start();
    t3.start();
    t4.start();
        
    try {
      t1.join();
      t2.join();
      t3.join();
      t4.join();
    } catch (InterruptedException e) {    
      e.printStackTrace();
    }
    System.out.println("Size of list is " + normalList.size());

  }

  @Override
  public void run() {
    System.out.println("in run method" + Thread.currentThread().getName());
    for(int i = 0; i < 5; i++){
      normalList.add(i);
      try {
        // delay to verify thread interference
        Thread.sleep(500);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  }
}
Output
in run methodThread-1
in run methodThread-0
in run methodThread-3
in run methodThread-2
Size of list is 20

Iterating a synchronized List

As per Java docs even if you use Collections.synchronizedList() to get a synchronized list, it is imperative that you manually synchronize on the returned list when traversing it via Iterator, Spliterator or Stream:

public class ListItr {
  public static void main(String[] args) {
    List<String> carList = Collections.synchronizedList(new ArrayList<String>());
    carList.add("Audi");
    carList.add("Jaguar");
    carList.add("BMW");
    carList.add("Mini Cooper");
    synchronized (carList) {
      // Must be in synchronized block
      Iterator<String> itr = carList.iterator(); 
      while (itr.hasNext()) {
        System.out.println(itr.next());
      }
    }
  }
}

Using CopyOnWriteArrayList

Another option to have a thread safe list is to use CopyOnWriteArrayList. Since a new copy of the list is made if there is any mutation so there is no thread interference.

Let’s see it using a simple example where a CopyOnWriteArrayList is created and then iterated. While iteration an element is removed using the List’s remove method, it still won’t throw ConcurrentModificationException. In the output you can see iteration is still displaying all the elements as iteration is done on a separate copy of CopyOnWriteArrayList.

import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyItr {
  public static void main(String[] args) {
    List<String> carList = new CopyOnWriteArrayList<String>();
    carList.add("Audi");
    carList.add("Jaguar");
    carList.add("BMW");
    carList.add("Mini Cooper");
    Iterator<String> i = carList.iterator(); 
    while (i.hasNext()){            
      carList.remove("Jaguar");
      System.out.println(i.next()); 
    } 
    System.out.println("List after removal" + carList); 
  }
}
Output
Audi
Jaguar
BMW
Mini Cooper
List after removal[Audi, BMW, Mini Cooper]

That's all for the topic How to Synchronize Java ArrayList. If something is missing or you have something to share about the topic please write a comment.


You may also like

How to Sort ArrayList of Objects in Java

In this post we’ll see how to sort ArrayList of objects in Java. In the post How to Sort ArrayList in Java we have already seen how you can sort ArrayList of String, Date or any Wrapper class (Integer, Float etc.). All those classes already implement Comparable interface so you just need to pass the list to Collections.sort() method to sort it.

When you need to sort ArrayList of custom objects in Java, you will have to make sure that the class whose objects are stored in the ArrayList implements Comparable interface or you have a Comparator implementation ready to be used.

Implementation of the Comparable interface will set the natural ordering of the class. If you want to sort in any other order rather than natural ordering set by Comparable then you can implement Comparator and use the sort() method of the Collections class which takes Comparator as argument.

If your class doesn’t implement Comparable interface and Comparator is also not specified then using an ArrayList of such objects with sort() method will result in compile time error.

sort(List<T> list, Comparator<? super T> c)- Sorts the specified list according to the order induced by the specified Comparator.

Sorting ArrayList of objects using Comparable

Here we have a class Employee and you want to sort by empName field of the class. Then Employee class should implement the Comparable interface and provide implementation of the compareTo() method.

public class Employee implements Comparable{
  private int empId;
  private String empName;
  private int age;
  Employee(int empId, String empName, int age){
    this.empId = empId;
    this.empName = empName;
    this.age = age;
  }
  public int getEmpId() {
    return empId;
  }
  public void setEmpId(int empId) {
    this.empId = empId;
  }
  public String getEmpName() {
    return empName;
  }
  public void setEmpName(String empName) {
    this.empName = empName;
  }
  public int getAge() {
    return age;
  }
  public void setAge(int age) {
    this.age = age;
  }
    
  @Override
  public String toString() {    
    return getEmpId() + " " + getEmpName() + " " + getAge();
  }
  @Override
  public int compareTo(Employee o) {
    // Sort by empName in ascending order alphabetically
    return this.getEmpName().compareTo(o.getEmpName());
    /// sort by ascending order of age
    ///return this.getAge() - o.getAge();
  }  
}

Then you can pass ArrayList of Employee class object in Collections.sort() method.

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

public class SortingObjList {
  public static void main(String[] args) {
    List<Employee> empList = new ArrayList<Employee>();
    empList.add(new Employee(1, "Zhiang", 34));
    empList.add(new Employee(2, "Marie", 23));
    empList.add(new Employee(3, "Amy", 31));
    empList.add(new Employee(4, "Robbie", 45));
    empList.add(new Employee(5, "Dean", 26));
    System.out.println("**List elements**");
    for(Employee emp : empList) {
     System.out.println("" + emp);
    }
    // Sorting the list
    Collections.sort(empList);
    System.out.println("**Sorted List**");
    for(Employee emp : empList) {
      System.out.println("" + emp);
    }
  }
}
Output
**List elements**
1 Zhiang 34
2 Marie 23
3 Amy 31
4 Robbie 45
5 Dean 26
**Sorted List**
3 Amy 31
5 Dean 26
2 Marie 23
4 Robbie 45
1 Zhiang 34

Sorting ArrayList of objects using Comparator

Employee class used above implements Comparable and provide implementation of the compareTo() method to sort by name. This sort order becomes the natural ordering of the class but now you are bound with that ordering. What if you want to sort by age now? Answer is write a separate method or class implementing Comparator interface. By implementing Comparator you can have more than one option for sorting.

Here is the updated Employee class with 2 Comparator implementations added to sort by age or to sort by name in reverse order.

import java.util.Comparator;

public class Employee implements Comparable<Employee>{
  private int empId;
  private String empName;
  private int age;
  Employee(int empId, String empName, int age){
    this.empId = empId;
    this.empName = empName;
    this.age = age;
  }
  public int getEmpId() {
    return empId;
  }
  public void setEmpId(int empId) {
    this.empId = empId;
  }
  public String getEmpName() {
    return empName;
  }
  public void setEmpName(String empName) {
    this.empName = empName;
  }
  public int getAge() {
    return age;
  }
  public void setAge(int age) {
    this.age = age;
  }
    
  @Override
  public String toString() {    
    return getEmpId() + " " + getEmpName() + " " + getAge();
  }
  @Override
  public int compareTo(Employee o) {
    // Sort by empName in ascending order alphabetically
    return this.getEmpName().compareTo(o.getEmpName());
    /// sort by ascending order of age
    ///return this.getAge() - o.getAge();
  }
    
  static Comparator<Employee> empCompByAge = new Comparator<Employee>() {
    @Override
    public int compare(Employee emp1, Employee emp2) {
        return emp1.getAge() - emp2.getAge();
    }        
  };

  static Comparator<Employee> empCompByNameDesc = new Comparator<Employee>() {
    @Override
    public int compare(Employee emp1, Employee emp2) {
        return emp2.getEmpName().compareTo(emp1.getEmpName());
    }        
  }; 
}
Then you can pass these Comparator implementations with the sort() method to get the required ordering.
public class SortingObjList {
  public static void main(String[] args) {
    List<Employee> empList = new ArrayList<Employee>();
    empList.add(new Employee(1, "Zhiang", 34));
    empList.add(new Employee(2, "Marie", 23));
    empList.add(new Employee(3, "Amy", 31));
    empList.add(new Employee(4, "Robbie", 45));
    empList.add(new Employee(5, "Dean", 26));
    System.out.println("**List elements**");
    for(Employee emp : empList) {
      System.out.println("" + emp);
    }
    // Sorting the list by employee age
    Collections.sort(empList, Employee.empCompByAge);
    System.out.println("**Sorted List**");
    for(Employee emp : empList) {
      System.out.println("" + emp);
    }
         
    // Sorting the list by employee name in reverse order
    Collections.sort(empList, Employee.empCompByNameDesc);
    System.out.println("**Sorted List**");
    for(Employee emp : empList) {
      System.out.println("" + emp);
    }
  }
}
Output
**List elements**
1 Zhiang 34
2 Marie 23
3 Amy 31
4 Robbie 45
5 Dean 26
**Sorted List by age**
2 Marie 23
5 Dean 26
3 Amy 31
1 Zhiang 34
4 Robbie 45
**Sorted List**
1 Zhiang 34
4 Robbie 45
2 Marie 23
5 Dean 26
3 Amy 31

That's all for the topic How to Sort ArrayList of Objects in Java. If something is missing or you have something to share about the topic please write a comment.


You may also like

How to Sort Java ArrayList

ArrayList in Java is an ordered collection in the sense that it maintains the insertion order of the elements but sometimes you may have a requirement to sort an ArrayList in ascending order or descending order. In this post we’ll see How to sort an ArrayList in Java.

Methods used to sort Java ArrayList

Collections class in Java provides many utility methods that operate on collections, this class also has sort method. Actually sort() method is overloaded in Collections class and there are 2 variants.

  • void sort(List list)- Sorts the specified list into ascending order, according to the natural ordering of its elements.
  • sort(List list, Comparator<? super T> c)- Sorts the specified list according to the order induced by the specified Comparator.

Sorting Java ArrayList example

If you want to sort ArrayList in ascending order then you can just pass the List in Collections.sort() method. All the wrapper classes in Java (Integer, Long etc.), String, Date implements Comparable interface and provide implementation of compareTo() method which decides their natural ordering. So, if you have an ArrayList of String, Integer, Long, Float, Date is will be sorted in ascending order by using sort() method.

Sorting ArrayList of String example code
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortingList {
  public static void main(String[] args) {
    List<String> carList = new ArrayList<String>();
    carList.add("Audi");
    carList.add("Jaguar");
    carList.add("Mini Cooper");
    carList.add("BMW");
    System.out.println("List elements- " + carList);
    // Sorting list
    Collections.sort(carList);
    System.out.println("List elements after sorting- " + carList);
  }
}
Output
List elements- [Audi, Jaguar, Mini Cooper, BMW]
List elements after sorting- [Audi, BMW, Jaguar, Mini Cooper]

Sorting Java ArrayList in descending order

If you want to sort ArrayList in reverse order of the natural ordering then Collections class has a reverseOrder() method that can be used. Alternatively you can write your own Comparator.

reverseOrder()- Returns a Comparator that imposes the reverse of the natural ordering on a collection of objects that implement the Comparable interface.

Sorting Arraylist using reverseOrder method

Since reverseOrder() method returns a Comparator so you will have to use Collections.sort() method where you can pass Comparator as an argument.

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

public class SortingList {
  public static void main(String[] args) {
    List<String> carList = new ArrayList<String>();
    carList.add("Audi");
    carList.add("Jaguar");
    carList.add("Mini Cooper");
    carList.add("BMW");
    System.out.println("List elements- " + carList);
    // Sorting list in reverse order
    Collections.sort(carList, Collections.reverseOrder());
    System.out.println("List elements after sorting- " + carList);
  }
}
Output
List elements- [Audi, Jaguar, Mini Cooper, BMW]
List elements after sorting- [Mini Cooper, Jaguar, BMW, Audi]

Sorting Arraylist by providing own custom Comparator

Collections.reverseOrder() method returns an implementation of Comparator class. Same way you can write your own Comparator for the ordering you want to impose and use that to sort the List.

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

public class SortingList {
  public static void main(String[] args) {
    List<String> carList = new ArrayList<String>();
    carList.add("Audi");
    carList.add("Jaguar");
    carList.add("Mini Cooper");
    carList.add("BMW");
    System.out.println("List elements- " + carList);
    // Sorting list in reverse order
    Collections.sort(carList, new MyComparator());
    System.out.println("List elements after sorting- " + carList);
  }
}

//Comparator class
class MyComparator implements Comparator<String>{
  @Override
  public int compare(String o1, String o2) {
    return o2.compareTo(o1);
  }    
}
Output
List elements- [Audi, Jaguar, Mini Cooper, BMW]
List elements after sorting- [Mini Cooper, Jaguar, BMW, Audi]

That's all for the topic How to Sort Java ArrayList. If something is missing or you have something to share about the topic please write a comment.


You may also like

Comparable Vs Comparator in Java

Comparable and Comparator in Java are two interfaces used to sort a collection of objects. The obvious question is why two interfaces when they both do the same task of sorting the objects. In this post we’ll see what are Comparable and Comparator interfaces in Java, why both are required and differences between Comparable and Comparator in Java.

Comparable interface in Java

Comparable interface in Java has a single method compareTo().

int compareTo(T o)- This method compares the object used to call the method with the object passed as parameter for ordering.

The objects of the class implementing this interface are ordered as per the implementation of the compareTo() method. Since the class itself is implementing the interface so the ordering as provided by Comparable interface is referred to as the class's natural ordering.

Lists (and arrays) storing objects of class that implements this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this interface can be used as keys in a sorted map i.e TreeMap or as elements in a sorted set i.e. TreeSet, without the need to specify a Comparator.

Comparator interface in Java

Comparator interface in Java has a method compare().

int compare(T o1, T o2)- Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Comparator interface is not part of the class which is sorted using the ordering provided by Comparator interface implementation. Comparator interface is implemented as a separate class or as an anonymous class.

Comparators can be passed to a sort method (such as Collections.sort or Arrays.sort) to allow precise control over the sort order.

Comparable and Comparator Java example

Let us see an example to see how sort ordering is done using Comparable and Comparator and why both of them are needed.

There is a Person class with fields firstName, lastName and age. You want to sort Person class objects using the firstName + lastName so the class implements Comparable interface and provide logic for that ordering by overriding the compareTo() method.

public class Person implements Comparable {
  private String firstName;
  private String lastName;
  private int age;
  Person(String firstName, String lastName, int age){
    this.firstName = firstName;
    this.lastName = lastName;
    this.age = age;
  }
  public String getLastName() {
    return lastName;
  }
  public void setLastName(String lastName) {
    this.lastName = lastName;
  }
  public String getFirstName() {
    return firstName;
  }
  public void setFirstName(String firstName) {
    this.firstName = firstName;
  }
  public int getAge() {
    return age;
  }
  public void setAge(int age) {
    this.age = age;
  }
  @Override
  // For sort order - sort on first name, 
  // if equal then sort on lastname
  public int compareTo(Person o) {
    int comp = this.getFirstName().compareTo(o.getFirstName());
    return comp != 0 ? comp :  this.getLastName().compareTo(o.getLastName());
  }

  @Override
  public String toString() {        
    return getFirstName() + " " + getLastName() + " " + getAge();
  }
}

Following class is used to create Person class objects and do the sorting by calling the Collections.sort() method. Since the objects stored in the List are already implementing Comparable interface so the objects will be sorted by using that implementation.

public class SortDemo {
  public static void main(String[] args) {
    List<Person> personList = new ArrayList<Person>();
    personList.add(new Person("William", "Shatner", 60));
    personList.add(new Person("William", "Brooks", 25));
    personList.add(new Person("Persis", "Khambatta", 50));
    personList.add(new Person("James", "Doohan", 70));
    personList.add(new Person("DeForest", "Kelley", 65));

    System.out.println("-- Original List --");
    for(Person person : personList){
     System.out.println("" + person);
    }
    // Sort the list
    Collections.sort(personList);
    System.out.println("--Sorted List--");
    for(Person person : personList){
      System.out.println("" + person);
    } 
  }
}
Output
-- Original List --
William Shatner 60
William Brooks 25
Persis Khambatta 50
James Doohan 70
DeForest Kelley 65
--Sorted List--
DeForest Kelley 65
James Doohan 70
Persis Khambatta 50
William Brooks 25
William Shatner 60

So far you have your class, class’ natural ordering is also defined by implementing the Comparable interface.

Now suppose you have a new requirement to sort the Person class by age or by last name + first name. Person class is already coupled with the Comparable interface and the ordering imposed by that interface. In this sort of scenario you can use Comparator interface, since Comparator can be implemented by another class so you can create different Comparator classes for different sort ordering. Then you can use the Collections.sort() method where Comparator is also passed to sort the objects.

public class Person implements Comparable<Person> {
  private String firstName;
  private String lastName;
  private int age;
  Person(String firstName, String lastName, int age){
    this.firstName = firstName;
    this.lastName = lastName;
    this.age = age;
  }
  public String getLastName() {
    return lastName;
  }
  public void setLastName(String lastName) {
    this.lastName = lastName;
  }
  public String getFirstName() {
    return firstName;
  }
  public void setFirstName(String firstName) {
    this.firstName = firstName;
  }
  public int getAge() {
    return age;
  }
  public void setAge(int age) {
    this.age = age;
  }
  @Override
  // For sort order - sort on first name, 
  // if equal then sort on lastname
  public int compareTo(Person o) {
    int comp = this.getFirstName().compareTo(o.getFirstName());
    return comp != 0 ? comp :  this.getLastName().compareTo(o.getLastName());
  }

  @Override
  public String toString() {        
    return getFirstName() + " " + getLastName() + " " + getAge();
  }
}

// Sorting using age field
class AgeComparator implements Comparator<Person>{
  @Override
  public int compare(Person o1, Person o2) {
    return o1.getAge() >= (o2.getAge()) ? 1 : -1;    
  }    
}
//Sorting using last name if equal then sort on firstName
class NameComparator implements Comparator<Person>{
  @Override
  public int compare(Person o1, Person o2) {
    int comp = o1.getLastName().compareTo(o2.getLastName());
    if(comp == 0){
      comp = o1.getFirstName().compareTo(o2.getFirstName());
    }
    return comp;
  }    
}

As you can see two new Comparator classes are added one that sorts by age and another sorts by last name. Person class still has its Comparable interface implementation defining its natural ordering.

public class SortDemo {
  public static void main(String[] args) {
    List<Person> personList = new ArrayList<Person>();
    personList.add(new Person("William", "Shatner", 60));
    personList.add(new Person("William", "Brooks", 25));
    personList.add(new Person("Persis", "Khambatta", 50));
    personList.add(new Person("James", "Doohan", 70));
    personList.add(new Person("DeForest", "Kelley", 65));
       
    System.out.println("-- Original List --");
    for(Person person : personList){
     System.out.println("" + person);
    }
		 
    // Sort the list by age
    Collections.sort(personList, new AgeComparator());
    System.out.println("--Sorted List by Age--");
    for(Person person : personList){
     System.out.println("" + person);
    } 
     
    // Sort the list by last name
    Collections.sort(personList, new NameComparator());
    System.out.println("--Sorted List by Last Name--");
    for(Person person : personList){
     System.out.println("" + person);
    } 
		 
    // Sort the list by first name - Natural ordering
    Collections.sort(personList);
    System.out.println("--Sorted List by first name--");
    for(Person person : personList){
      System.out.println("" + person);
    } 
  }
}
Output
-- Original List --
William Shatner 60
William Brooks 25
Persis Khambatta 50
James Doohan 70
DeForest Kelley 65
--Sorted List by Age--
William Brooks 25
Persis Khambatta 50
William Shatner 60
DeForest Kelley 65
James Doohan 70
--Sorted List by Last Name--
William Brooks 25
James Doohan 70
DeForest Kelley 65
Persis Khambatta 50
William Shatner 60
--Sorted List by first name--
DeForest Kelley 65
James Doohan 70
Persis Khambatta 50
William Brooks 25
William Shatner 60

As you can see now if you want to sort by age field then you can pass the Comparator that sorts by age in the Collections.sort() method. Same way if you want to sort by lastName field then you can pass the Comparator that sorts by lastName in the Collections.sort() method. If you want to sort by firstName you still have that implementation provided by the implementation of the Comparable interface.

Difference between Comparable and Comparator in Java

Comparable Comparator
Comparable interface has compareTo() method for providing sorting logic. Comparator interface has compare() method for providing sorting logic.
Comparable interface is in java.lang package. Comparator interface is in java.util package.
Comparable interface is implemented by the class whose objects are to be sorted. Comparator interface is implemented by some other class or as an anonymous class.
Since the class whose objects are to be sorted implements the Comparable interface so Comparable can provide only one way of sorting the objects. There can be many Comparator classes providing logic for different sort ordering.
A List or array having objects that implement the Comparable interface can be sorted by just passing the List in Collections.sort() or by using Arrays.sort() for array. In case of Comparator, instance of Comparator has to be passed with the Collections.sort() method.

That's all for the topic Comparable Vs Comparator in Java. If something is missing or you have something to share about the topic please write a comment.


You may also like

Java Collections Framework Tutorial

Java Collections framework is an important API in Java programming language. In any Java application if you have to store objects you will certainly use one of the data structure defined in the Java collections. This Java collections tutorial gives an overview of Java collections framework; interfaces and classes that constitute the collections framework and the Java collections hierarchy.

What is Java Collections framework

A collection can be defined as a container that can store multiple elements into a single container. Collections framework in Java provides a unified architecture for defining such container classes that can store, retrieve and manipulate group of elements.

Java Collections framework contains the following-

  1. Interfaces- Interfaces in the Java collections are the abstract data types that represent collections. These interfaces provide the generalized structure for the collection which are then implemented to provide specialized implementations. For example java.util.Collection is the root interface in the collection hierarchy defining methods for the collections and the implementations of this interface like ArrayList or HashSet provide the specialized data structures.
  2. Implementations- Implementation classes are the concrete implementations of the collection interfaces. These are the reusable data structures which you can use as per your need. For example, if you want to store elements that can be accessed using an index then you can use ArrayList, if you want to ensure that only unique elements are stored then you can use HashSet.
  3. Algorithms- These are the methods that perform useful computations on the collection classes. These methods are designed in such a way that same method can be used on different collection classes. So, these algorithms provide some common functionalities that are applicable to all the collections like searching, sorting, comparing elements. Algorithms are defined as static methods in java.util.Collections class.

Interfaces in Java Collections

With in the Java Collections framework there are several core interfaces that are the foundation of the Java Collections Framework. These interfaces are designed in an evolving style, starting from more generalized to specialized interfaces. The following list describes the core collection interfaces-

  1. Collection interface- This interface is the root of the collection hierarchy which is implemented by all the collections. Though it is not directly implemented by any class, Collection interface is extended by more specific sub-interfaces like List and Set which in turn are implemented by classes.
  2. List interface- Extends Collection interface and provide behavior for an ordered collection (in which elements are stored in sequence) which can contain duplicate elements. Apart from inheriting methods of Collection interface, the List interface includes operations so that elements can be accessed using index (get, set, add, remove methods), elements can be searched returning their index (indexOf, lastIndexOf methods).
  3. Set interface- Extends Collection interface and provides behavior for a collection that cannot contain duplicate elements.
  4. Queue interface- Extends Collection interface and provides behavior for a collection where head of the queue is the element removed by a call to remove or poll.
  5. SortedSet interface- Extends Set interface and provides behavior for a sorted set. The elements in the Set are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time.
  6. NavigableSet interface- Extends SortedSet and adds navigation methods reporting closest matches for given search targets. Methods lower, floor, ceiling, and higher return elements respectively less than, less than or equal, greater than or equal, and greater than a given element, returning null if there is no such element.
  7. Deque interface- Extends Queue and provides support for element insertion and removal at both ends.

Map interfaces

  1. Map interface- Map interface provides behavior for a collection that store (key, value) pair. Note that though Map is part of Java Collections framework but it doesn’t extend the Collection interface. You can’t directly iterate a Map too, in order to iterate a Map you will have to get a Collection view of a Map and then iterate it.
  2. SortedMap interface- Extends Map interface and provides behavior for a map sorted on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time.
  3. NavigableMap interface- Extends SortedMap and adds navigation methods reporting closest matches for given search targets. Methods lowerEntry, floorEntry, ceilingEntry, and higherEntry return Map.Entry objects associated with keys respectively less than, less than or equal, greater than or equal, and greater than a given key, returning null if there is no such key.

Interfaces for iterating a collection

  1. Iterable interface- Implementing java.lang.Iterable interface allows an object to be the target of the "for-each loop" statement. Collection interface extends this interface so that collection classes can be iterated using for-each loop.
  2. Iterator interface- java.util.Iterator enables you to traverse a collection. It also allows the caller to remove elements from the underlying collection during the iteration.
  3. ListIterator interface- Extends Iterator and provides specialized behavior to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.

Java Collections classes

We have already gone through the core interface of the Java Collections framework now let’s go through the classes that implements these interfaces. Again classes evolve from general to more specific, so there are abstract classes that implement the interfaces to provide general implementation then there are more specific classes for specific collections.

  1. AbstractCollection- This abstract class provides a skeletal implementation of the Collection interface, to minimize the effort required to implement this interface.
  2. AbstractList- This abstract class extends AbstractCollection and implements List interface in order to minimize the effort required to implement this interface.
  3. AbstractSet - This abstract class extends AbstractCollection and implements Set interface in order to minimize the effort required to implement this interface.
  4. AbstractQueue- This abstract class extends AbstractCollection and implements Queue interface to provide skeletal implementations of some Queue operations.
  5. AbstractSequentialList- Extends AbstractList to provide implementation for collection that uses sequential access (like linked list) rather than random access (like array list) of its elements.
  6. ArrayList- Java ArrayList extends AbstractList and provides resizable-array implementation of the List interface. Refer ArrayList in Java to know more about Arraylist in Java.
  7. LinkedList- Extends AbstractSequentialList and provides doubly-linked list implementation of the List and Deque interfaces.
  8. HashSet- Extends AbstractSet and provides implementation for an unordered collection that doesn't allow duplicates. Refer HashSet in Java to know more about HashSet in Java.
  9. LinkedHashSet- Extends HashSet and provides specialized implementation for a Set that maintains the iteration ordering, which is the order in which elements were inserted into the set. Refer LinkedHashSet in Java to know more about LinkedHashSet in Java.
  10. TreeSet- Extends AbstractSet and implements NavigableSet interface to provide an ordered Set. Refer TreeSet in Java to know more about TreeSet in Java.
  11. EnumSet- Extends AbstractSet and provides specialized Set implementation for use with enum types.
  12. ArrayDeque- Extends AbstractCollection and implements Deque interface to provide a Resizable-array implementation of the Deque interface. In ArrayDeque you can add and remove elements at both end points.

Map Related classes

  1. AbstractMap- This abstract class provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface.
  2. HashMap- Extends AbstractMap and provides Hash table based implementation of the Map interface. Refer HashMap in Java to know more about HashMap in Java.
  3. LinkedHashMap - Extends HashMap and provides specialized implementation for a Map that maintains the iteration ordering, which is normally the order in which keys were inserted into the map.  Refer LinkedHashMap in Java to know more about LinkedHashMap in Java.
  4. TreeMap - Extends AbstractMap and implements NavigableMap to provide an ordered Map. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. Refer TreeMap in Java to know more about TreeMap in Java.
  5. IdentityHashMap- Extends AbstractMap and provides implementation where reference-equality is used in place of object-equality when comparing keys and values. In an IdentityHashMap, two keys k1 and k2 are considered equal if and only if (k1==k2) where as in normal Map implementations two keys k1 and k2 are considered equal if and only if (k1==null ? k2==null : k1.equals(k2)).
  6. EnumMap- Extends AbstractMap and provides specialized Map implementation for use with enum type keys.
  7. WeakHashMap- Extends AbstractMap and provides Hash table based implementation of the Map interface, with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use.

Java Collection Hierarchy

Here is a diagram depicting Java Collections framework hierarchy.
Java Collections framework

That's all for the topic Java Collections Framework Tutorial. If something is missing or you have something to share about the topic please write a comment.


You may also like

Java ListIterator With Examples

In Java there is an Iterator interface which provides an iterator over a collection (List, Set etc.) but there is another interface ListIterator in Java which provides an iterator exclusively for lists like ArrayList, LinkedList, CopyOnWriteArrayList.

While iterator can only move forward, ListIterator provides functionality to traverse the List in either direction; forward or backward, which is one of the difference between Iterator and ListIterator in Java. Other differences are as follows.

  1. Both of these interfaces have remove() method to safely remove an element from List after the iterator is created but ListIterator has an add() method too.
  2. ListIterator also has a set() method to change the element while iterating a List.

No current element in ListIterator

A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). Following image shows the possible cursor positions for a list of length n.

ListIterator in Java

Java ListIterator methods

ListIterator interface in Java provides the following methods-

  1. add(E e)- Inserts the specified element into the list.
  2. hasNext()- Returns true if this list iterator has more elements when traversing the list in the forward direction.
  3. hasPrevious()- Returns true if this list iterator has more elements when traversing the list in the reverse direction.
  4. next()- Returns the next element in the list and advances the cursor position.
  5. nextIndex()- Returns the index of the element that would be returned by a subsequent call to next().
  6. previous()- Returns the previous element in the list and moves the cursor position backwards.
  7. previousIndex()- Returns the index of the element that would be returned by a subsequent call to previous().
  8. remove()- Removes from the list the last element that was returned by next() or previous().
  9. set(E e)- Replaces the last element returned by next() or previous() with the specified element.

Java ListIterator example with bi-directional traversal

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class ListIterationDemo {
  public static void main(String[] args) {
    List<String> carList = new LinkedList<String>();
    carList.add("Audi");
    carList.add("Jaguar");
    carList.add("BMW");
    carList.add("Mini Cooper");
    //Getting ListIterator
    ListIterator<String> ltr = carList.listIterator();
    //forward iteration
    System.out.println("List iteration - forward direction");
    while(ltr.hasNext()){
        System.out.println(ltr.next());
    }
    // backward iteration 
    System.out.println("List iteration - backward direction");
    while(ltr.hasPrevious()){
        System.out.println(ltr.previous());
    }
  }
}
Output
List iteration - forward direction
Audi
Jaguar
BMW
Mini Cooper
List iteration - backward direction
Mini Cooper
BMW
Jaguar
Audi

Example using add() and set() method of ListIterator

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class ListIterationDemo { 
  public static void main(String[] args) {
    List<String> carList = new LinkedList<String>();
    carList.add("Audi");
    carList.add("Jaguar");
    carList.add("BMW");
    carList.add("Mini Cooper");
    //Getting ListIterator
    ListIterator<String> ltr = carList.listIterator(); 
    while(ltr.hasNext()){
      String car = ltr.next();
      
      if(car.equals("BMW")) {
          ltr.add("Mercedes");
      }
      if(car.equals("Mini Cooper")) {
          ltr.set("Camry");
      }
    }
    System.out.println("List elements- " + carList);
  }
}
output
List elements- [Audi, Jaguar, BMW, Mercedes, Camry]

That's all for the topic Java ListIterator With Examples. If something is missing or you have something to share about the topic please write a comment.


You may also like