Сравнение ArrayList и LinkedList

#java #коллекции #arraylist #linked_list

Решил сравнить быстродействие. Написал простой пример:

public class ServiceList {
    public void addList(List list, String name){
        Date start = new Date();
        for (int i = 0; i < 4000000; i++) {
            list.add(new String());
        }
        Date finish = new Date();


        long time = finish.getTime() - start.getTime();
        //sum = sum + time;

        System.out.println("ADD "+ name + " : " + time);
    }
}


public class Main {
        public static void main(String[] args) {
            for(int i = 0; i < 10; i++) {
                new ServiceList().addList(new ArrayList(), "ArrayList");
                new ServiceList().addList(new LinkedList(), "LinkedList"); 
                System.out.println("- - - - - - - - -");

            }
        }
    }


Результаты просто удивляют:

ADD ArrayList : 1218
ADD LinkedList : 2673
- - - - - - - - -
ADD ArrayList : 156
ADD LinkedList : 187
- - - - - - - - -
ADD ArrayList : 141
ADD LinkedList : 125
- - - - - - - - -
ADD ArrayList : 141
ADD LinkedList : 297
- - - - - - - - -
ADD ArrayList : 31
ADD LinkedList : 656
- - - - - - - - -
ADD ArrayList : 188
ADD LinkedList : 32
- - - - - - - - -
ADD ArrayList : 223
ADD LinkedList : 422
- - - - - - - - -
ADD ArrayList : 31
ADD LinkedList : 1001
- - - - - - - - -
ADD ArrayList : 312
ADD LinkedList : 391
- - - - - - - - -
ADD ArrayList : 31
ADD LinkedList : 1141
- - - - - - - - -


Почему они такие разные? А порой даже linked быстрее?
    

Ответы

Ответ 1

Нет смысла сравнивать эти структуры, если нет контекста их применения. Вставки только
в конец? Удаления будут? Доступ нужен к каким элементам?


У вас вставка всегда в конец. Там сложность O(1) для обеих реализаций. Вот только
у ArrayList ресайз происходит, если он полностью забит. А стартовый размер, если память
не изменяет, равен 10. То есть, уже после десятой вставки там будет ресайз.
По поводу вставки. LinkedList выигрывает, когда вставки осуществляются в середину
списка. Особенно, если вы переиспользуете итератор, тогда вставка/удаление может выполняться
за O(1).
Обращение к элементу в ArrayList всегда за O(1). В LinkedList в худшем случае O(n).
Мне почему-то кажется, что вы там больше замеряете не работу с коллекциями, а время
на создание строк. А если там в промежутках stop the world у GC будет, то вообще не
релевантный тест тогда.
У вас тесты без прогрева. По-хорошему, до тестов нужно прогреть jvm.
Использовать Date для замеров времени - ужас. Используйте System.nanoTime() или хотя
бы System.currentTimeMillis().


К чему это я? Ну да, вы получили какие-то метрики, но на них не сделать никаких выводов,
пока не ясен контекст использования этих структур.