How ArrayList provides random access behaviour?

Question

ArrayList is simply implemented as an Object[]. I know it implements the RandomAccess interface, but it is only a marker interface...

So, my question is: Why/How ArrayList provides the random access feature?

EDIT 1: perhaps I should make this clearer...what I want to understand is why it is constant time to access the element while it is an Object[]?

Answer 1

By comparing a LinkedList, an ArrayList and an Array visually should makes things easy:

Linked list:

+----+      +----+      +----+      +----+
|Head| ---> | e1 | ---> | e2 | ---> | e3 | ---> null
+----+      +----+      +----+      +----+

Now, let say I want to get element e2, however the linkedlist itself holds the reference of the headNode. To get to e2, I have to traverse all the way to e2 from the HeadNode. Clearly, this does not provides constant time operation as you can't access any of the elements directly without traversing through the list.

Array:

+----++----++----++----+
| e1 || e2 || e3 || e4 |  (value)
+----++----++----++----+
| 01 || 02 || 03 || 04 |  (address)
+----++----++----++----+

Imagine this, when you have a variable holding an array, only the address of the first element (e1) is held in the variable. The following array elements will be stored in the next available memory block. The array elements sit next to each other in a sequential sequence in memory. This makes it a constant time operation when you need to access a specific element. For example, when you want to access e3 and each memory block is 4 bytes. From the first element, move 2 blocks of memory (8 bytes) from the array reference. The key to constant time operation is: No traversing needed. It just has to calculate how many bytes to shift from current location according to size of each block and number of blocks to move (indicated by array index). In Java, when you try to shift beyond the bounds of the allocated memory for the array, it gives you an ArrayIndexOutOfBoundsException.

ArrayList:

Arraylist uses the same idea of an array. It will allocate a size of 10 initially. When it needs to grow (more elements added for instance), it creates a new array with added length for storage. Since the storage of the data is by array, the operation time will be same as array (i.e. constant time).