CODEWITHSUNDEEP
javaarraylistdata-structurescollectionslinked-list
Ivan Syrups
Ivan Syrups

Reputation: 23

Why does adding an element at the end of LinkedList take longer than an ArrayList?

I learned that adding an element at the end of a LinkedList is O(1) since we're just adding linking an object to the last node of the list And ArrayList is also O(1), but worst case scenario is O(n) because of having to resize when there is no space in the array. I tried to put that to the test expecting the outcomes I learned, but the ArrayList was significantly faster in adding 10 million elements than the LinkedList.

After multiple tries, the ArrayList took around ~570 milliseconds, while the LinkedList took around ~1900 milliseconds.

public static void listPractice(List<String> test) {
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 10_000_000; i++) {
        test.add(String.valueOf(i));
    }
    System.out.println(System.currentTimeMillis() - startTime);

}

Seems very odd. I've been reading other discussions and I see a lot of programmers say that the LinkedList, in short words, kinda sucks. Is this evidence, or just something I'm missing?

Upvotes: 0

Views: 1297

Answers (1)

a guest
a guest

Reputation: 472

Adding an element to an array (that does not need resizing) requires copying a reference into an empty cell, and incrementing the count of object elements in the array.

Adding an element to a linked list requires allocating a new node, pointing the 'next' link of the former last entry to the new last entry, nulling the 'next' of the new entry, pointing the 'last' link of the head to the new entry, and pointing the previous link of the new entry to the former last entry. And then copying the object reference into the new node, and incrementing the count of elements in the list.

In short, the linked list requires an allocation and 4 more writes than the array version.

If you think linked lists suck, though, try using an array in a situation where you repeatedly remove the front element from your array of 10 million entries.

There are techniques to avoid having to shuffle all the entries down the array, but unless it's a circular array, it's probably going to shuffle. The ArrayList sources I've seen do shuffle, so removing the first of 10,000,000 entries is going to move the remaining 9,999,999 entries down. And removing the next entry will have to move the remaining 9,999,998 entries down...

Not to mention that your 10 million entry array needed to be able to get a contiguous 40 or 80 megabytes of memory.

The lesson is, different data structures have different sweet spots.

Upvotes: 2

Related Questions