Когда использовать LinkedList поверх ArrayList в Java? - PullRequest
Новая
       231

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

2841 голосов
/ 27 ноября 2008

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

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

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

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

Ответы [ 31 ]

7 голосов
/ 27 ноября 2008

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

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

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

7 голосов
/ 14 января 2019

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

|---------------------|---------------------|--------------------|------------|
|      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    |
|--------------------------------------|
6 голосов
/ 04 октября 2011

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

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

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

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

5 голосов
/ 15 мая 2017

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

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

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

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

5 голосов
/ 25 апреля 2013

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

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

5 голосов
/ 02 ноября 2016

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

ArrayList против LinkedList

1) Search: ArrayList Операция поиска довольно быстрая по сравнению с LinkedList операцией поиска. get(int index) in 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 метод add дает производительность 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 a ConcurrentModificationException).

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

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

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

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

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

4 голосов
/ 07 июня 2018

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.

1 голос
/ 11 июня 2016

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

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

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

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

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

0 голосов
/ 04 августа 2018

Один из тестов, которые я видел здесь, проводит тест только один раз. Но я заметил, что вам нужно запускать эти тесты много раз, и в конечном итоге их время будет сходиться. По сути, 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;
}
0 голосов
/ 21 февраля 2018

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

Класс LinkedList расширяет AbstractSequentialList и реализует интерфейсы List, Deque и Queue.
Performance
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)
В массиве
iterator.remove() обозначает O (n)
, тогда как в связном списке
iterator.remove() обозначает O (1)

Страница:
...