If the worst case latency of ArrayList is a deal breaker, then almost certainly the average case latency of LinkedList is also a deal breaker. You maybe want s

If the worst case latency of ArrayList is a deal breaker, then almost certainly the average case latency of LinkedList is also a deal breaker. You maybe want something like a linked array, but it's staggeringly difficult to find a scenario where a Java LinkedList or c++ std::list is ever the optimal choice. You should pretty much always start with an ArrayList or std::vector and go from there if/when it ever turns out to be a hotspot in benchmarks or profiling