Какая структура данных лучше подходит для поиска элементов с использованием последовательного поиска - Array List или Linked List?

Question

например, если у меня есть список массивов с элементами (1,4,7,2,10,100,76) и связанный список с теми же данными, и я хочу найти ключ = 2, что займет меньше времени , .contains () для списка массивов или .contains для связанного списка? Я слышал, что список массивов лучше для произвольного доступа, но значит ли это, что он также лучше для поиска?

Answer 1

Ваши самые большие, по большей части ненужные накладные расходы, это необходимость упаковывать примитивы вместо использования int[].

ArrayList, как правило, работает быстрее практически в любой реальной ситуации (используйте ArrayDeque для очередей). В этом случае доступ к ссылкам на элементы гарантированно будет последовательным через память, что благоприятно для кэша, а также не потребует дополнительных затрат на узлы и чтения следующей ссылки на узел.

Лучший алгоритм для всех, кроме самые маленькие коллекции, это будет двоичный поиск в отсортированном массиве. Даже HashSet (или TreeSet) будет лучше.