Of course, deletion is a whole different story. I was talking about addition in isolation.

Anyway, I felt I had to run the benchmarks myself.

  @Benchmark
  @Fork(1)
  @BenchmarkMode(Mode.Throughput)
  @OutputTimeUnit(TimeUnit.SECONDS)
  public Object arrayListPreallocAddMillionNulls() {
    ArrayList<Object> arrList = new ArrayList<>(1048576);
    for (int i = 0; i <= 1_000_000; i++) {
      arrList.add(null);
    }
    return arrList;
  }

  @Benchmark
  @Fork(1)
  @BenchmarkMode(Mode.Throughput)
  @OutputTimeUnit(TimeUnit.SECONDS)
  public Object arrayListAddMillionNulls() {
    ArrayList<Object> arrList = new ArrayList<>();
    for (int i = 0; i <= 1_000_000; i++) {
      arrList.add(null);
    }
    return arrList;
  }

  @Benchmark
  @Fork(1)
  @BenchmarkMode(Mode.Throughput)
  @OutputTimeUnit(TimeUnit.SECONDS)
  public Object linkedListAddMillionNulls() {
    LinkedList<Object> linkList = new LinkedList<>();
    for (int i = 0; i <= 1_000_000; i++) {
      linkList.add(null);
    }
    return linkList;
  }

And as I expected, on JDK 8 ArrayList with an appropriate initial capacity was faster than LinkedList. Admittedly not an order of magnitude difference, only 1.7x.

  JDK8
  Benchmark                                      Mode  Cnt    Score    Error  Units
  MyBenchmark.arrayListAddMillionNulls          thrpt    5  229.950 ±  9.994  ops/s
  MyBenchmark.arrayListPreallocAddMillionNulls  thrpt    5  344.116 ±  7.070  ops/s
  MyBenchmark.linkedListAddMillionNulls         thrpt    5  199.446 ± 15.910  ops/s

But! On JDK 17 the situation is completely upside-down:

  JDK17
  Benchmark                                      Mode  Cnt    Score    Error  Units
  MyBenchmark.arrayListAddMillionNulls          thrpt    5   90.462 ± 18.576  ops/s
  MyBenchmark.arrayListPreallocAddMillionNulls  thrpt    5  214.079 ± 15.505  ops/s
  MyBenchmark.linkedListAddMillionNulls         thrpt    5  216.796 ± 19.392  ops/s

I wonder why ArrayList with default initial capacity got so much worse. Worth investigating further.