0

for example if I have an array list with elements (1,4,7,2,10,100,76) and a linked list with same data, and I want to search for key=2, which one would take less time, .contains() for array list or .contains for linked list? I have heard that array list is better for random access but does that mean it is also better for searching?

Dharamveer Grewal
  • 137
  • 4
  • 13
  • 3
    `ArrayList` is **better** for random access. Whoever told you `LinkedList` was mistaken. As for linear search, they should both have the same algorithmic complexity. But the constant factors are likely different. In short, you would have to test it to know which is better. – Elliott Frisch Apr 13 '20 at 23:18
  • Either list will do. It's the fact that you're doing sequential search that is the problem, not which of those two you use. – Andreas Apr 13 '20 at 23:28
  • If you're calling `contains` frequently, a possible optimization is to store the items in a `Set` instead of a `List`. If preserving insertion order is important for your use case, check out `LinkedHashSet`. – dnault Apr 13 '20 at 23:50

1 Answers1

4

Your biggest largely unnecessary overhead is having to box the primitives instead of using int[].

ArrayList will generally perform faster for practically any real situation (use ArrayDeque for queues). In this case accessing references to the elements is guaranteed to be sequential through memory, which is cache friendly, and also not incur the overhead of nodes and reading the next node reference.

A better algorithm, for all but the smallest collections, would be a binary search in a sorted array. Even a HashSet (or TreeSet) would be better.

Pedro Pinho
  • 33
  • 5
Tom Hawtin - tackline
  • 145,806
  • 30
  • 211
  • 305