- LinkedList implements the java.util.List interface, so you can sort the LinkedList by using Collections.sort() method.
- Since 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 O(n).
How Collections.sort() does sorting to avoid O(n) complexity?
- Collections.sort() 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.
About Collections.sort() ‘s natural sorting/custom sorting ?
- By default Collections.sort() arrange elements of linked list into their natural order of sorting
- But it also accepts a Comparator, which can be used to sort elements in 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