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 все элементы располагаются в одном нефрагментированном участке памяти, ибо по сути это всего лишь динамически расширяемый массив!
И что делать прикажете? Теория говорит одно! Практика другое!