Рекомендации по выбору между ArrayList и LinkedList

List<Integer> ints = ...; // varies in size

int LAST = ints.size() - 1;
int MIDDLE = ints.size() / 2;

// читаем 1й элемент списка
ints.get(0);

// читаем последний элемент
ints.get(LAST);

// читаем средний элемент
ints.get(MIDDLE);

ArrayList     SIZE  Score   Error  Units
Read first      10  1.181 ± 0.022  ns/op
Read first     100  1.200 ± 0.041  ns/op
Read first    1000  1.167 ± 0.009  ns/op
Read first   10000  1.174 ± 0.014  ns/op

LinkedList    SIZE  Score   Error  Units
Read first      10  1.127 ± 0.030  ns/op
Read first     100  1.107 ± 0.008  ns/op
Read first    1000  1.121 ± 0.016  ns/op
Read first   10000  1.119 ± 0.014  ns/op

ArrayList     SIZE  Score   Error  Units
Read last       10  1.248 ± 0.020  ns/op
Read last      100  1.232 ± 0.035  ns/op
Read last     1000  1.240 ± 0.019  ns/op
Read last    10000  1.254 ± 0.040  ns/op

LinkedList    SIZE  Score   Error  Units
Read last       10  1.493 ± 0.040  ns/op
Read last      100  1.467 ± 0.019  ns/op
Read last     1000  1.475 ± 0.019  ns/op
Read last    10000  1.484 ± 0.042  ns/op

ArrayList     SIZE  Score   Error  Units
Read middle     10  1.571 ± 0.055  ns/op
Read middle    100  1.616 ± 0.073  ns/op
Read middle   1000  1.543 ± 0.018  ns/op
Read middle  10000  1.537 ± 0.010  ns/op

LinkedList    SIZE     Score     Error  Units
Read middle     10     3.211 ±   0.023  ns/op
Read middle    100    31.118 ±   0.321  ns/op
Read middle   1000   566.079 ±   8.696  ns/op
Read middle  10000  7836.099 ± 902.666  ns/op

var ints = 
    IntStream.range(0, LIST_SIZE)
            .boxed()
            .collect(Collectors.toCollection(LinkedList::new));

var ints = new LinkedList<>();
var intsOther = new LinkedList<>();
for (int i = 0; i < LIST_SIZE; i++) {
    ints.add(i);
    for (int j = 0; j < SPARSE_INDEX; j++) {
        intsOther.add(j);
    }
}

LinkedList   SIZE  SPARSE    Score    Error  Units
Read middle  1000       0  561.428 ±  4.853  ns/op
Read middle  1000       1  602.401 ± 17.126  ns/op
Read middle  1000      10  944.997 ± 31.920  ns/op
Read middle  1000     100 1509.282 ± 28.749  ns/op

var ints = ...; // LinkedList или ArrayList  
for (var index = 0; index < ints.size(); index++) {  
    var v = ints.get(index);
    // pass v to the blackhole
}

for (var v : ints) {  
   // pass v to the blackhole
}

ArrayList         SIZE    Score   Error Units
Iterate iterator  1000    1.447 ± 0.024 ms/op
Iterate index     1000    1.986 ± 0.045 ms/op

LinkedList        SIZE    Score   Error Units
Iterate iterator  1000    4.950 ± 0.116 ms/op
Iterate index     1000  584.889 ± 4.396 ms/op

var ints = 
   IntStream.range(0, 1_000)
            .boxed()
            .collection(Collection.toCollection(LinkedList::new));

var copyOfInts = ints.stream().toList();
for (var v: copyOfInts) {
   // pass v to the blackhole
}

LinkedList           SIZE  ITERATION    Score    Error  Units
toList then iterate  1000          1    5.182 ±  0.347  ms/op
toList then iterate  1000         10   14.031 ±  0.793  ms/op
toList then iterate  1000        100  100.104 ±  7.422  ms/op

LinkedList      SIZE    Score    Error  Units
Insert first      10    7.002  ± 0.306  ns/op
Insert first     100    7.126  ± 0.424  ns/op
Insert first    1000    7.561  ± 0.371  ns/op
Insert first   10000    7.738  ± 0.614  ns/op

LinkedList      SIZE    Score    Error  Units
Adding            10    9.135  ± 0.137  ns/op
Adding           100    9.076  ± 0.082  ns/op
Adding          1000    9.795  ± 0.399  ns/op
Adding         10000    9.549  ± 0.202  ns/op

LinkedList      SIZE      Score     Error  Units
Insert middle     10     10.641 ±   0.679  ns/op
Insert middle    100     49.122 ±   1.808  ns/op
Insert middle   1000    584.870 ±   6.925  ns/op
Insert middle  10000  46157.961 ± 379.327  ns/op

ArrayList  SIZE    Score    Error  Units
Adding       10    2.215  ± 0.053  ns/op
Adding      100    2.184  ± 0.027  ns/op
Adding     1000    5.607  ± 0.856  ns/op
Adding    10000    5.240  ± 0.777  ns/op

ArrayList        SIZE    Score     Error  Units
Insert middle     10   23.708  ±  0.370  ns/op
Insert middle    100   25.399  ±  0.241  ns/op
Insert middle   1000   56.061  ±  0.840  ns/op
Insert middle  10000  294.457  ±  4.689  ns/op

ArrayList       SIZE    Score    Error  Units
Insert first     10   22.380  ±  0.266  ns/op
Insert first    100   26.929  ±  0.385  ns/op
Insert first   1000   78.958  ±  1.429  ns/op
Insert first  10000  717.892  ±  9.242  ns/op

ArrayList                  SIZE       Score    Error  Units
Adding in a full array      10      19.300 ±    2.953  ns/op
Adding in a full array     100      45.488 ±    3.922  ns/op
Adding in a full array    1000     432.351 ±   46.055  ns/op
Adding in a full array   10000    4140.668 ±  329.160  ns/op

ArrayList                        SIZE     Score    Error  Units
Insert middle in a full array     10    39.334 ±    1.588  ns/op
Insert middle in a full array    100    61.037 ±    2.130  ns/op
Insert middle in a full array   1000   451.471 ±   27.247  ns/op
Insert middle in a full array  10000  4638.632 ±  360.694  ns/op

ArrayList                       SIZE     Score     Error  Units
Insert first in a full array     10    28.288 ±    0.656  ns/op
Insert first in a full array    100    52.935 ±    2.457  ns/op
Insert first in a full array   1000   452.179 ±   37.434  ns/op
Insert first in a full array  10000  4762.783 ±  133.468  ns/op

var intsV1 = new ArrayList<Integer>();
intsV1.add(1); // wraps an array of size 10

var intsV2 = new ArrayList<Integer>();
intsV2.addAll(List.of(1)); // wraps an array of size 10

var intsV3 = new ArrayList<Integer>(List.of(1)); // wraps an array of size 1