How does an ArrayList retrieve data in constant time? [duplicate]

Question

One interview question which I couldn't answer and couldn't find any relevant answers online.

Suppose in an arraylist, there are 10000 data, and I want to find the number which is currently on 5000th index, how does the arraylist know the indexes and give result in constant time?

Because if we are traversing through the arraylist to find the data, it would take linear time and not constant time.

Thanks in advance.

Answer 1

The storage backing an ArrayList is an array. Whether primitive values or object references are stored, all objects in the array are in consecutive order in memory.

For array access, all the compiler has to do is have instructions that calculate the correct memory address based on the initial address and which index is desired, which is O(1). Then it can go directly to that calculated address. There is no traversing, so it is not O(n).

Answer 2

ArrayLists can be thought of as an array of Objects (Which happens to be exactly how they are implemented). You can index into it as any other array at O(1). The advantage over a true "Array" is that it tracks a "Length" independent of the array's length and automatically extends the array when it "overflows"--plus a few extra operations.

LinkedLists (probably the structure you are thinking of) require you to walk from one item to the next, so the implementation is O(n) to find an item at an index.