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

StackOverflow https://stackoverflow.com/questions/322715

Вопрос

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

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

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

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

Это было полезно?

Решение

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

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

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

Для LinkedList<E>

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

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

Для ArrayList<E>

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

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

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

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

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

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

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

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

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

Другие советы

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

Поскольку ссылки имеют размер 32 или 64 бита (даже если они равны нулю) в соответствующих системах, я включил 4 набора данных для 32 и 64 бит. LinkedLists и ArrayLists.

Примечание: Размеры указаны для ArrayList линии предназначены для обрезанные списки - На практике емкость резервного массива в ArrayList обычно больше, чем текущее количество элементов.

Заметка 2: (спасибо BeeOnRope) Поскольку CompressedOops теперь используется по умолчанию начиная с середины JDK6 и выше, приведенные ниже значения для 64-битных машин будут в основном соответствовать их 32-битным аналогам, если, конечно, вы специально не отключите его.

Graph of LinkedList and ArrayList No. of Elements x Bytes

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

Формулы, которые я использовал, приведены ниже. Если я сделал что-то не так, дайте мне знать, и я это исправлю.«b» — это 4 или 8 для 32- или 64-битных систем, а «n» — количество элементов.Обратите внимание, что причина использования модов заключается в том, что все объекты в Java будут занимать пространство, кратное 8 байтам, независимо от того, используются они все или нет.

Список массивов:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

Связанный список:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

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

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

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

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

Точно так же вы можете получить лучшую пропускную способность в приложении из стандартного сборщика мусора с пропускной способностью по умолчанию, но как только вы получите java-приложения с кучей 10 ГБ, вы можете заблокировать приложение на 25 секунд во время полного GC, что приводит к тайм-аутам и сбоям в приложениях SOA и разрывает ваши SLA, если это происходит слишком часто. Несмотря на то, что сборщик CMS потребляет больше ресурсов и не достигает той же исходной пропускной способности, это гораздо лучший выбор, поскольку он имеет более предсказуемую и меньшую задержку.

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

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Алгоритмы: примечание Big-Oh

ArrayLists хороши для записи один раз для чтения или добавления, но плохо для добавления / удаления спереди или посередине.

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

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

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

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

Array vs ArrayList vs LinkedList vs Vector - это более глубокий анализ, как и Связанный список .

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

Редактировать / удалить быстрее в 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);
    }
}

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

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

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

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

=== ArrayList ===

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

=== Связанный список ===

  • добавить (Е е)

    • добавить в конец списка
    • О(1)

  • add(int index, элемент E)

    • вставить в указанное место
    • сначала нужно найти позицию
    • На)
  • удалять()
    • удалить первый элемент списка
    • О(1)
  • удалить (целевой индекс)
    • удалить элемент с указанным индексом
    • нужно сначала найти элемент
    • На)
  • удалить (Объект о)
    • удалить первое вхождение указанного элемента
    • нужно сначала найти элемент
    • На)

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

enter image description here

Джошуа Блох, автор LinkedList:

  

Кто-нибудь на самом деле использует LinkedList? Я написал это, и я никогда не использую это.

Ссылка: https://twitter.com/joshbloch/status/583813919019573248

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

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

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

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

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

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

Вот обозначение 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)

Связанный список

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)

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

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

<Ч>

Теоретически, LinkedList имеет O (1) для add (E element)

Добавление элемента в середине списка также должно быть очень эффективным.

Практика сильно отличается, так как LinkedList является структурой данных Cache Hostile . От производительности POV - очень мало случаев, когда LinkedList мог бы работать лучше, чем Cache-friendly ArrayList .

Вот результаты тестового тестирования вставки элементов в случайных местах. Как вы можете видеть - список массивов, если он гораздо эффективнее, хотя теоретически каждая вставка в середине списка потребует «переместить». n более поздние элементы массива (чем меньше значения, тем лучше):

введите описание изображения здесь

Работа на оборудовании более позднего поколения (большие, более эффективные кэши) - результаты еще более убедительны:

введите описание изображения здесь

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

Для этого есть две основные причины:

<Ол>

  • В основном - что узлы LinkedList случайно разбросаны по памяти. ОЗУ («Оперативное запоминающее устройство») на самом деле не является случайным, и блоки памяти должны быть извлечены для кэширования. Эта операция занимает много времени, и когда такие выборки происходят часто - страницы памяти в кэше необходимо постоянно заменять - > Кеш пропускает - > Кэш не эффективен. Элементы ArrayList хранятся в непрерывной памяти - именно для этого оптимизируется современная архитектура ЦП.

  • Вторичный LinkedList , необходимый для удержания указателей назад / вперед, что означает трехкратное потребление памяти на каждое сохраненное значение по сравнению с ArrayList .

    • DynamicIntArray , кстати, является пользовательской реализацией ArrayList, содержащей Int (тип примитива), а не Objects - следовательно, все данные действительно хранятся смежно - следовательно, еще более эффективно.

    Ключевым элементом, который следует помнить, является то, что стоимость выборки блока памяти является более значительной, чем стоимость доступа к одной ячейке памяти. Вот почему считыватель 1 МБ последовательной памяти работает в х400 раз быстрее, чем считывает этот объем данных из разных блоков памяти: 

    Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

    Источник: Номера задержек, которые должен знать каждый программист

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

    введите описание изображения здесь

    Примечание: это тест C ++ Std lib, но мой предыдущий опыт показал, что результаты C ++ и Java очень похожи. Исходный код

    Давайте сравним LinkedList и ArrayList с.р.т.ниже параметры:

    1.Выполнение

    ArrayList — это реализация интерфейса списка с изменяемым размером массива, а

    Связанный список — это реализация интерфейса списка в виде двусвязного списка.

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

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

      ArrayList Операция get(int index) выполняется за постоянное время, т.е. O(1), в то время как

      Связанный список Время выполнения операции get(int index) равно O(n) .

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

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

    • операция вставки() или добавления(Объект)

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

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

    • операция удаления (int)

      Операция удаления в LinkedList обычно аналогична ArrayList, т.е.На).

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

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

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

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

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

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

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

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

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

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

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

    Источник

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

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

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

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

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

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

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

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

    |---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

    Важной особенностью связанного списка (который я не прочитал в другом ответе) является объединение двух списков. Для массива это O (n) (+ накладные расходы на некоторые перераспределения), для связанного списка это только O (1) или O (2); -)

    Важно : для Java это LinkedList , это не так! См. Существует ли быстрый метод concat для связанного списка в Java?

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

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

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

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

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

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

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

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

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

    ArrayList против LinkedList

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

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

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

    Заключение:Удаление элемента LinkedList более быстро по сравнению с ArrayList.

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

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

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

    следовательно, потребление памяти в LinkedList сравнительно велико.

    Между этими классами есть несколько сходств, а именно:

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

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

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

      Следовательно, если в приложении требуется частое добавление и удаление, LinkedList — лучший выбор.

    • Поиск (get method) операции выполняются быстро в Arraylist (O(1)) но не в LinkedList (O(n))

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

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

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

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

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

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

    Еще одно различие между ArrayList и LinkedList состоит в том, что помимо интерфейса List, LinkedList также реализует интерфейс Deque, который предоставляет операции first-first-out для 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, который является статическим вложенным классом для хранения данных и двух узлов следующего и предыдущего, тогда как ArrayList просто хранит данные в массиве.

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

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

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

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

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

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

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

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

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

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

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

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

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

    iterator.remove () - O (n)
    , тогда как В связном списке
    iterator.remove () - O (1)

    Один из тестов, которые я видел здесь, проводит тест только один раз. Но я заметил, что вам нужно запускать эти тесты много раз, и в конечном итоге их время будет сходиться. По сути, JVM необходимо разогреть. Для моего конкретного случая использования мне нужно было добавить / удалить элементы до последней, которая увеличивается примерно до 500 элементов. В моих тестах LinkedList выходил быстрее, со связным LinkedList , входящим примерно в 50000 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;
}
    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top