How to sort a LinkedList in Java? Example Tutorial

Since LinkedList implements the java.util.List interface, you can sort the LinkedList by using the Collections.sort() method, just like you sort an ArrayList. Since the LinkedList class implements the linked list data structure which doesn't provide random access based upon the index, sorting is quite expensive. In order to access any element, you need to first traverse through that element which is the O(n) operator. This method uses an efficient strategy to handle this scenario. It first copies the contents of LinkedList to an array, sorts the array, and copies it back. 

So it's as efficient as sorting an ArrayList. By default Collections.sort() arrange elements of a linked list into their natural order of sorting but it also accepts a Comparator, which can be used to sort elements in the custom order. 

Java 8 also introduced a new sort() method on the java.util.List interface itself, which means you no longer need Collections.sort() to sort a LinkedList, you can do directly by calling the LinkedList.sort() method in Java 8. 

Java Development Kit comes with Java API, which has sample implementation for many common data structures e.g. array, hash table, red-black tree, etc. The LinkedList class is an implementation of a doubly-linked list, which allows traversal in both directions like from head to tail and vice-versa. 

For a detailed description of red-black trees, see a good data structure and algorithm book like Introduction to Algorithms By Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein.

Sorting LinkedList using Collections.sort() in Java

There are 2 ways to sort the LinkedList using Collection.sort() method, first, in the natural order which is imposed by the Comparable interface i.e. String are sorted in lexicographic order, Integers are sorted in numeric order and Dates are sorted in chronological order. 

On the second way, You can use pass your own Comparator to define the sorting strategy e.g. you can sort the LinkedList of String on their length as we have done in the second example in our program. This method of sorting is available in Java since Java 1.2, hence, you can use it most of the JDK.

Sorting LinkedList with Collecitons.sort() method in natural order
Collections.sort(singlyLinkedList);

Sorting LinkedList using Collection.sort() and Comparator in Java
Collections.sort(singlyLinkedList, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
  return s1.length() - s2.length();
} 

} );

You can see that I have used an Anonymous class to implement the Comparator interface, from Java 8 onwards you can use the lambda expression to implement any SAM class or interface e.g. Runnable, EventListener or Comparator as shown here. 

Using lambda expression reduces the clutter generated via boilerplate code and makes the code more readable. See Java SE 8 for Really Impatient to learn more about lambda expression in Java 8. 

Java Program  for Sorting LinkedList using List.sort() in Java 8

This is a relatively new way to sort LinkedList in Java. It is only available from Java 8 onward. Instead of calling Collections.sort(), you just call the list.sort() method. It behaves similarly to Collections.sort(), actually internally it just calls the Collection.sort() method as shown below:

default void sort(Comparator<? super E> c) {
        Collections.sort(this, c);
}

Though it always needs a custom Comparator for sorting. Anyway, here is an example of sorting a List in Java 8 in reverse order. In this example, we have a LinkedList of some food which helps in losing weight and we sort them into reverse order by using Comparator.reverseOrder(), which returns a Comparator instance for sorting in reverse of the natural order.

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * Java Program to show how to sort a list in Java 8.
 *
 * @author WINDOWS 8
 */
public class Java8Demo {

    public static void main(String args[]) {

        // foods which helps in weight loss
        List<String> listOfWeightLossFood = new LinkedList<>(
                Arrays.asList("beans", "oats", "avocados", "broccoli"));

        System.out.println("before sorting: " + listOfWeightLossFood);
        listOfWeightLossFood.sort(Comparator.reverseOrder());
        System.out.println("after sorting: " + listOfWeightLossFood);

    }

}

Output
before sorting: [beans, oats, avocados, broccoli]
after sorting: [oats, broccoli, beans, avocados]

You can see that the list is sorted in reverse order.  Btw, you can also write your own method to sort a LinkedList in Java using any sorting algorithms like QuickSort or Insertion Sort.

Java Program to sort the LinkedList in Java

Here is a complete Java program to sort the LinkedList. We have used the Collections.sort() method for sorting elements stored in the LinkedList class. You can also see Java SE 8 for Really Impatient to learn more about new features of Java 8. In this article, I'll show you a couple of examples of sorting LinkedList in Java.

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class LinkedListSorting{

public static void main(String args[]) {

// Creating and initializing an LinkedList for sorting
LinkedList<String> singlyLinkedList = new LinkedList<>();
singlyLinkedList.add("Eclipse");
singlyLinkedList.add("NetBeans");
singlyLinkedList.add("IntelliJ");
singlyLinkedList.add("Resharper");
singlyLinkedList.add("Visual Studio");
singlyLinkedList.add("notepad");

System.out.println("LinkedList (before sorting): " 
 + singlyLinkedList);

// Example 1 - Sorting LinkedList with Collecitons.sort() method 
// in natural order
Collections.sort(singlyLinkedList);

System.out.println("LinkedList (after sorting in natural): " 
 + singlyLinkedList);

// Example 2 - Sorting LinkedList using Collection.sort() and Comparator in Java
Collections.sort(singlyLinkedList, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
} } );

System.out.println("LinkedList (after sorting using Comparator): " 
   + singlyLinkedList);
}
}

Output
LinkedList (before sorting): [Eclipse, NetBeans, IntelliJ, 
Resharper, Visual Studio, notepad]
LinkedList (after sorting in natural): [Eclipse, IntelliJ,
NetBeans, Resharper, Visual Studio, notepad]
LinkedList (after sorting using Comparator): [Eclipse, notepad, 
IntelliJ, NetBeans, Resharper, Visual Studio]

That's all about how to sort a LinkedList in Java. Sorting a LinkedList is very inefficient because you need to traverse through elements, which is the O(n) operation. There is no indexed access like an array, but using the Collections.sort() method is as good as sorting ArrayList because it copies LinkedList elements into an array, sorts it, and then puts it back into a linked list.