How to Sort Linked List in Java

A Linked List in Java is a data structure or a collection that allows users to create a dynamic array in the memory. The list does not hold any pre-defined size. It creates nodes dynamically and stores value and reference to the next node in a single memory address. The list elements keep the values in the sequential order, or the list maintains the insertion order in which the elements get inserted.

Sorting is defined as the method of arranging the elements in a data structure in a definite order. The arrangement can either be in ascending or descending order, depending on the requirement. Note that there can be various approaches to sort the list collection.

Below is the code block to sort the elements in the array.

import java.text.Collator;
import java.util.Comparator;
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("ab");
    list.add("bb");
    list.add("aA");
    list.add("bB");
    System.out.println(list);
    list.sort(new Comparator<String>() {
      @Override
      public int compare(String s1, String s2) {
        return Collator.getInstance().compare(s1, s2);
      }
    });
    System.out.println(list);
  }
}

In the code block above, a list gets instantiated using the new keyword. The keyword instantiates the linked list of String datatypes and calls the constructor internally. Then, the list instance calls the add method to fill in the elements in the list. The value gets printed to check the insertion order.

The sort method is present in the List interface. The function sorts the list based on some comparator given as a parameter. The comparator gets used to compare the list of elements passed.

The point that you should consider is to sort the values passed and ensure that they must be of the same type. If the values are not of the same type or when the elements are non-comparable, the class throws ClassCastException.

The internal implementation of the sort gets done using the merge sort command that is efficient enough and makes the comparison in the log n time. So a new Comparator instance gets formed that overrides the compare method. The implementation is a traditional way of method-overriding and providing the implementation.

Instead, a one-liner implementation using the Java 8 lambda functions can get used. The interface is a Functional Interface and has a single method to call. The lambda directly takes the number of parameters present in the interface. The one-liner Java 8 representation of the code above is shown below.

list.sort((o1, o2) -> Collator.getInstance().compare(o1, o2));

The actual statement for comparing the elements in the list is the collator class. This class is abstract in nature and defines the prototypes of the methods. The implementation is present in the abstract class that extends them.

The collator class compares the locale-sensitive string. The getInstance method gets the instance with the current default Locale value. The compare function compares the values based on the Collator and returns +1,-1 or 0, based on the values which are greater-to, lesser than, or equals.

The output of the code above is shown below. The second line represents the output in an arranged form. As per the ASCII sequence of the characters on the keyboard, capital letters fall in the higher range(A-Z) than the small alphabets (a-z). So the resultant list in the second line prints the small case bb first and then prints bB as it has a capital case alphabets.

[ab, bb, aA, bB][aA, ab, bb, bB]