mzeeirka mzeeirka - 5 months ago 11
Java Question

Why is accessing an item by index slower in a linked list than an array?

I think I am missing a very obvious point but could not find it in my Java textbook.

I understand that node storage does not necessarily have to be contiguous in memory for linked list. Does this also mean that a linked list is not indexable? If so, then the only way to find an item in a linked list is to traverse the list, right, whereas you can

get
from an array by index?

Answer

Why is accessing an item by index slower in a linked list than an array?

A linked list has a chain of entries. If you want to get (say) the element at position 42, the code has to:

  • get the entry for the first element (position 0)
  • follow the next link to the entry for position 1
  • follow the next link to the entry for position 2

and so on .... 42 times in total.

There is no short cut.

I am still not understanding why a linked list is not indexable ....

Now a LinkedList is indexable in the sense that there is a get(int) operation that works. It is just that indexing a LinkedList is inefficient. In general, it takes O(N) steps to perform a get(i) in a linked list of length N. By contrast with an array, or an ArrayList, you can retrieve any element of the data structure in one step. We say that the complexity is O(1).

Contrast this with (say) Set objects in general, and HashSet in particular. The HashSet class is NOT indexable because there is no get(int) method to retrieve the set element at position i. Indeed, even the notion of "position i" in a set is meaningless. The ordering of the elements in a Set is unspecified and (for some Set implementations, like HashSet) it may be effectively indeterminate.