Use of Linkedlist [duplicate]

Question

i studied that we use LinkedList if we want more number of insertion / deletion ; And we use ArrayList if we have more retravision.

But my doubt is in programming all insertion needs retrivtion at every time , otherwise insertion is nearly useless. At everytime for manipulating, for calculation every time we need to retrive data.

So why we should use Linkedlist ?

Answer 1

Let’s consider a program that does the following actions:

1. adds n elements to the end of the list
2. retrieves the first element from the list n times.

In this case, if you use LinkedList all insertions will take O(1) time and all retrievals will also take O(1).

On the other hand, if you use ArrayList, you may need to increase the array size of the array backing the list multiple times , each times requires to duplicate the array which takes O(n). When you do the retrievals, depending on the implementation, you may need to decrease the array size multiple times, each time takes O(n) once again.

So as you can see, there are cases where LinkedList has advantages on ArrayList.

This mainly results from the individual operation time complexity of each data structure, as demonstrated above.