Java: Does it make sense to create LinkedList and convert it to an ArrayList for sorting?

Question

The title says it all. I have to add several thousand objects to a List and then sort them. For now I thought (since adding something to a LinkedList is considerably faster) I'd use a LinkedList for creation and then make a new ArrayList like so:

LinkedList<Foo> createList = new LinkedList<Foo>();
// add stuff
ArrayList<Foo> returnList = new ArrayList<Foo>(createList);
Collections.sort(returnList);
return returnList;

My question is: Is this method really faster or even slower than just adding the objects directly to an ArrayList? Or, I know the rough number of objects to add. Is an ArrayList with initial capacity faster?

Answer 1

tl;dr

You asked:

Does it make sense to create LinkedList and convert it to an ArrayList for sorting?

No, that conversion does not make sense. Not from what we see in the empirical benchmarking test shown below.

➥ Both ArrayList and LinkedList take about the same amount of time to sort a list of 100,000 random hex strings.

Beware of premature optimization

Never intuit performance problems. Programmers of every skill/experience level are notoriously bad at spotting bottlenecks in their code base. This is especially true with the highly-tuned Java compilers and Java Virtual Machine implementations. Worrying about performance without actual evidence is known as the trap of premature optimization.

No difference: Sorting 100,000 element ArrayList or LinkedList takes around 0.05 seconds

Doing a quick-and-dirty benchmark test shows that indeed you should not be spending time focused on performance of sorting performance of ArrayList versus LinkedList. Assuming my benchmark code is valid, the performance of either list is nearly the same. I also tried two implementations of SortedSet, TreeSet and ConcurrentSkipListSet, since you said your collection of objects is distinct (no duplicate objects). Each of the four collections take at most a tenth of a second to populate and sort 100,000 random String elements.

The results are around half of a tenth of a second for the combination of populating and sorting a collection of over 100,000. Since your work involves only 10,000, we are talking about a tiny fraction of a second. Unless you are doing thousands/millions of these operations per second, this populating & sorting of a list has no significant impact on your app.

durationArrayList = PT0.038510117S

durationLinkedList = PT0.045435537S

durationTreeSet = PT0.067535504S

durationConcurrentSkipListSet = PT0.104006783S

Here is another run.

durationArrayList = PT0.031999744S

durationLinkedList = PT0.037321294S

durationTreeSet = PT0.065598175S

durationConcurrentSkipListSet = PT0.084586606S

Those results come from running inside IntelliJ 2020.2, compiled via Maven for Java 14, using AdoptOpenJDK (build 14.0.1+7), on a Mac mini (2018) with 3 GHz Intel Core i5 CPU without Hyper-Threading, 32 GB 2667 MHz DDR4, macOS Mojave 10.14.6.

Notice that the ConcurrentSkipListSet takes the longest time. That class is designed for concurrent (thread-safe) use. So the longer execution time is justified, if you need concurrent protection of your collection. Otherwise, if not accessing the collection across threads, use one of the other three collection types instead.

Here is the benchmark code. Please review carefully, as I threw this together quickly, and with all the cutting-and-pasting, I may well have made a mistake.

The testing code call this timeout method to sleep several seconds, in an attempt to let the garbage collection run (assuming the JVM respected by request to run gc cycle).

private void timeout ( )
{
    try
    {
        Thread.sleep( TimeUnit.SECONDS.toMillis( 5 ) );
    }
    catch ( InterruptedException e )
    {
        e.printStackTrace();
    }
}

Here is the testing code.

We start with a list of 100,000 strings, each the hexadecimal representation of a Version 4 UUID, where 122 of the 128 bits are randomly generated. Example value: 0063a1f3-39d0-421b-80ab-70e4e1726904.

System.out.println( "INFO - Beginning the speed tests for sorting ArrayList, LinkedList, TreeSet, and ConcurrentSkipListSet." );

System.gc();
this.timeout();

// --------|  setup  | ---------------------
final int LIMIT = 100_000;
List < String > tempList = new ArrayList <>();
for ( int i = 0 ; i < LIMIT ; i++ )
{
    tempList.add( UUID.randomUUID().toString() );
}
final List < String > sourceList = List.copyOf( tempList );  // List.copyOf makes an unmodifiable list.
tempList = null ;

{
    // Warmup
    final List < String > warmUpArrayList = new ArrayList <>( sourceList );
    Collections.sort( warmUpArrayList );
    final List < String > warmUpLinkedList = new LinkedList <>( sourceList );
    Collections.sort( warmUpLinkedList );
    final SortedSet < String > warmUpSortedSet = new TreeSet <>( sourceList );
    final SortedSet < String > warmUpConcurrentSkipListSet = new ConcurrentSkipListSet <>( sourceList );
}

// Pause
System.gc();
this.timeout();

long start, stop;

// --------|  ArrayList  | ---------------------
start = System.nanoTime();

List < String > arrayList = new ArrayList <>();
arrayList.addAll( sourceList );
Collections.sort( arrayList );

stop = System.nanoTime();
Duration durationArrayList = Duration.ofNanos( stop - start );

arrayList = null;
// Pause
System.gc();
this.timeout();

// --------|  LinkedList  | ---------------------
start = System.nanoTime();

List < String > linkedList = new LinkedList <>();
linkedList.addAll( sourceList );
Collections.sort( linkedList );

stop = System.nanoTime();
Duration durationLinkedList = Duration.ofNanos( stop - start );

linkedList = null;
// Pause
System.gc();
this.timeout();


// --------|  TreeSet  | ---------------------
start = System.nanoTime();

TreeSet < String > treeSet = new TreeSet <>();  // Implements `SorteSet`.
treeSet.addAll( sourceList );

stop = System.nanoTime();
Duration durationTreeSet = Duration.ofNanos( stop - start );

treeSet = null;
// Pause
System.gc();
this.timeout();


// --------|  ConcurrentSkipListSet  | ---------------------
start = System.nanoTime();

ConcurrentSkipListSet < String > concurrentSkipListSet = new ConcurrentSkipListSet <>();  // Implements `SorteSet`.
concurrentSkipListSet.addAll( sourceList );

stop = System.nanoTime();
Duration durationConcurrentSkipListSet = Duration.ofNanos( stop - start );

concurrentSkipListSet = null;
// Pause
System.gc();
this.timeout();


// --------|  reporting  | ---------------------

System.out.println( "durationArrayList = " + durationArrayList );
System.out.println( "durationLinkedList = " + durationLinkedList );
System.out.println( "durationTreeSet = " + durationTreeSet );
System.out.println( "durationConcurrentSkipListSet = " + durationConcurrentSkipListSet );

Answer 2

Forget LinkedList. It's much slower except when you need things like .add(0, item) or remove(0) where the ArrayList has quadratic complexity. As long as all you need is .add(item) and sort, the ArrayList wins hands down.

See also this answer of mine.

---

Note also that the copying into the ArrayList is questionable as Collections.sort used to copy it itself to an array. Since Java 8, the internal array of the ArrayList gets sorted directly.

Answer 3

This is related to two questions:
1. What's the difference between ArrayList and LinkedList, which one is faster for insertion?
2. Which one is faster in sorting?

For question 1, the essential difference between ArrayList and LinkedList is the data structure. ArrayList uses an array inside and good at random access(O(1)). On the other hand, LinkedList in good at delete and insert items(O(1). You can find more here
Back to the question, because we don't need to insert by index here. So ArrayList and LinkedList both O(1) operation. But LinkedList will cause more memory because of the data structure, and ArrayList will cause more time if it needs to scale capacity(set a large enough initial capacity will help speed up the insertion).

For question 2, you can find the answer here ArrayList is better for sorting.

In conclusion, I think you should stick with ArrayList, no need to import LinkedList here.