ArrayList vs LinkedList: Deletion

In previous post, we compared LinkedList and ArrayList in addition operations using JMH.

In this post, we are going to compare ArrayList and LinkedList performance using deletion 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.

Deleting from the End – remove(size - 1)

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

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

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListDeletionEndTest.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.remove(list.size() - 1);

    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.remove(list.size() - 1);

    return list;
  }

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

Now, let’s see the results:

ArrayList vs LinkedLists performance, removing from the end

That is pretty interesting, LinkedList and ArrayList have pretty much a equal behavior. Let’s see why they behave like that.

NOTE: Careful, if you run those tests multiple times, the result mightn’t be equal

ArrayList

Well, let’s use this example:

ArrayList example

Now, we want to remove the index 6 of the list. So, ArrayList will do the following:

  1. Set NULL the 6 position:
Set null the last position

2. Change the array size variable from 7 to 6:

Reduce the size in one

TIP: In a logic point of view, the ArrayList size is now 6, however, its pure array is 7. That means, the next time we need to add a new element at the end, is going to be fast, there is a position available.

We can conclude:

  • In the worst case, we just need to set NULL the last position
  • The amount of operations is 1.
  • The complexity of this operation is O(1).

LinkedList

Well, let’s use this example:

LinkedList example

Now, we want to remove the 6 index from the list. This is the process:

1.Move the Tail one index before:

Move the Tail one index before

2. Unlink the previous Tail from the new Tail:

Unlink the new Tail from the old Tail

3. The garbage collector is going to reclaim the unlinked node:

Unlinked node disappear

We can conclude:

  • We only need to unlink the node from the Tail.
  • The amount of operations is 1.
  • The complexity of this operation is O(1).

Deleting from the Middle – remove(size / 2)

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

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

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

    Collection<Integer> 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.remove(list.size() / 2);

    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.remove(list.size() / 2);

    return list;
  }

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

Now, let’s see the results:

ArrayList vs LinkedLists performance, removing from the middle

Again, LinkedList and ArrayList have pretty much a equal behavior. Let’s see why they behave like that.

ArrayList

Well, let’s use this example:

ArrayList example

Now, we want to remove the 3 index from the list. So, ArrayList will do the following:

1. Set NULL the 3 index:

Set the 3 index to NULL

2. Move the whole elements after 3 index one position before:

Move the elements one position before

We can conclude:

  • In the worst case, we need to move the half of the list one position before.
  • The amount of operations is n/2.
  • The complexity of this operation is O(n).

LinkedList

Well, let’s use this example:

LinkedList example

Now, we want to remove the 3 index from 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 3 index

2. Removing the reference from the 3 index, to previous (2) and next (4):

3. Linking the 2 index to 4 index:

Joining 2 index to 4 index

4. The garbage collector is going to reclaim the unlinked node:

Garbage collector reclaims the unliked node

We can conclude:

  • In the worst case, we need to move from the head/tail to the index
  • The amount of operations is n/2.
  • The complexity of this operation is O(n).

Removing from the Start – remove(0)

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


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

    Options opt = new OptionsBuilder()
            .include(
                    ArrayListVsLinkedListDeletionStartTest.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.remove(0);

    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.remove(0);

    return list;
  }

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

Now, let’s see the results:

ArrayList vs LinkedLists performance, removing from 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 remove the 0 index from the list. So, ArrayList will do the following:

1. Set NULL the 0 index:

Set NULL the 0 index

2. Move the whole elements one position before:

Moving the whole elements one position before

2. Change the array size variable from 7 to 6:

Reduce size in one

We can conclude:

  • In the worst case, we need to move the whole elements minus one, one position before.
  • The amount of operations is n-1.
  • The complexity of this operation is O(n).

LinkedList

Well, let’s use this example:

LinkedList example

Now, we want to remove the 0 index from the list. This is the process:

1. Move the Head one position forward:

Moving the Head one position forward

2. Unlink the 0 index from the Head:

Unlinking the 0 index from the Head

3. The garbage collector is going to reclaim the unlinked node:

Unlinked node disappear

We can conclude:

  • We only need to unlink the node from the Head.
  • The amount of operations is 1.
  • The complexity of this operation is O(1).

Summary

Okey, this is a summary of the amount of operations in the deletion operations between ArrayList and LinkedList:

ArrayListLinkedList
OperationMethodBestWorstBestWorst
Remove From
End
remove(size-1)1111
Remove From
Middle
remove(size/2)n/2n/2n/2n/2
Remove From
Start
remove(0)n-1n-111

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

ArrayListLinkedList
OperationMethodBestWorstBestWorst
Remove From
End
remove(size-1)O(1)O(1)O(1)O(1)
Remove From
Middle
remove(size/2)O(n)O(n)O(n)O(n)
Remove From
Start
remove(0)O(n)O(n)O(1)O(1)

Final Thought

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

However, ArrayList behaves similar in 2 of 3 deletion operations.

In the following post, we are going to talk about sort, get and iteration operations.

Advertisements

3 comments

Leave a Reply to ArrayList vs LinkedList: Addition – 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