элементов - коллекции java




Когда использовать LinkedList над ArrayList в Java? (20)

1) Поиск: операция поиска ArrayList довольно быстро по сравнению с операцией поиска LinkedList. get (int index) в ArrayList дает производительность O (1), а производительность LinkedList - O (n).

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

2) Удаление: операция удаления LinkedList дает O (1) производительность, в то время как ArrayList дает переменную производительность: O (n) в худшем случае (при удалении первого элемента) и O (1) в лучшем случае (при удалении последнего элемента) ,

Вывод: удаление элемента LinkedList происходит быстрее по сравнению с ArrayList.

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

3) Вставка производительности: метод добавления LinkedList дает O (1) производительность, в то время как ArrayList дает O (n) в худшем случае. Причина та же, что и для удаления.

4) Накладные расходы памяти: ArrayList поддерживает индексы и данные элемента, а LinkedList поддерживает данные элемента и два указателя для соседних узлов, следовательно, потребление памяти в LinkedList сравнительно велико.

Существует несколько сходств между этими классами, которые заключаются в следующем:

И ArrayList, и LinkedList - это реализация интерфейса List. Они оба поддерживают порядок вставки элементов, что означает, что при отображении элементов ArrayList и LinkedList набор результатов будет иметь тот же порядок, в котором элементы были вставлены в список. Оба эти класса не синхронизированы и могут быть синхронизированы явно с помощью метода Collections.synchronizedList. Итератор и listIterator, возвращаемые этими классами, являются неустойчивыми (если список структурно изменен в любое время после создания итератора, любым способом, кроме как через собственные методы удаления или добавления итератора, итератор будет вызывать исключение ConcurrentModificationException).

Когда использовать LinkedList и когда использовать ArrayList?

1) Как объяснялось выше, операции вставки и удаления дают хорошую производительность (O (1)) в LinkedList по сравнению с ArrayList (O (n)). Следовательно, если в приложении есть требование частого добавления и удаления, тогда LinkedList является лучшим выбором.

2) Операции поиска (get method) бывают быстрыми в ArrayList (O (1)), но не в LinkedList (O (n)), поэтому, если есть меньше операций добавления и удаления и большего количества операций поиска, ArrayList будет вашим лучшим выбором.

Я всегда был один, чтобы просто использовать:

List<String> names = new ArrayList<>();

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

Когда следует использовать LinkedList над ArrayList и наоборот?


Да, я знаю, это древний вопрос, но я брошу свои два цента:

LinkedList почти всегда является неправильным выбором, с точки зрения производительности. Существуют некоторые очень специфические алгоритмы, для которых требуется ссылка LinkedList, но они очень и очень редки, и алгоритм обычно зависит от способности LinkedList вставлять и удалять элементы в середине списка относительно быстро, как только вы переходите туда с ListIterator.

Существует один распространенный случай использования, при котором LinkedList превосходит ArrayList: очередь. Однако, если ваша цель - производительность, вместо LinkedList вы также должны рассмотреть возможность использования ArrayBlockingQueue (если вы можете заранее определить верхнюю границу вашего размера очереди и можете позволить себе выделить всю память вверх) или эту реализацию CircularArrayList , (Да, это с 2001 года, поэтому вам нужно будет его генерировать, но у меня есть сопоставимые коэффициенты производительности с тем, что цитируется в статье только в недавней JVM)


Правильно или неверно: Пожалуйста, выполните тест на месте и решите сами!

Изменить / Удалить быстрее в LinkedList чем в ArrayList .

ArrayList , поддерживаемый Array , который должен быть в два раза больше, хуже в приложении большого объема.

Ниже приведен единичный результат теста для каждой операции. Цитирование дано в наносекундах.

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Вот код:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

Это вопрос эффективности. LinkedList быстро добавляет и удаляет элементы, но медленный доступ к определенному элементу. ArrayList быстро получает доступ к определенному элементу, но может быть медленным добавлением в любой конец и особенно медленным для удаления в середине.

Array vs ArrayList vs LinkedList vs Vector идет более подробно, как и Linked List .


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

Почему LinkedList отстой:

  • Он использует множество небольших объектов памяти и, следовательно, влияет на производительность во всем процессе.
  • Множество мелких объектов плохо для локализации кеша.
  • Любая индексированная операция требует обхода, т. Е. Имеет O (n) производительность. Это не очевидно в исходном коде, что приводит к тому, что алгоритмы O (n) медленнее, чем при использовании ArrayList .
  • Получение хорошей производительности сложно.
  • Даже когда производительность большого вывода совпадает с ArrayList , она, вероятно, будет значительно медленнее.
  • Это раздражает, чтобы увидеть LinkedList в источнике, потому что это, вероятно, неправильный выбор.

ArrayList по существу является массивом. LinkedList реализуется как двойной связанный список.

get довольно ясно. O (1) для ArrayList , поскольку ArrayList допускает произвольный доступ с использованием индекса. O (n) для LinkedList , потому что он должен сначала найти индекс. Примечание. Существуют разные версии add и remove .

LinkedList быстрее добавляет и удаляет, но медленнее получается. Вкратце, LinkedList должен быть предпочтительнее, если:

  1. нет большого количества случайного доступа элемента
  2. существует большое количество операций добавления / удаления

=== ArrayList ===

  • add (E e)
    • добавить в конец ArrayList
    • требуют изменения размера памяти.
    • O (n) хуже, O (1) амортизируется
  • add (индекс int, элемент E)
    • добавить к определенной позиции индекса
    • требуют смещения и возможной стоимости изменения размера памяти
    • На)
  • remove (int index)
    • удалить указанный элемент
    • требуют смещения и возможной стоимости изменения размера памяти
    • На)
  • remove (Object o)
    • удалить первое вхождение указанного элемента из этого списка
    • необходимо сначала выполнить поиск по элементу, а затем сдвинуть и возможную стоимость изменения размера памяти
    • На)

=== LinkedList ===

  • add (E e)

    • добавить в конец списка
    • O (1)
  • add (индекс int, элемент E)

    • вставить в указанное положение
    • нужно сначала найти позицию
    • На)
  • Удалить()
    • удалить первый элемент списка
    • O (1)
  • remove (int index)
    • удалить элемент с указанным индексом
    • нужно сначала найти элемент
    • На)
  • remove (Object o)
    • удалить первое вхождение указанного элемента
    • нужно сначала найти элемент
    • На)

Вот цифра от programcreek.com ( add и remove - это первый тип, т. Е. Добавление элемента в конце списка и удаление элемента в указанной позиции в списке.):


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

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


1) Базовая структура данных

Первое различие между ArrayList и LinkedList связано с тем, что ArrayList поддерживается Array, а LinkedList поддерживается LinkedList. Это приведет к дальнейшим различиям в производительности.

2) LinkedList реализует Deque

Другое отличие между ArrayList и LinkedList заключается в том, что помимо интерфейса List LinkedList также реализует интерфейс Deque, который обеспечивает первую в первых операциях функции add () и poll () и несколько других функций Deque. 3) Добавление элементов в ArrayList. Добавление элемента в ArrayList - это операция O (1), если она не вызывает повторный размер массива, в этом случае она становится O (log (n)). С другой стороны, добавление элемента в LinkedList - это операция O (1), так как она не требует навигации.

4) Удаление элемента из положения

Чтобы удалить элемент из определенного индекса, например, вызвав remove (index), ArrayList выполняет операцию копирования, которая делает ее близкой к O (n), в то время как LinkedList должен пройти к этой точке, что также делает ее O (n / 2) , так как он может проходить с любого направления, основанного на близости.

5) Итерация по ArrayList или LinkedList

Итерация - это операция O (n) для LinkedList и ArrayList, где n - число элементов.

6) Извлечение элемента из положения

Операция get (index) - это O (1) в ArrayList, а O (n / 2) в LinkedList, поскольку она должна проходить до этой записи. Хотя в записи Big O O (n / 2) есть только O (n), потому что мы игнорируем там константы.

7) Память

LinkedList использует объект-оболочку, Entry, который является статическим вложенным классом для хранения данных и двух узлов next и previous, в то время как ArrayList просто хранит данные в массиве.

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

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

Из всех вышеперечисленных различий между ArrayList и LinkedList, похоже, что ArrayList является лучшим выбором, чем LinkedList почти во всех случаях, за исключением случаев, когда вы выполняете частое действие add (), чем remove () или get ().

Изменить связанный список проще, чем ArrayList, особенно если вы добавляете или удаляете элементы из начала или конца, потому что связанный список внутренне сохраняет ссылки этих позиций, и они доступны в O (1) раз.

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

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


Резюме ArrayList с ArrayDeque предпочтительнее в гораздо большем количестве случаев использования, чем LinkedList . Если вы не уверены - начните с ArrayList .

LinkedList и ArrayList - это две разные реализации интерфейса List. LinkedList реализует его с дважды связанным списком. ArrayList реализует его с помощью динамически изменяющегося массива.

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

Для LinkedList<E>

  • get(int index) - O (n) (с средним значением n / 4 )
  • add(E element) - O (1)
  • add(int index, E element) - O (n) (с средним значением n / 4 ), но O (1), когда index = 0 <--- главное преимущество LinkedList<E>
  • remove(int index) - O (n) (при среднем числе n / 4 )
  • Iterator.remove() - O (1) . <--- главное преимущество LinkedList<E>
  • ListIterator.add(E element) - это O (1) Это одно из основных преимуществ LinkedList<E>

Примечание: для выполнения многих операций требуется в среднем n / 4 шага в среднем, постоянное количество шагов (например, индекс = 0) и n / 2 шага в худшем случае (в середине списка)

Для ArrayList<E>

  • get(int index) - O (1) <--- главное преимущество ArrayList<E>
  • add(E element) является O (1) амортизированным, но O (n) наихудшим, так как массив должен быть изменен и скопирован
  • add(int index, E element) - это O (n)n / 2 шагами в среднем)
  • remove(int index) - это O (n) (с в среднем n / 2 шага)
  • Iterator.remove() - O (n)n / 2 шагами в среднем)
  • ListIterator.add(E element) - это O (n) (при среднем числе n / 2 шага)

Примечание: для многих операций требуется среднее число шагов в среднем, постоянное количество шагов в лучшем случае (конец списка), n шагов в худшем случае (начало списка)

LinkedList<E> позволяет устанавливать или удалять постоянное время с использованием итераторов , но только последовательный доступ к элементам. Другими словами, вы можете перемещать список вперед или назад, но поиск позиции в списке занимает время, пропорциональное размеру списка. Javadoc говорит: «Операции, которые индексируют в список, будут пересекать список с начала или конца, в зависимости от того, что ближе» , поэтому эти методы в среднем равны O (n) ( n / 4 шага), хотя O (1) для index = 0 .

ArrayList<E> , с другой стороны, допускает быстрый случайный доступ к чтению, поэтому вы можете захватывать любой элемент в постоянное время. Но добавление или удаление из любого места, кроме конца, требует смещения всех последних элементов, чтобы сделать открытие или заполнить пробел. Кроме того, если вы добавляете больше элементов, чем емкость базового массива, выделяется новый массив (в 1,5 раза больше размера), а старый массив копируется в новый, поэтому добавление в ArrayList - это O (n) в наихудший случай, но постоянный в среднем.

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

Основные преимущества использования LinkedList возникают при повторном использовании существующих итераторов для вставки и удаления элементов. Затем эти операции можно выполнить в O (1) путем изменения только локального списка. В списке массивов остальная часть массива должна быть перемещена (т.е. скопирована). С другой стороны, поиск в LinkedList означает следующие ссылки в O (n) ( n / 2 шага) для наихудшего случая, тогда как в ArrayList желаемая позиция может быть математически вычислена и доступна в O (1) .

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

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

Начальная емкость ArrayList умолчанию довольно маленькая (10 из Java 1.4 - 1.8). Но поскольку базовая реализация представляет собой массив, массив должен быть изменен, если вы добавите много элементов. Чтобы избежать высокой стоимости изменения размера, когда вы знаете, что собираетесь добавить много элементов, ArrayList с более высокой начальной емкостью.


Давайте сравним LinkedList и ArrayList по параметрам:

1. Реализация

ArrayList - это переменная реализация массива списка, в то время как

LinkedList - это реализация списка ссылок с двойным соединением.

2. Производительность

  • get (индекс int) или операция поиска

    Операция getArrayList get (int index) выполняется в постоянное время, то есть O (1) while

    Время выполнения операции LinkedList get (int index) равно O (n).

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

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

  • insert () или добавить (Object)

    Вставки в LinkedList обычно бывают быстрыми, как сравнение с ArrayList. В добавлении или вставке LinkedList выполняется операция O (1).

    В то время как в ArrayList , если массив является полным, т.е. наихудшим случаем, существует дополнительная стоимость изменения размера массива и копирования элементов в новый массив, что делает время выполнения операции добавления в ArrayList O (n), в противном случае O (1) ,

  • remove (int)

    Удалить операцию в LinkedList, как правило, совпадает с ArrayList, то есть O (n).

    В LinkedList существует два перегруженных метода удаления. один - remove () без какого-либо параметра, который удаляет головку списка и запускается в постоянное время O (1). Другим перегруженным методом удаления в LinkedList является remove (int) или remove (Object), который удаляет Object или int, переданные в качестве параметра. Этот метод пересекает LinkedList, пока не найдет объект и не отделит его от исходного списка. Следовательно, это время выполнения метода O (n).

    Хотя метод ArrayList remove (int) включает в себя копирование элементов из старого массива в новый обновленный массив, отсюда его время выполнения - O (n).

3. Обратный итератор

LinkedList можно повторить в обратном направлении, используя descendingIterator (), в то время как

в ArrayList отсутствует descendingIterator () , поэтому нам нужно написать собственный код для повторения по ArrayList в обратном направлении.

4. Начальная мощность

Если конструктор не перегружен, то ArrayList создает пустой список начальной емкости 10, тогда как

LinkedList только создает пустой список без какой-либо начальной емкости.

5. Накладные расходы памяти

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

В ArrayList каждый индекс содержит только фактический объект (данные).

Source


У ArrayList и LinkedList есть свои плюсы и минусы.

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

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

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


Это зависит от того, какие операции вы будете делать больше в Списке.

ArrayListбыстрее получить доступ к индексированному значению. Это намного хуже при вставке или удалении объектов.

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


ArrayList расширяет AbstractList и реализует интерфейс List. ArrayList - это динамический массив.
Можно сказать, что он был создан в основном для преодоления недостатков массивов.

Класс LinkedList расширяет AbstractSequentialList и реализует интерфейс List, Deque и Queue.
Спектакль
arraylist.get()O (1), тогда linkedlist.get()как O (n)
arraylist.add()является O (1) и linkedlist.add()0 (1)
arraylist.contains()является O (n) и linkedlist.contains()O (n)
arraylist.next()является O (1) и linkedlist.next()O (1)
arraylist.remove()является O (n), тогда как linkedlist.remove()O (1)
В arraylist
iterator.remove()есть O (n),
тогда как в связанном списке
iterator.remove()O (1)


В дополнение к другим хорошим аргументам, приведенным выше, вы должны заметить интерфейс ArrayListреализации RandomAccess, в то время как LinkedListреализует Queue.

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


Вот запись Big-O в обоих ArrayListи , LinkedListа также CopyOnWrite-ArrayList:

ArrayList

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Исходя из этого, вы должны решить, что выбрать. :)


Если у вашего кода есть add(0)и remove(0), используйте его LinkedListи его красивее addFirst()и removeFirst()методы. В противном случае используйте ArrayList.

И, конечно же , Guava «s ImmutableList ваш лучший друг.


Один из тестов, которые я видел здесь, проводит только один раз. Но я заметил, что вам нужно много раз запускать эти тесты, и в конечном итоге их время будет сходиться. В принципе, JVM нужно прогревать. Для моего конкретного случая использования мне нужно было добавлять / удалять элементы до последнего, которые вырастают примерно до 500 элементов. В моих тестах LinkedListвышло быстрее, с привязанными LinkedListоколо 50 000 NS и ArrayListприходящими в около 90 000 NS ... дайте или возьмите. См. Код ниже.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

Операция get (i) в ArrayList быстрее, чем LinkedList, потому что:
ArrayList: реализация интерфейса Resizable-array интерфейса List
LinkedList: реализация с двойным соединением интерфейсов List и Deque

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


Список массивов по существу представляет собой массив с методами для добавления элементов и т. Д. (И вместо этого вы должны использовать общий список). Это набор элементов, к которым можно получить доступ с помощью индексатора (например, [0]). Это подразумевает переход от одного пункта к другому.

Связанный список указывает переход от одного элемента к другому (элемент a -> элемент b). Вы можете получить тот же эффект с помощью списка массивов, но связанный список абсолютно говорит, какой элемент должен следовать предыдущему.


Я знаю , что это старый пост, но я честно не могу поверить , что никто не упомянул , что LinkedListорудия Deque. Просто взгляните на методы в DequeQueue); если вы хотите , справедливое сравнение, попробуйте запустить LinkedListпротив ArrayDequeи сделать функционально для-функции сравнения.





linked-list