LinkedList

  • 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