Различия в производительности между ArrayList и LinkedList

Ответ 1

ArrayList быстрее, чем LinkedList, если я случайно получаю доступ к его элементам. Я думаю, что случайный доступ означает "дать мне n-й элемент". Почему ArrayList быстрее?

ArrayList имеет прямые ссылки на каждый элемент в списке, поэтому он может получить n-й элемент в постоянное время. LinkedList должен пересекать список с самого начала, чтобы перейти к n-му элементу.

LinkedList быстрее, чем ArrayList для удаления. Я понимаю это. ArrayList медленнее, так как внутренний резервный массив необходимо перераспределить.

ArrayList работает медленнее, потому что ему нужно скопировать часть массива, чтобы удалить освобожденный слот. Если удаление выполняется с помощью ListIterator.remove() API, LinkedList просто нужно манипулировать несколькими ссылками; если удаление выполняется по значению или по индексу, LinkedList сначала потенциально сканирует весь список, чтобы найти элемент (ы), который нужно удалить.

Если это означает переместить некоторые элементы назад, а затем поместить элемент в среднее пустое место, ArrayList должен быть медленнее.

Да, это то, что это значит. ArrayList действительно медленнее, чем LinkedList, потому что он должен освободить слот в середине массива. Это связано с перемещением некоторых ссылок вокруг и в худшем случае перераспределением всего массива. LinkedList просто нужно манипулировать некоторыми ссылками.

Ответ 2

Игнорируйте этот ответ. Другие ответы, в частности, aix, в основном верны. В долгосрочной перспективе они могут сделать ставку. И если у вас достаточно данных (по одному эталону на одной машине, похоже, около миллиона записей) ArrayList и LinkedList в настоящее время работают как рекламируемые. Однако есть некоторые тонкости, которые применяются в начале XXI века.

Современная компьютерная технология, по моим испытаниям, дает огромное преимущество массивам. Элементы массива могут быть сдвинуты и скопированы с безумной скоростью. В результате массивы и ArrayList будут в большинстве практических ситуаций превосходить LinkedList на вставках и удалении, часто резко. Другими словами, ArrayList будет бить LinkedList в своей собственной игре.

Недостаток ArrayList заключается в том, что он имеет тенденцию висеть на пространстве памяти после удаления, где LinkedList отбрасывает пространство, когда он выдает записи.

Чем больше обратная сторона массивов и ArrayList, тем они свободны от фрагментов и перегружают сборщик мусора. По мере расширения массива ArrayList он создает новые массивы большего размера, копирует старый массив в новый и освобождает старый. Память заполняется большими смежными кусками свободной памяти, которые недостаточно велики для следующего распределения. В конце концов нет подходящего места для этого распределения. Несмотря на то, что 90% памяти бесплатны, ни одна отдельная часть не является достаточно большой, чтобы выполнять эту работу. GC будет работать отчаянно, чтобы перемещать вещи, но если это займет слишком много времени, чтобы перестроить пространство, оно выкинет OutOfMemoryException. Если он не сдастся, он все равно может замедлить работу программы.

Хуже всего то, что эту проблему трудно предсказать. Ваша программа будет работать нормально один раз. Затем, с меньшим объемом памяти, без предупреждения, она замедляется или останавливается.

LinkedList использует небольшие, изящные бит памяти и GC любит его. Он по-прежнему работает нормально, когда вы используете 99% доступной памяти.

В общем случае, используйте ArrayList для меньших наборов данных, которые вряд ли удалят большую часть их содержимого, или когда у вас жесткий контроль над созданием и ростом. (Например, создание одного ArrayList, использующего 90% памяти, и использование его без его заполнения в течение продолжительности программы в порядке. Постоянное создание и освобождение экземпляров ArrayList, которые используют 10% памяти, убьет вас.) В противном случае перейдите к LinkedList (или какую-либо карту, если вам нужен произвольный доступ). Если у вас очень большие коллекции (например, более 100 000 элементов), нет проблем с GC, а также планировать множество вставок и удалений и нет произвольного доступа, запустите несколько эталонных тестов, чтобы узнать, что быстрее.

Ответ 3

Класс ArrayList - это класс-оболочка для массива. Он содержит внутренний массив.

public ArrayList<T> {
    private Object[] array;
    private int size;
}

A LinkedList - это класс-оболочка для связанного списка с внутренним node для управления данными.

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

Примечание. Настоящий код используется, чтобы показать, каким может быть класс, а не фактическая реализация. Зная, как это может быть реализовано, мы можем провести дальнейший анализ:

ArrayList быстрее, чем LinkedList, если я случайно получаю доступ к его элементам. Я думаю, что случайный доступ означает "дать мне n-й элемент". Почему ArrayList быстрее?

Время доступа для ArrayList: O (1). Время доступа для LinkedList: O (n).

В массиве вы можете получить доступ к любому элементу с помощью array[index], в то время как в связанном списке вы должны перемещаться по всему списку, начиная с first, пока не получите нужный элемент.

LinkedList быстрее, чем ArrayList для удаления. Я понимаю это. ArrayList медленнее, поскольку внутренний резервный массив необходимо перераспределить.

Время удаления для ArrayList: время доступа + O (n). Время удаления для LinkedList: время доступа + O (1).

ArrayList должен переместить все элементы из array[index] в array[index-1], начиная с элемента, чтобы удалить индекс. LinkedList должен перейти до этого элемента, а затем удалить этот node, отделив его от списка.

LinkedList быстрее, чем ArrayList для удаления. Я понимаю это. ArrayList медленнее, поскольку внутренний резервный массив необходимо перераспределить.

Время вставки для ArrayList: O (n). Время вставки для LinkedList: O (1).

Почему ArrayList может принимать O (n)? Потому что, когда вы вставляете новый элемент и массив заполнен, вам нужно создать новый массив с большим размером (вы можете рассчитать новый размер с формулой размером 2 * или 3 * размером /2). LinkedList просто добавляет новый node рядом с последним.

Этот анализ происходит не только на Java, но и на других языках программирования, таких как C, С++ и С#.

Подробнее здесь:

• http://en.wikipedia.org/wiki/Array_data_structure
• http://en.wikipedia.org/wiki/Linked_list

Ответ 4

Оба метода remove() и insert() имеют эффективность выполнения O (n) как для ArrayLists, так и для LinkedLists. Однако причина линейного времени обработки зависит от двух разных причин:

В ArrayList вы попадаете в элемент в O (1), но на самом деле удаление или вставка чего-то делает его O (n), потому что необходимо изменить все следующие элементы.

В LinkedList для фактического перехода к нужному элементу требуется O (n), потому что мы должны начинать с самого начала, пока не достигнем желаемого индекса. Удаление или вставка является постоянным, когда мы туда попадаем, потому что нам нужно изменить только 1 ссылку для remove() и 2 ссылки для insert().

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

Бонус: Хотя нет способа сделать эти два метода O (1) для ArrayList, на самом деле есть способ сделать это в LinkedLists. Допустим, мы хотим пройти весь список, удалив и вставив элементы на нашем пути. Обычно вы начинаете с самого начала для каждого элемента с помощью LinkedList, мы также можем "сохранить" текущий элемент, с которым мы работаем с Iterator. С помощью Iterator мы получаем эффективность O (1) для remove() и insert() при работе в LinkedList. Являясь единственным преимуществом производительности, я знаю, где LinkedList всегда лучше, чем ArrayList.

Ответ 5

Ответ на 1: ArrayList использует массив под капотом. Доступ к объекту объекта ArrayList так же просто, как обращение к массиву с предоставленным индексом, при условии, что индекс находится в пределах массива поддержки. LinkedList должен выполнить итерацию через своих членов, чтобы перейти к n-му элементу. Это O (n) для LinkedList, по сравнению с O (1) для ArrayList.

Ответ 6

В LinkedList элементы имеют ссылку на элемент до и после него. В ArrayList структура данных представляет собой всего лишь массив.

• LinkedList должен перебирать N элементов для получения элемента Nth. ArrayList должен только вернуть элемент N массива поддержки.

• Базовый массив должен либо перераспределяться для нового размера, либо массив, скопированный поверх каждого элемента, после удаления удаляемого элемента, чтобы заполнить пустое пространство. LinkedList просто должен установить предыдущую ссылку на элемент после удаления до того, как он был удален, и следующую ссылку на элемент перед удаленным элементом в элемент после удаляемого элемента. Дольше объяснять, но быстрее делать.

• По той же причине, что и удаление.

Ответ 7

ArrayList

• ArrayList - лучший выбор, если наша частая операция - операция поиска.
• ArrayList - худший выбор, если наша операция - вставка и удаление в середине, потому что внутренне выполняется несколько операций сдвига.
• В ArrayList элементы будут храниться в последовательных ячейках памяти, поэтому операция поиска станет легкой.

LinkedList: -

• LinkedList - лучший выбор, если нашей частой операцией является вставка и удаление в середине.
• LinkedList - худший выбор, наша частая операция - операция поиска.
• В LinkedList элементы не будут храниться в последовательной ячейке памяти, и, следовательно, операция поиска будет сложной.

Теперь перейдем к вашим вопросам:

1) ArrayList сохраняет данные в соответствии с индексами и реализует интерфейс RandomAccess, который представляет собой интерфейс маркера, который обеспечивает возможность случайного извлечения в ArrayList, но LinkedList не реализует интерфейс RandomAccess, поэтому ArrayList работает быстрее, чем LinkedList.

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

Ответ 8

ArrayList: ArrayList имеет структуру, подобную массиву, она имеет прямую ссылку на каждый элемент. Таким образом, доступ к Rendom быстро выполняется в ArrayList.

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

Ответ 9

ArrayList: Класс ArrayList расширяет AbstractList и реализует интерфейс List и RandomAccess (интерфейс маркера). ArrayList поддерживает динамические массивы, которые могут расти по мере необходимости. Он дает нам первую итерацию по элементам.

LinkedList: LinkedList упорядочивается по позиции индекса, например ArrayList, за исключением того, что элементы дважды связаны друг с другом. Эта привязка дает вам новые методы (помимо того, что вы получаете из интерфейса List) для добавления и удаления с самого начала или конца, что делает его легким выбором для реализации стека или очереди. Имейте в виду, что LinkedList может выполнять итерацию медленнее, чем ArrayList, , но это хороший выбор, когда вам нужна быстрая вставка и удаление.. С Java 5 класс LinkedList был расширен для реализации java. util.Queue. Таким образом, теперь он поддерживает общие методы очереди: peek(), poll() и offer().

Ответ 10

Я хочу добавить ей дополнительную информацию о разнице в производительности.

Мы уже знаем, что из-за того, что реализация ArrayList поддерживается Object[] она поддерживает произвольный доступ и динамическое изменение размера, а реализация LinkedList использует ссылки на head и tail для навигации по нему. У него нет возможности произвольного доступа, но он также поддерживает динамическое изменение размера.

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

Во-вторых, вставка в ArrayList обычно происходит медленнее, потому что она должна расти, как только вы достигнете ее границ. Он должен будет создать новый больший массив и скопировать данные из исходного.

Но интересно то, что когда вы создаете ArrayList, который уже достаточно велик, чтобы вместить все ваши вставки, он, очевидно, не будет включать никаких операций копирования массива. Добавление к нему будет даже быстрее, чем с LinkedList, потому что LinkedList будет иметь дело с его указателями, в то время как огромный ArrayList просто устанавливает значение по данному индексу.

Проверьте больше различий ArrayList и LinkedList.

Ответ 11

Даже они кажутся идентичными (тот же реализованный inteface List - non thread-safe), они дают разные результаты с точки зрения производительности в добавлении/удалении, времени поиска и потребляющей памяти (LinkedList потребляет больше).

LinkedLists могут использоваться, если вы используете высокую степень вставки/удаления с производительностью O (1). ArrayLists можно использовать, если вы используете операции прямого доступа с производительностью O (1)

Этот код может исключить эти комментарии, и вы можете попытаться понять результаты работы. (Извините за код плиты котла)

public class Test {

    private static Random rnd;


    static {
        rnd = new Random();
    }


    static List<String> testArrayList;
    static List<String> testLinkedList;
    public static final int COUNT_OBJ = 2000000;

    public static void main(String[] args) {
        testArrayList = new ArrayList<>();
        testLinkedList = new LinkedList<>();

        insertSomeDummyData(testLinkedList);
        insertSomeDummyData(testArrayList);

        checkInsertionPerformance(testLinkedList);  //O(1)
        checkInsertionPerformance(testArrayList);   //O(1) -> O(n)

        checkPerformanceForFinding(testArrayList);  // O(1)
        checkPerformanceForFinding(testLinkedList); // O(n)

    }


    public static void insertSomeDummyData(List<String> list) {
        for (int i = COUNT_OBJ; i-- > 0; ) {
            list.add(new String("" + i));
        }
    }

    public static void checkInsertionPerformance(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.add(rndIndex, "test");
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));
    }

    public static void checkPerformanceForFinding(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.get(rndIndex);
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));

    }

}