Why does ArrayList implement RandomAccess Interface?

1) There are two classes which implement RandomAccess Interface. They are:

ArrayList (Part of List<I>)
Vector    (Part of List<I>)

2) The purpose of RandomAccess Interface is to retrieve any random element in the Collection at the same speed. Example: I have a collection of 1 million objects. Implementing RandomAccess interface makes your time to retrieve the 10th element and 17869th element the same. This makes ArrayList and Vector more powerful.

3) RandomAccess Interface has no methods or fields and is also called a Marker Interface. These are used to indicate something to the compiler, in other words implementing these interfaces is meant to imply some special treatment of the implementing class.

The interface has no methods(Marker Interface), but you can use it to test whether a particular collection supports efficient random access

Collection<Integer> c = new ArrayList<Integer>();
if (c instanceof RandomAccess)
{
        System.out.println("use random access algorithm -> like ArrayList");//fast access date
}
else
{
        System.out.println("use sequential access algorithm -> like LinkedList");//fast delete data 
}

1. The mere presence of marker interface is that, it indicates ( or expects ) specific behavior from the implementing class.

2. So, in our case, ArrayList implements RandomAccess marker interface.

3. So, the expectation from ArrayList class, is that, it should produce RandomAccess behavior to the clients of ArrayList class, when the client wants to access some element at some index.

So, how has ArrayList implemented this randomness ?

public E get(int index) {
        rangeCheck(index); // to check for out of bounds index.

        return elementData(index); // another method invocation
    }

E elementData(int index) {
        return (E) elementData[index]; // accesses internal array.
    }

// following is the internal array , used by ArrayList
transient Object[] elementData; // non-private to simplify nested class access

4. Now, we know that LinkedList has not implemented RandomAccess, so , it is not expected to guarantee random access behavior. Let us also check LinkedList code below, Notice the for loop here, so, it is a sequential access. And also observe the bitwise operator trick: size >> 1 means that, size is divided by 2. So, it basically checks , if the index is in first half or second half. If it is in second half, it makes sense to start from the end. It is an optimization, good trick.

   `public E get(int index) { checkElementIndex(index); return node(index).item; }

   Node node(int index) { // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
   

   }`

RandomAccess : This interface introduced in Java version 1.4. It marks the implementations of list which can be accessed randomly. It is present in java.util.RandomAccess

Marker interface used by List implementations to indicate that they support fast random access.

More accurately, the RandomAccess interface identifies List implementations which are faster to iterate using the List.get() method rather than using the Iterator.next() method.

ArrayList implements RandomAccess interface. RandomAccess interface has no methods. When I checked LinkedList it does not implement RandomAccess interface.

Because ArrayList & Vector are index based & LinkedList is follows Double Linked List.

Time Complexity

ArrayList: The ArrayList in Java is backed by an array. Random access takes O(1) time

get() – is always a constant time O(1) operation

LinkedList LinkedList is a linear data structure which consists of nodes holding a data field and a reference to another node.

get() – searching for an element takes O(n) time.

Note: ArrayList can give you any element in O(1) complexity as the array has random access property. You can access any index directly without iterating through the whole array.

LinkedList has a sequential access property. It needs to iterate through each element to reach a given index, so time complexity to get a value by index from LinkedList is O(N).