Como é avaliada a eficiência de procurar um elemento por valor em ArrayList?

No ArrayList, a procura de um elemento por valor geralmente é implementada pelo método contains() ou indexOf(), que percorre os elementos do início ao fim, comparando cada um com o valor procurado. A eficiência dessa busca é O(n), onde n é o número de elementos na lista, pois o ArrayList não indexa os elementos pelo valor.

Exemplo:

ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
boolean found = list.contains("banana"); // percorrendo os elementos

Se for necessária uma busca mais rápida por valor, é melhor usar estruturas de dados com hash, como HashSet ou HashMap.