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