Интерфейс RandomAccess

public interface RandomAccess

Маркерный интерфейс, используемый List реализациями для указания того, что они поддерживают быстрый (обычно постоянное время) случайный доступ. Основная цель этого интерфейса — позволить общим алгоритмам изменять своё поведение для обеспечения хорошей производительности, когда они применяются к спискам со случайным или последовательным доступом.

Лучшие алгоритмы для работы со списками со случайным доступом (такие как ArrayList) могут иметь квадратичное поведение при применении к спискам с последовательным доступом (таким как LinkedList). Общие алгоритмы для списков должны проверять, является ли данный список instanceof этим интерфейсом, прежде чем применять алгоритм, который мог бы обеспечить плохую производительность, если бы он был применён к списку с последовательным доступом, и изменять своё поведение при необходимости, чтобы гарантировать приемлемую производительность.

Признаётся, что различие между случайным и последовательным доступом часто размыто. Например, некоторые List реализации обеспечивают асимптотически линейное время доступа, если они становятся огромными, но постоянное время доступа на практике. Такая List реализация, как правило, должна реализовывать этот интерфейс. Как правило, List реализация должна реализовывать этот интерфейс, если для типичных экземпляров класса этот цикл:

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

выполняется быстрее, чем этот цикл:

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

Этот интерфейс является частью Java Collections Framework.