LinkedList Sort Overview
LinkedList is part of the Java collection framework. It is implemented as a bidirectional linked list and has the characteristics of a dynamic data structure. Due to its linked list nature, LinkedList is more efficient than ArrayList when inserting and deleting elements. But in terms of sorting, LinkedList's performance is usually not as good as ArrayList, because LinkedList stores data based on a linked list structure. It cannot directly access elements through indexes like ArrayList, but requires sequential traversal.
However, Java 8 introduces some new methods that simplify sorting of LinkedList elements. In particular, the () method and the Stream API provide stronger support for sorting and can effectively improve the readability and performance of the code.
Use the () method to sort LinkedList
Default sort (natural order)
The () method in Java is a very concise sorting method, which can directly sort elements in LinkedList. The () method sorts elements in natural order, that is, in ascending order, provided that these elements implement the Comparable interface.
Example: Sort ascending order for LinkedList of Integer type
import ;
import ;
public class DefaultSortExample {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
(5);
(2);
(8);
(1);
(3);
// Use () for default sorting (natural order) (null); // null means the natural order of using elements
("Sorted list in natural order: " + list);
}
}
Output:
List sorted in natural order: [1, 2, 3, 5, 8]
In this example,IntegerImplementedComparableInterface, so it can be used directly(null)Sort in natural order. PassnullGivesort()Methods mean using the order defined by the elements themselves.
Use custom Comparator to sort
If we need to follow custom rulesLinkedListSort, you can pass oneComparatorGive()method.ComparatorThe interface allows us to define sorting rules, such as sorting in descending order, sorting by custom attributes, etc.
Example: Sort LinkedList in descending order
import ;
import ;
import ;
public class CustomSortExample {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
(5);
(2);
(8);
(1);
(3);
// Sort descending with () and custom Comparator (());
("Sorted list in descending order: " + list);
}
}
Output:
List sorted in descending order: [8, 5, 3, 2, 1]
In this example, we use()Create a comparator in descending order and pass it to()Method to implement descending sorting.
Sort by string
ifLinkedListThe element in it isStringType, we can also use()Methods are sorted alphabetically.
Example: Sort strings alphabetically
import ;
import ;
public class StringSortExample {
public static void main(String[] args) {
List<String> list = new LinkedList<>();
("Banana");
("Apple");
("Orange");
("Grapes");
// Sort the strings in ascending order using () (null); // null means sorting in natural order
("List of strings sorted alphabetical: " + list);
}
}
Output:
List of strings sorted alphabetically: [Apple, Banana, Grapes, Orange]
In this example,StringType has been implementedComparableInterface, so it can be used directly(null)Sort alphabetically.
Use the Stream API to sort LinkedList
Java 8'sStreamThe API provides a more flexible and functional way to handle collection operations, including sorting. passStreamAPI, we can match it in a more declarative wayLinkedListSort.
Sort in ascending order using Stream
Example: Sort in ascending order using Stream
import ;
import ;
import ;
public class StreamSortExample {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
(5);
(2);
(8);
(1);
(3);
// Sort in ascending order using Stream API List<Integer> sortedList = ()
.sorted()
.collect(());
("Sorted list in ascending order: " + sortedList);
}
}
Output:
List sorted in ascending order: [1, 2, 3, 5, 8]
In this example, first use () to convert the LinkedList to a stream, then use the sorted() method to sort in ascending order, and finally use collect(()) to collect the sorted results back into a new List.
Sort in descending order using Stream
Example: Sort in descending order using Stream
import ;
import ;
import ;
import ;
public class StreamReverseSortExample {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
(5);
(2);
(8);
(1);
(3);
// Sort in descending order using Stream API List<Integer> sortedList = ()
.sorted(())
.collect(());
("Sorted list in descending order: " + sortedList);
}
}
Output:
List sorted in descending order: [8, 5, 3, 2, 1]
In this example, we use () to implement descending sorting.
Use Stream to sort custom objects
The Stream API can also be used to sort custom objects. If we need to sort objects in a LinkedList by a certain property, we can use it through a combination of Comparator and Stream.
Example: Sort Person objects in ascending order in age
import ;
import ;
import ;
import ;
class Person {
String name;
int age;
Person(String name, int age) {
= name;
= age;
}
@Override
public String toString() {
return name + " (" + age + ")";
}
public int getAge() {
return age;
}
}
public class StreamSortPersonExample {
public static void main(String[] args) {
List<Person> list = new LinkedList<>();
(new Person("Alice", 30));
(new Person("Bob", 25));
(new Person("Charlie", 35));
// Sort by ascending age using Stream API List<Person> sortedList = ()
.sorted((Person::getAge))
.collect(());
("People list sorted by ascending order of age: " + sortedList);
}
}
Output:
List of people sorted by ascending age: [Bob (25), Alice (30), Charlie (35)]
In this example, use(Person::getAge)rightPersonThe object'sageThe attributes are sorted in ascending order and passedStreamThe API performs streaming operations and finally obtains a list of people arranged in ascending order of age.
Performance considerations for sorting
AlthoughLinkedListProvides convenient linked list operations, but in terms of sorting performance, it is not likeArrayListThat has superior performance. The sorting operation will essentially traverseLinkedList, so its time complexity is usually high, especially for large-scale datasets. existLinkedListWhen sorting in Java needs to traverse nodes in the linked list multiple times, which may lead to performance bottlenecks.
Memory consumption
andArrayListdifferent,LinkedListReferences to the front and back elements are maintained in memory for each element, which makesLinkedListComparison of memory consumptionArrayListBiger. When sorting, Java needs to create temporary space for sorting operations to store sorted elements, which can result in higher memory consumption.
Performance optimization
If frequent sorting operations on large amounts of data are required, or sorting operations are the main source of performance bottlenecks, it is recommended to consider the following optimization strategies:
-
use
ArrayListReplacementLinkedList: For situations where frequent sorting is required, useArrayListIt can avoid performance losses caused by linked list structure, especially in sorting operations.ArrayListElements can be accessed directly through indexes, providing faster sorting performance. -
Custom sorting algorithm: In some cases, custom sorting algorithms may be required to optimize specific data structures or sorting requirements. For example, for the sorting of linked list elements, consider
LinkedListConvert toArrayList, sort it and then convert it back to the linked list.
The above is a detailed explanation of the method of sorting LinkedList elements in Java 8. For more information about sorting Java 8 LinkedList, please pay attention to my other related articles!