ArrayList vs LinkedList: Addition

In previous post, we introduced this List collection and some implementations like LinkedList and ArrayList.

In this post, we are going to compare ArrayList and LinkedList performance using addition operations.

TRY IT YOURSELF: You can find the source code of this post here.

Java Collections List Series

Environment

  • JDK 11.0.3, OpenJDK 64-Bit Server VM, 11.0.3+7-Ubuntu-1ubuntu218.04.1
  • Ubuntu 18.04
  • Memory 15,6 GiB
  • Processor Intel® Core™ i7-7500U CPU @ 2.70GHz × 4
  • Graphics Intel® HD Graphics 620 (Kaby Lake GT2)
  • OS 64-bit
  • Disk 387,9 GB
  • Intellj IDE Community 2018.3

Approach

  • We are going to use JMH for the micro benchmark.
  • We are going to use a list of 10.000.000 of elements, generated randomly, and we are going to calculate the average response time in 10 iterations.
  • As JMH doesn’t allow sharing data between benchmarks, we are going to create a file with the list of elements, and read from it by each benchmark. In that way, we guarantee we are measuring the same scenario.

Adding at the End – add(type)

Now, let’s see the code for measuring how ArrayList and LinkedList behave when we need to add at the end:

  @Test
  public void add_end()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListAdditionEndTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection<RunResult> runResults = new Runner(opt)
            .run();

    Result arrayListResult = Utils
            .find("arrayList",
                    runResults);
    Result linkedListResult = Utils
            .find("linkedList",
                    runResults);

    assertThat(linkedListResult.getScore())
            .isLessThan(arrayListResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public ArrayList<Integer> arrayList(
          ArrayListExecutionPlan executionPlan) {
    ArrayList<Integer> list = executionPlan.arrayList;

    list.add(executionPlan.element);

    return list;
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public LinkedList<Integer> linkedList(
          LinkedListExecutionPlan executionPlan) {
    LinkedList<Integer> list = executionPlan.linkedList;

    list.add(executionPlan.element);

    return list;
  }

TRY IT YOURSELF: You can find this source code here.

Now, let’s see the results:

ArrayList vs LinkedLists performance, adding at the end

That is pretty interesting, LinkedList is pretty fast. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

ArrayList example

Now, we want to add a 2 number to the end of the list. However, this is a pure Java array, it means, we only have 7 spots for numbers, nothing more. So, ArrayList will do the following:

1. Creates a new pure Java array with more space:

New array bigger

NOTE: ArrayList can choose to increase in different ways, list.size()/2 is the more common.

2. Copy the elements from our previous array to the new one:

Copying elements

3. Add the element we requested:

Add the new element

We can conclude:

  • In the worst case, we need to create a new bigger array, if we reach the current size, this means, we will reserve more memory than we might not use.
  • We need to copy the whole array in a new one in the worst case, so, there are n operations.
  • The complexity of this operation is O(n).
  • The following additions are going to be fast until we reach the new size.
  • There is a limit. The max capacity for a pure Java array is 2147483639.

LinkedList

Well, let’s use this example:

LinkedList example

Now, we want to add a 2 number to the end of the list. This is the process:

1. Create a new node for the new element:

New node

2. Linking the new node to the Tail:

Linking the new node

3. Moving the Tail to the new node:

Moving the tail

We can conclude:

  • We only need to create a new node and linked to the tail.
  • The amount of operations is 1.
  • The complexity of this operation is O(1).
  • The size limit here is defined by your JVM memory, there is no other restriction.

Adding to the Middle – add(index, type)

Now, let’s see the code for measuring how ArrayList and LinkedList behave when we need to add at the middle:

  @Test
  public void add_middle()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListAdditionMiddleTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection<RunResult> runResults = new Runner(opt)
            .run();

    Result arrayListResult = Utils
            .find("arrayList",
                    runResults);
    Result linkedListResult = Utils
            .find("linkedList",
                    runResults);

    assertThat(linkedListResult.getScore())
            .isLessThan(arrayListResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public ArrayList<Integer> arrayList(
          ArrayListExecutionPlan executionPlan) {
    ArrayList<Integer> list = executionPlan.arrayList;

    list.add(list.size() / 2, executionPlan.element);

    return list;
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public LinkedList<Integer> linkedList(
          LinkedListExecutionPlan executionPlan) {
    LinkedList<Integer> list = executionPlan.linkedList;

    list.add(list.size() / 2, executionPlan.element);

    return list;
  }

TRY IT YOURSELF: You can find this source code here.

Now, let’s see the results:

ArrayList vs LinkedLists performance, adding at the middle

LinkedList is faster. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

ArrayList example

Now, we want to add a 2 number to the middle, before 9 number of the list. So, ArrayList will do the following:

1. Creates a new pure Java array with with more space:

New array bigger

2. Copy the elements from our previous array to the new one:

Copying elements

3. Moves the elements after the index one position:

Move elements one position

4. Insert the element to the empty position:

Insert the element

We can conclude:

  • In the worst case, we need to create a new bigger array, if we reach the current size, this means, we will reserve more memory than we might not use.
  • We need to copy the whole array in a new one in the worst case, so, the amount of operations is n.
  • We need to move the elements one position to create an empty space (n/2)
  • The total amount of operations needed is n + n/2.
  • The complexity of this operation is O(n).
  • Any insertion will require to move the elements one position.
  • There is a limit. The max capacity for a pure Java array is 2147483639.

LinkedList

Well, let’s use this example:

LinkedList example

Now, we want to add a 2 number before the 9 number of the list. This is the process:

1. Move to the index from the closest reference (Head or Tail), in this case, Head is closest:

Moving from the head to the index

2. Creating the new node:

Creating the new node

3. Changing references from 5 number and 9 number to the new node:

Changing references to insert new node

We can conclude:

  • In the worst case, we need to move from the head/tail to the index (n/2).
  • The complexity of this operation is O(n).
  • We only need to create a new node and linked to the tail.
  • The size limit here is defined by your JVM memory, there is no other restriction.

Adding to the Start – add(0, type)

Now, let’s see the code for measuring how ArrayList and LinkedList behave when we need to add at the start:


  @Test
  public void add_start()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListAdditionStartTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection<RunResult> runResults = new Runner(opt)
            .run();

    Result arrayListResult = Utils
            .find("arrayList",
                    runResults);
    Result linkedListResult = Utils
            .find("linkedList",
                    runResults);

    assertThat(linkedListResult.getScore())
            .isLessThan(arrayListResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public ArrayList<Integer> arrayList(
          ArrayListExecutionPlan executionPlan) {
    ArrayList<Integer> list = executionPlan.arrayList;

    list.add(0, executionPlan.element);

    return list;
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public LinkedList<Integer> linkedList(
          LinkedListExecutionPlan executionPlan) {
    LinkedList<Integer> list = executionPlan.linkedList;

    list.add(0, executionPlan.element);

    return list;
  }

TRY IT YOURSELF: You can find this source code here.

Now, let’s see the results:

ArrayList vs LinkedLists performance, adding at the start

LinkedList is faster, pretty fast. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

ArrayList example

Now, we want to add a 2 number to the start. So, ArrayList will do the following:

1. Creates a new pure Java array with with more space:

New array bigger

2. Copy the elements from our previous array to the new one:

Copying elements

3. Moves the elements after the index, one position, in this case, it needs to move everything:

Move everything one position

4. Insert the element at the start:

Insert at the start

We can conclude:

  • In the worst case, we need to create a new bigger array, if we reach the current size, this means, we will reserve more memory than we might not use.
  • We need to copy the whole array in a new one in the worst case (n).
  • We need to move every element, one position to create an empty space at the start (n).
  • The complexity of this operation is O(n).
  • There is a limit. The max capacity for a pure Java array is 2147483639.

LinkedList

Well, let’s use this example:

LinkedList example

Now, we want to add a 2 number at the start of the list. This is the process:

1. Create a new node for the new element:

Create a new node at start

2. Linking the new node to the Head:

Linking the new node to the head

3. Moving the Head to the new node:

Moving the head

We can conclude:

  • We only need to create a new node and linked to the head.
  • The amount of operations is 1.
  • The complexity of this operation is O(1).
  • The size limit here is defined by your JVM memory, there is no other restriction.

Summary

Now, this is a summary of the amount of operations in addition between ArrayList and LinkedList:

ArrayListLinkedList
OperationMethodBestWorstBestWorst
Add At Endadd(type)1n11
Add At Middleadd(index, type)n/2n + n/2n/2n/2
Add At Startadd(0, type)nn + n11

Then, this is a summary of the Big O complexity in addition operations between ArrayList and LinkedList:

ArrayListLinkedList
OperationMethodBestWorstBestWorst
Add At Endadd(type)O(1)O(n)O(1)O(1)
Add At Middleadd(index, type)O(n)O(n)O(n)O(n)
Add At Startadd(0, type)O(n)O(n)O(1)O(1)

Final Thought

As we saw, LinkedList is better than ArrayList when we talk about addition operations.

This means, if you have a use case were you required a constant performance through the additions, you should choose the LinkedList.

In the following post, we are going to talk about deletion operations.

Advertisements

3 comments

Leave a Reply to ArrayList vs LinkedList: Deletion – The Coders Tower Cancel reply

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