-1

I would think that inserting into a LinkedList should be faster than inserting into an ArrayList because inserting into a LinkedList just requires copying references whereas inserting into an ArrayList requires creating a bunch of new arrays in addition to copying references. But I created Java code to test this and I found the opposite, that inserting into an ArrayList is faster than inserting into a LinkedList.

import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class ListPerformanceTester {
    public static void main(String[] args) {
        System.out.println("Time to perform ten million insertions using LinkedList: " +
                timeToPerformTenMillionInsertionsUsing(new LinkedList<>()));
        System.out.println("Time to perform ten million insertions using ArrayList: " +
                timeToPerformTenMillionInsertionsUsing(new ArrayList<>()));
    }

    private static long timeToPerformTenMillionInsertionsUsing(List<String> list) {
        Instant start = Instant.now();
        for (int i = 0; i < 10000000; ++i) {
            list.add("");
        }
        return Duration.between(start, Instant.now()).toMillis();
    }
}

Results from running three times:

Time to perform ten million insertions using ArrayList: 135
Time to perform ten million insertions using LinkedList: 1321

Time to perform ten million insertions using ArrayList: 126
Time to perform ten million insertions using LinkedList: 1094

Time to perform ten million insertions using ArrayList: 125
Time to perform ten million insertions using LinkedList: 1086

I even tried reversing the order of the inserts just in case that had an effect and LinkedList still took longer:

Time to perform ten million insertions using LinkedList: 2642
Time to perform ten million insertions using ArrayList: 402

Why is inserting into an ArrayList faster than inserting into a LinkedList?

$ java -version
java version "1.8.0_171"
Java(TM) SE Runtime Environment (build 1.8.0_171-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.171-b11, mixed mode)
Ezra-Shimon
  • 35
  • 2
  • 7
  • 3
    btw, Ezra-Shimon: The answer is, because ArrayList does *not* reallocate the backing array on every insert. It tracks the number of items actually in the list, but the array is pre-allocated to some size and, only when that size is exceeded, a realloc occurs that again provides additional space (beyond what's needed "now") which is used for the next `N` inserts. By contrast, LinkedList must actually allocate and link a new container node for each insert. – Mark Adelsberger Dec 07 '18 at 17:16

1 Answers1

-1

...but...it is faster. Linked list insertion time at either the front or back is constant time. Array list insertion is amortized constant time, with the caveat that if it reaches a certain capacity, it will double the size of its internal array and copy over all of the previous values it had to keep track of, which is O(k), where k is the size of the current list.

Additionally, let's talk about the obvious flaw in your testing methodology - you don't warm up just-in-time optimizer before actually running it. Those numbers look like they're running cold benchmarks, and JIT optimization can do strange and phenomenal things with your code.

With that, if we warm up the code by running it through say, 100 times, and then politely ask Java to garbage collect after each test run (and know that it may say "no"), we can get a slightly better picture.

class ListPerformanceTester {
    public static void main(String[] args) {
        System.out.println("Warming up by running 100 times...");
        for(int i = 0; i < 100; i++) {
            // warm up
            timeToPerformTenMillionInsertionsUsing(new LinkedList<>());
            timeToPerformTenMillionInsertionsUsing(new ArrayList<>());
        }

        System.out.println("Starting test.");
        for(int i = 0; i < 10; i++) {
            System.out.println("Time to perform ten million insertions using LinkedList: " +
                                       timeToPerformTenMillionInsertionsUsing(new LinkedList<>()));
            System.out.println("Time to perform ten million insertions using ArrayList: " +
                                       timeToPerformTenMillionInsertionsUsing(new ArrayList<>()));
            System.out.println();

            System.gc();
        }

    }

    private static long timeToPerformTenMillionInsertionsUsing(List<String> list) {
        Instant start = Instant.now();
        for (int i = 0; i < 10000000; ++i) {
            list.add("");
        }
        return Duration.between(start, Instant.now()).toMillis();
    }
}

Here's ten results from my machine (which is a Intel Core i7-7820HQ):

Warming up by running 100 times...
Starting test.
Time to perform ten million insertions using LinkedList: 40
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 41
Time to perform ten million insertions using ArrayList: 46

Time to perform ten million insertions using LinkedList: 41
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 44

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 44

Time to perform ten million insertions using LinkedList: 41
Time to perform ten million insertions using ArrayList: 45

Time to perform ten million insertions using LinkedList: 38
Time to perform ten million insertions using ArrayList: 44

Time to perform ten million insertions using LinkedList: 39
Time to perform ten million insertions using ArrayList: 47
Makoto
  • 104,088
  • 27
  • 192
  • 230
  • ...and from what era is your CPU and memory @CarlosHeuberger? – Makoto Dec 07 '18 at 18:06
  • 1
    This benchmark is not meaningful either - you might want to look into JMH https://openjdk.java.net/projects/code-tools/jmh/ – Clashsoft Dec 07 '18 at 18:15
  • still from the Christian Era... but not sure how this could change relative speed comparison... – user85421 Dec 07 '18 at 18:15
  • @Clashsoft: I don't have the luxury of running a JMH-oriented benchmark right now, but this seemed to be the quick way to go about fixing what were a few glaring issues with the benchmark. Perhaps you'd like to post your own answer with JMH benchmarks and demonstrate what's going on, too? – Makoto Dec 07 '18 at 18:18
  • @CarlosHeuberger: If your machine is fairly old and your memory isn't very fast, it's likely you're going to see performance degradation when performing something compute-intensive. This is why warming up JIT is necessary where possible, as well as taking stock of what machine you're running on. For instance, if I threw this code on my Threadripper I'd probably get different results, but I would wager they'd be consistent with what I expect for the standard runtime order of a linked list insert. – Makoto Dec 07 '18 at 18:20
  • the performance degradation should affect both list... just strange that my results with that code (including warm up) are VERY similar to the ones in the question... but never mind... – user85421 Dec 07 '18 at 19:00