Вопрос: Когда использовать LinkedList над ArrayList?


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

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

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

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


2535


источник


Ответы:


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


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

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

Для LinkedList<E>

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

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

Для ArrayList<E>

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

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

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

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

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

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

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

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

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


2813



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

Поскольку ссылки являются либо 32, либо 64 битами (даже когда null) в их относительных системах, я включил 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:

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:

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)

530



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

Зачем LinkedListотстой:

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

187



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

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

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


124



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 Notation

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


110



Yeah, I know, this is an ancient question, but I'll throw in my two cents:

LinkedList is almost always the wrong choice, performance-wise. There are some very specific algorithms where a LinkedList is called for, but those are very, very rare and the algorithm will usually specifically depend on LinkedList's ability to insert and delete elements in the middle of the list relatively quickly, once you've navigated there with a ListIterator.

There is one common use case in which LinkedList outperforms ArrayList: that of a queue. However, if your goal is performance, instead of LinkedList you should also consider using an ArrayBlockingQueue (if you can determine an upper bound on your queue size ahead of time, and can afford to allocate all the memory up front), or this CircularArrayList implementation. (Yes, it's from 2001, so you'll need to generify it, but I got comparable performance ratios to what's quoted in the article just now in a recent JVM)


91



It's an efficiency question. LinkedList is fast for adding and deleting elements, but slow to access a specific element. ArrayList is fast for accessing a specific element but can be slow to add to either end, and especially slow to delete in the middle.

Array vs ArrayList vs LinkedList vs Vector goes more in depth, as does Linked List.


50



Correct or Incorrect: Please execute test locally and decide for yourself!

Edit/Remove is faster in LinkedList than ArrayList.

ArrayList, backed by Array, which needs to be double the size, is worse in large volume application.

Below is the unit test result for each operation.Timing is given in Nanoseconds.


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

Here's the code:

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);
    }
}

48



ArrayList is essentially an array. LinkedList is implemented as a double linked list.

The get is pretty clear. O(1) for ArrayList, because ArrayList allow random access by using index. O(n) for LinkedList, because it needs to find the index first. Note: there are different versions of add and remove.

LinkedList is faster in add and remove, but slower in get. In brief, LinkedList should be preferred if:

  1. there are no large number of random access of element
  2. there are a large number of add/remove operations

=== ArrayList ===

  • add(E e)
    • add at the end of ArrayList
    • require memory resizing cost.
    • O(n) worst, O(1) amortized
  • add(int index, E element)
    • add to a specific index position
    • require shifting & possible memory resizing cost
    • O(n)
  • remove(int index)
    • remove a specified element
    • require shifting & possible memory resizing cost
    • O(n)
  • remove(Object o)
    • remove the first occurrence of the specified element from this list
    • need to search the element first, and then shifting & possible memory resizing cost
    • O(n)

=== LinkedList ===

  • add(E e)

    • add to the end of the list
    • O(1)
  • add(int index, E element)

    • insert at specified position
    • need to find the position first
    • O(n)
  • remove()
    • remove first element of the list
    • O(1)
  • remove(int index)
    • remove element with specified index
    • need to find the element first
    • O(n)
  • remove(Object o)
    • remove the first occurrence of the specified element
    • need to find the element first
    • O(n)

Here is a figure from programcreek.com (add and remove are the first type, i.e., add an element at the end of the list and remove the element at the specified position in the list.):

enter image description here


36