Geek asks and answers

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

I understand that an ArrayList is an index-based data structure that allows you to access its element using an index, but LinkedList is not designed for an index, so why does it have a get (index) method that allows direct access to an element ?

+7
source share
3 answers

It really is just a solution to implement. Although the array is likely to be a pretty useless data structure if you can't search for items by index, adding index search to the implementation of a linked list does no harm (well, if users don't accept it quickly - see below), and sometimes it come in handy.

Each item can be assigned a number as follows:

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

From here it is trivial to write a function that returns an element at any given index.

Please note that index search on linked lists will be slow - if you want, let them say that the item is in the middle, you will need to work through half the list to get there.

+2
source

, , . , get, . , .

+2

, LinkedLists .

However, a fixed index for each element in the data structure will contradict the purpose of LinkedList and, for example, make some delete / add operations slower, because the structure will need to be reindexed every time. This will take linear time, even for items at the beginning and at the end of a list that are critical to the effectiveness of Java LinkedList.

From the implementation of the Java LinkedList, you can see that there is no access to the element with a constant time index, but there is a linear traversal in which the exact element is calculated on the go.

0
source

More articles:


All Articles