Интерфейс 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.