ArrayList VS LinkedList

Везде говорится про преимущество LinkedList в сравнении с ArrayList, относительно вставки элементов в середину. Однако, тестами такого результата я получить не могу!

Дано...
В обе коллекции добавлено 10_000_000 элементов. При попытке вставить новый элемент по индексу 600_000, ArrayList уже начинает выигрывать в скорости. И чем дальше я сдвигаю индекс к концу, тем разрыв во времени исполнения становится более ощутимым.

Может я неверно тестирую?

import java.util.*;

public class ArrayListVSLinkedList {
    private final static int SIZE   = 10_000_000;
    private final static int INSERT = 600_000;

    public static void main(String[] args) {
        List<Integer> arrayList  = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        new Thread(() -> {
            initList(arrayList);
            insertInMiddle(arrayList);
        }).start();

        new Thread(() -> {
            initList(linkedList);
            insertInMiddle(linkedList);
        }).start();
    }

    private static void initList(List list) {
        for (int i = 0; i < SIZE; i++) {
            list.add(i);
        }
    }

    private static void insertInMiddle(List list) {
        long start = System.currentTimeMillis();
        list.add(INSERT, 1203);
        long result = System.currentTimeMillis() - start;
        System.out.println(list.getClass() + "\nTime: " +  result + "\n");
    }
}

В теории все логично - для ArrayList приходится сдвигать все элементы справа от индекса вставки на одну позицию, а для LinkedList нужно только позаботится о ссылках на вновь вставленный элемент (в узлах, между которыми будет происходить вставка).

Однако, ведь в LinkedList у узлов нет никаких индексов? Я делаю такой вывод исходя из метода, который участвует в работе метода add(int index, E element)....

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

Ни о чем вам не говорит? Ну хорошо! Глянем другое! Вот сам метод добавления по индексу....

 public void add(int index, E element) {
     checkPositionIndex(index);

     if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
    }

Нас интересует linkBefore(element, node(index)). В частности динамическое получение второго аргумента метода!
Вот здесь то собака и зарыта...

Node<E> node(int index) {                             
    // assert isElementIndex(index);                  

    if (index < (size >> 1)) {                        
        Node<E> x = first;                            
        for (int i = 0; i < index; i++)               
            x = x.next;                               
        return x;                                     
    } else {                                          
        Node<E> x = last;                             
        for (int i = size - 1; i > index; i--)        
            x = x.prev;                               
        return x;                                     
    }                                                 
}                                                     

То есть элемент по индексу мы получаем путем прямого перебора узлов - либо от начала, либо с конца.

Ну окей..... Вроде бы пролистать 600_000 элементов это вам не сдивнуть вправо 9_400_000. Но компьютер упорно намекает на то, что быстрее сдивнуть.

Быть может дело в расположении элементов в памяти. У связного списка они разбросаны как попало, а у ArrayList все элементы располагаются в одном нефрагментированном участке памяти, ибо по сути это всего лишь динамически расширяемый массив!

И что делать прикажете? Теория говорит одно! Практика другое!