How to Sort a Linked List in Java

A linked list is one of the primary types of data structures in the programming world. It's an arrangement of nodes which contains both data and references pointing to the next node. To sort a linked list in Java, there's a linked list class that works with the Collections framework that implements algorithms like sorting.

Difficulty: Moderate

Instructions

Sort a Linked List in Java

1. Declare the linked list by creating a new LinkedList object and assigning it to a LinkedList variable. LinkedList inherits from the generic List class, so any method that accepts a List will also accept a LinkedList object.
   ""LinkedList l = new LinkedList();""

2. Add objects of the same type (such as integers) to the list. These can be objects of any type, but in order to sort a linked list, they should be of all the same type.

3. Use the List.addFirst method to insert new objects to the beginning of the list, so that whatever objects you add will be in the reverse order. If you want to add them to the end of the list, use List.addLast method.""list.addFirst(1);
list.addFirst(3);
list.addFirst(2);""
   

4. Use an Iterator to iterate over the list, and print them before and afterward to see what the sort method is doing. ""for( Iterator i = list.iterator(); i.hasNext(); ) {
System.out.println(i.next());
}""

Sort Using Default and Custom Comparators

5. Sort the list with the default comparator. A comparator is an object that compares two objects. The default comparator object uses the less than operator, so the list will be sorted in ascending order. To sort the list, use the Collections.sort static method.""Collections.sort(list);""

6. Sort the list with a custom comparator by writing a class that implements the comparator interface and passes to it an instance as an argument to sort. The class that implements comparator only has to implement the single method "compare." ""public class GreaterThan implements Comparator {@Override
public int compare(Object arg0, Object arg1) {
int x = (Integer)arg0;
int y = (Integer)arg1;
if(x > y) {
return -1;
} else if(x == y) {
return 0;
} else {
return 1;
}
}}""

7. Use the call to Collections.sort by passing a new instance to GreaterThan as a second argument. Since objects that are greater will be sorted first, the list will be sorted into descending order instead of ascending order. As an alternative, if you're sorting a list of objects of a custom class you've written yourself, that class can implement the Comparable interface instead of using a separate Comparator class.""Collections.sort(list, new GreaterThan());""

Tips & Warnings

• It's problematic to use an an integer to iterate for loop and the List.size() method. Iterating over a linked list is a computationally expensive operation. When using the index operator (like l[2]) as you would with an array, Java has to iterate over the list until it gets to index 2. For small lists, this isn't a problem, but with anything larger, using the index operator to iterate becomes very resource-expensive.
• It doesn't matter how the List object is implemented, since LinkedList implements the same interface.
• The compare method should return -1 if arg0 should be sorted before arg1, 0 if it should be sorted equally and 1 if arg1 should be sorted before arg0.
• The iterator object ensures that each node in the list is visited only once. This is an important thing to remember, as visiting nodes unnecessarily can abuse data structures to the point that your program will barely run.