CODEWITHSUNDEEP
javaarraylistlinked-list
Johanna
Johanna

Reputation: 27628

Is it more efficient to remove elements from an ArrayList or a LinkedList?

In theory, is it more efficient to remove elements from an ArrayList or a LinkedList?

Upvotes: 1

Views: 2273

Answers (3)

Ayman Amjad
Ayman Amjad

Reputation: 264

ArrayList internally uses a dynamic array to store the elements so manipulation with ArrayList is slow because it internally uses an array.

If any element is removed from the array, all the bits are shifted in memory while LinkedList internally uses a doubly linked list to store the elements.

Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.

Upvotes: 2

GManNickG
GManNickG

Reputation: 503805

Well, removal of an element from a (doubly-linked-)list is O(1). But removal from an array will require that the remaining elements are shifted down one space in the array, which is O(n).

That said, getting a specific element in a list by index is O(n), while getting a specific element in an array by index is O(1).

So, the for actual removal, LinkedList will be better. There is more info on Array's versus LinkedList here.

Upvotes: 5

erickson
erickson

Reputation: 269647

It is "easier" (that is, more efficient) to remove them from a LinkedList, because removal from an ArrayList requires moving all subsequent elements to a new position in the list—all subsequent elements of the array must be assigned a new value. With a linked list, only one pointer (or two, with a doubly-linked list) must be re-assigned.

Upvotes: 10

Related Questions