• Post Reply Bookmark Topic Watch Topic
  • New Topic

Why LinkedList over ArrayList for Insertion and Deletion?  RSS feed

 
Gagan Popli
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 71
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
good question, we should think about it. why? Explore it youself for better understanding of data-structure.

 
Anuj Prashar
Ranch Hand
Posts: 99
Android Java Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 441
IntelliJ IDE Scala Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 88
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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... ....
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!