LinkedList does not provide index based access, so why does it have get(index) method?

Question

I understand that ArrayList is index based datastructure, that allows you to access its element using the index but LinkedList is not supposed index based so why does it have get(index) method that allows direct access to the element?

Accepted Answer

This is really just an implementation decision. While an array would probably be a fairly useless data structure if you can't look up elements by index, adding a by-index lookup to a linked-list implementation doesn't do any harm (well, unless users assume it's fast - see below), and it does come in handy sometimes.

One can assign every element a number as follows:

```
      0               1           2           3           4
Head (Element0) -> Element1 -> Element2 -> Element3 -> Element4 -> NULL
```

From here, it's trivial to write a function to return the element at some given index.

Note that a by-index lookup on a linked-list will be slow - if you're looking for let's say the element in the middle, you'll need to work through half the list to get there.

LinkedList does not provide index based access, so why does it have get(index) method?

Solution

Problem