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