mzeeirka - 10 months ago 26

Java Question

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`

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.