Why LinkedList over ArrayList for Insertion and Deletion?

[Gagan Popli]

Hi,

I would like to understand that, why in all the books its mentioned that LinkedList should be used when we are trying to do frequent insertions and deletions and not ArrayList.
They do not explain "why".

Please do let me why is that we use LinkedList for frequent insertions and deletion, what is it that it provides better than ArrayList?

Thanks.

[Sudhakar Sharma]

Hi,
good question, we should think about it. why? Explore it youself for better understanding of data-structure.

[Anuj Prashar]

Arralist internally uses array & when you run an "add" command a new Array of size more than old array will be created and in deletion that internal array will be modified. Whereas in linkedlist there are three parts. First part stores the pointer to previous element, second stores the data & third stores pointer to next element. So when insertion & deletion happens in linkedlist these pointers get updated. Thats why linkedlist is fast.


Check this
link1.
link2.

[Luigi Plinge]

LinkedLists can be slow as well. I did some micro-benchmarking here. It depends on
- how you will be accessing the list elements
- and if by random access, where in the list you're adding / removing

If you need to add / remove using random access (e.g. list.remove(n)), LinkedLists will be much slower than ArrayLists if you're adding / removing at the middle or near the end, but faster at the beginning. This is because LinkedList needs to iterate through the first n elements to find it, but can do the actual removal quickly; ArrayList can find it quickly but removal is slow since all the higher elements need to be moved down into the gap.

If you're adding / removing via an Iterator, (e.g. if you need to go through a whole list and conditionally add / remove for each element) LinkedList should be faster, since it already knows where it is and insertion / deletion is quick.

[K Abhijit]

If you have little backgroud of data structures (in C,C++ since in Java everythign is readymade ) you would know the reason.

Lets understand these collection and their performance based on following aspects
1. Collection update: Insertion /Deletion :
2. Collection Access and Traversing

1. Insertion /deletion:
Have you ever heard of contiguous memory location? Arrays are maintained in Contiguous memory location,so any insertion /deletion result in re-alignment of all rest members...where as in linked list this overhead is out of question.

Suppose 0-1-2-3-4-5 ...n are memory references(addresses actually) holding the elements in Arraylist and linklist and if delete element 3rd one then

for Linklist the memory Structure would be 0-1-2-4-5...n : So time required for update is nearly constant
where as for Array list it would be
0-1-2-4-5 ------> this would get re-alined by shifting all elements one by one and would be 0-1-2-3-4-....n
this is the overhead.....So time required for update directly proportional to index of the Element undergoing change

2. Access /Traversing
Arraylist : being Randon access , memeber accessing , traversing time is almost constant (and FAST off course)....
linked list : where as in linked list being sequential access directly proportional to Lengh of list.
Now if you understand both data structures you would understand which one should be used when...

Neither of them would always be better than other, both are meant for different requirements and scenarios.
you need to understand your need and then take the decision.


please go through data structures you would understand it better.. this is very much a candy question... ....