Linked Lists Are Bad (Part 1)

This might not be a surprising fact to any performance hacker but could quite shocking from Big-O point of view.

The claim: Linked Lists are bad and don’t have any use case.

In this post we will see that even in the most simple and common use case which is sequentially iterating over the list ( linear scan), An ArrayList would perform much better.

Problem: Linear scan over a list.

LinkedList Big-O: O(n)

ArrayList Big-O: O(n)

So both structures have the same characteristics for this use case.  Now lets hack a quick JMH benchmark to see if this holds.

private LinkedList<Integer> linkedList;
    private ArrayList<Integer> arrayList;

    @Setup
    public void setup(){
        linkedList = new Random().ints().limit(10_000_000).boxed()
                .collect(Collectors.toCollection(LinkedList::new));
        arrayList = new Random().ints().limit(10_000_000).boxed()
                .collect(Collectors.toCollection(ArrayList::new));
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public void iterateLinkedList(Blackhole blackhole){
        for (Integer i : linkedList) {
            blackhole.consume(i);
        }
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public void iterateArrayList(Blackhole blackhole){
        for (Integer i : arrayList) {
            blackhole.consume(i);
        }
    }

When running it with the following configuration

public static void main(String[] args) throws RunnerException {
        Options options = new OptionsBuilder()
                .include(ListsBenchmark.class.getSimpleName())
                .warmupIterations(3)
                .measurementIterations(10)
                .forks(1)
                .build();

        Runner runner = new Runner(options);
        runner.run();
    }

It gives the following

Benchmark                         Mode  Cnt    Score    Error  Units
ListsBenchmark.iterateArrayList   avgt   10   58.399 ± 14.834  ms/op
ListsBenchmark.iterateLinkedList  avgt   10  132.461 ±  7.075  ms/op

Showing that scanning an ArrayList is way more efficient than scanning a LinkedList.

Why?

Reactions GIF - Find & Share on GIPHY

Locality. Locality does matter. Reading a value from memory is expensive compared to reading it from the cache. Arrays are great in getting the best out of your cache line by batch loading relevant data to the cache.

Memories are the new disks. Cliff Click.

Another problem with linked lists is their huge footprint. Every node needs special object allocation and maintains at least two references to the next and previous node. This problem just doesn’t exist in ArrayList where all what you allocate is big array object and extra variables for bookkeeping.

Advertisements

Leave a Reply

Name and email address are required. Your email address will not be published.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

You may use these HTML tags and attributes:

<a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <s> <strike> <strong> 

%d bloggers like this: