Replace remaining usage of LinkedList with ArrayList/ArrayDeque

[stsypanov]

As of 2020 there's no need to use LinkedList:

• empty ArrayList is more lightweight than LinkedList:

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(jvmArgsAppend = {"-Xms2g", "-Xmx2g"})
public class ListBenchmark {
  @Benchmark
  public Object arrayList() {
    return new ArrayList<>();
  }

  @Benchmark
  public Object linkedList() {
    return new LinkedList<>();
  }
}

which on JDK 11 gives

ListBenchmark.arrayList                                    avgt   15     4.011 ±   0.120   ns/op
ListBenchmark.arrayList:·gc.alloc.rate.norm                avgt   15    24.002 ±   0.001    B/op

ListBenchmark.linkedList                                   avgt   15     4.243 ±   0.181   ns/op
ListBenchmark.linkedList:·gc.alloc.rate.norm               avgt   15    32.002 ±   0.001    B/op

if we put one element then LinkedList wins:

enchmark                                                  Mode  Cnt     Score     Error   Units
ListBenchmark.arrayList                                    avgt   15     9.188 ±   0.831   ns/op
ListBenchmark.arrayList:·gc.alloc.rate.norm                avgt   15    80.005 ±   0.001    B/op
ListBenchmark.linkedList                                   avgt   15     8.148 ±   0.285   ns/op
ListBenchmark.linkedList:·gc.alloc.rate.norm               avgt   15    56.004 ±   0.001    B/op

in other cases LinkedList looses:

2 elements
Benchmark                                                  Mode  Cnt     Score     Error   Units
ListBenchmark.arrayList                                    avgt   15    11.308 ±   0.290   ns/op
ListBenchmark.arrayList:·gc.alloc.rate.norm                avgt   15    80.006 ±   0.001    B/op
ListBenchmark.linkedList                                   avgt   15    11.898 ±   0.608   ns/op
ListBenchmark.linkedList:·gc.alloc.rate.norm               avgt   15    80.006 ±   0.001    B/op

3 elements
ListBenchmark.arrayList                                    avgt   15    14.763 ±   1.452   ns/op
ListBenchmark.arrayList:·gc.alloc.rate.norm                avgt   15    80.006 ±   0.001    B/op
ListBenchmark.linkedList                                   avgt   15    19.166 ±   1.686   ns/op
ListBenchmark.linkedList:·gc.alloc.rate.norm               avgt   15   104.008 ±   0.001    B/op

• ArrayList provides better data locality and less cache-misses due to usage of array
• LinkedList consumes much more memory per element, see https://stackoverflow.com/a/7671021/12473843
• the only case when LinkedList could probably win (re-use of existing iterators to insert and remove elements) are comparatively seldom, in most of the cases we just store elements and iterate over them
• if frequently used LinkedList gets C2-compiled and thus requires space in Code Cache

[jhoeller]

Since we've done such a pass towards ArrayList before (#21575 and further ones), there should be a limited amount of LinkedList usage in the codebase already, mostly for cases where there is usually only one element to keep (similar to the performance indications above). I'll do one more pass for 5.3, pretty sure there are further cases than we can easily switch to ArrayList (although probably not very performance relevant, mostly just configuration storage).

[jhoeller]

Would using new ArrayList(0) / new ArrayList(1) get us close to the LinkedList numbers for the empty and one-element case, respectively? We're mostly just trying to avoid the 10-element array allocation for scenarios with one element... and also to initialize empty lists such that they don't grow to a 10-element array just for one element added eventually.

[wind57]

@jhoeller yes, it should get a lot closer to those. there has been some discussion here https://stackoverflow.com/questions/56647032/why-does-using-different-arraylist-constructors-cause-a-different-growth-rate-of for example (disclaimer: I asked that question).