Why does ArrayList implement RandomAccess Interface?

Question

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

So in case of ArrayList, what is the point of implementing it?

Answer 1

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).

Answer 2

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;
    }
   

   }`

Answer 3

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 
}

Answer 4

RandomAccess interface signifies an Efficient Random access to elements of Collection.

In client code, you can check whether the collection is instance of RandomAccess and then only perform the Random access operations.

Elements from both LinkedList and ArrayList can be accessed randomly however ArrayList complexity is O(1) and LinkedList is O(n).

Answer 5

Let's see how you can practically make use of this marker interface. First the relevant parts from docs (bolds are mine just to emphasise).

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists. RandomAccess Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists. The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList).

Let's take an example. Suppose you are writing a generic implementation of algorithm such as sort and you are choosing quick sort as you want in-place sorting. Why generic ? Because maybe you want the algorithm to be able to work with reasonable and predictable performance characteristics on all kinds of List (there are many kinds out there - aren't). So your algorithm function would take a list as input and return the same list as sorted. For a moment let's leave aside the various factors which influence the performance of quick sort (such as already sorted data, repeated data, right choice of pivot etc.). Apart from the above characteristics of the data/sort another crucial point is that your algorithm makes heavy us of traversing the list - in this case it makes use of random access heavily as it needs to compare and swap elements. So what do you think - will your algorithm perform well on all types of List implementations. Think about LinkedList - there is a provision for random access in the API but it needs lots of traversals because of the very nature of how data is organised in list as nodes pointing to each other and the painful unavoidable act of going through large number of nodes to arrive at a random node. So your generic algorithm has more variability in terms of performance. What if you knew somehow that some Lists provide fast ramdom access and some do not. What if have a marker which says so. In comes the "RandomAccess" marker interface which is implemented (marked/annotated would be better word) by ArrayList to indicate (your code will typically check with instanceof RandomAccess test) that it's quite fast to access randomly it's data and you can rely on that to write an algorithm which performs and if some list does not then try an alternate algorithm or maybe convert it first into ArrayList or at worst reject such an input entirely.

Another part of doc deals with what is considered to be fast random by giving two different ways to access the underlying data which is easy to understand. Fast random access means the first runs faster than second at all times.

for (int i=0, n=list.size(); i < n; i++)
         list.get(i);

runs faster than this loop:
     for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();

Answer 6

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.

Answer 7

This seems pretty well described in the documentation: http://docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html

RandomAccess Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists. The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

 for (int i=0, n=list.size(); i < n; i++)
     list.get(i);   

runs faster than this loop:

 for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

Answer 8

Interfaces with no methods are called marker interfaces in Java.

As per the JavaDoc of RandomAccess:

Marker interface used by List implementations to indicate
that they support fast (generally constant time) random access.

For more information check the two JavaDoc pages.

http://docs.oracle.com/javase/6/docs/api/java/util/RandomAccess.html

http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html

Answer 9

RandomAccess interface has no method

This is called a marker interface and is a design pattern called marker interface pattern.

When I checked LinkedList it does not implement RandomAccess interface. So in case of ArrayList what is the point of implementing it?

Because random access in a LinkedList is O(n), while it's O(1) in an ArrayList.

It's stated in the doc :

The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList)