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

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

Массив против ArrayList против LinkedList против вектора идет более подробно, как и Связанный список.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 хороши для однократной записи и многократного чтения или добавлений, но плохи при добавлении / удалении спереди или посередине.

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

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

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

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

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

См. Учебники по Java - Список реализаций.

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

Редактирование / удаление выполняется быстрее в 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, которым я хочу поделиться, чтобы услышать мнения:

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

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

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

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

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

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

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

Результат ясно показывает, что 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)

Когда мне следует использовать LinkedList? При работе в основном со стеками или при работе с буферами. Когда мне следует использовать ArrayList? Только при работе с индексами, иначе вы можете использовать HashTable со связанным списком, тогда вы получите:

Хеш-таблица + связанный список

• Доступ по ключу О (1),
• Вставить ключом О (1),
• Снимаем ключом О (1)
• и есть трюк для реализации RemoveAll / SetAll с O (1) при использовании управления версиями

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

Также посмотрите Красно-Черное дерево

• Произвольный доступ Журнал (n),
• Вставить Журнал (n),
• Удалить Журнал (n)

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

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

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

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

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

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

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

=== ArrayList ===

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

=== LinkedList ===

• добавить (E e)

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

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

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

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

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

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

И 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, мы также можем «сохранить» текущий элемент, над которым мы работаем, с помощью Iterator. С помощью итератора мы получаем эффективность O (1) для remove() и insert() при работе в LinkedList. Это единственное преимущество в производительности, которое я знаю, где LinkedList всегда лучше, чем ArrayList.

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) в лучшем случае (при удалении последнего элемента).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

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

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

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

hence the memory consumption is high in LinkedList comparatively.

Между этими классами есть несколько общих черт:

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

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

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

  Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

• Поиск (get method) быстр в Arraylist (O(1)), но не в LinkedList (O(n))

  so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

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

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

ArrayList is the resizable array implementation of list interface , while

LinkedList is the Doubly-linked list implementation of the list interface.

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

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

  ArrayList get(int index) operation runs in constant time i.e O(1) while

  LinkedList get(int index) operation run time is O(n) .

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

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

• операция insert () или add (Object)

  Insertions in LinkedList are generally fast as compare to ArrayList. In LinkedList adding or insertion is O(1) operation .

  While in ArrayList, if the array is the full i.e worst case, there is an extra cost of resizing array and copying elements to the new array, which makes runtime of add operation in ArrayList O(n), otherwise it is O(1).

• операция remove (int)

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

  In LinkedList, there are two overloaded remove methods. one is remove() without any parameter which removes the head of the list and runs in constant time O(1). The other overloaded remove method in LinkedList is remove(int) or remove(Object) which removes the Object or int passed as a parameter. This method traverses the LinkedList until it found the Object and unlink it from the original list. Hence this method runtime is O(n).

  While in ArrayList remove(int) method involves copying elements from the old array to new updated array, hence its runtime is O(n).

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

LinkedList can be iterated in reverse direction using descendingIterator() while

there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.

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

If the constructor is not overloaded, then ArrayList creates an empty list of initial capacity 10, while

LinkedList only constructs the empty list without any initial capacity.

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

Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of the next and previous node. While

In ArrayList each index only holds the actual object(data).

Источник

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

Does anyone actually use LinkedList? I wrote it, and I never use it.

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

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

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

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

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

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

ArrayList расширяет AbstractList и реализует интерфейс списка. 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)
. В arrayylist
iterator.remove() - это O (n)
, тогда как в связанном списке
iterator.remove() - это O (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 очень похожи. Исходный код

Последовательное копирование большого объема памяти - это операция, оптимизированная современными процессорами, меняющая теорию и фактически делающая ArrayList / Vector намного более эффективным.

Кредиты: все тесты, опубликованные здесь, созданы Кьелл Хедстрём. Еще больше данных можно найти на его блог

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

|---------------------|---------------------|--------------------|------------|
|      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    |
|--------------------------------------|

Мое практическое правило: если мне нужен Collection (т.е.не обязательно должен быть List), используйте ArrayList, если вы знаете размер заранее, или можете точно знать размер, или знаете, что он не будет сильно отличаться. Если вам нужен произвольный доступ (т.е. вы используете get(index)), избегайте LinkedList. По сути, используйте LinkedList только в том случае, если вам не нужен доступ к индексу и вы не знаете (приблизительный) размер выделяемой коллекции. Также, если вы собираетесь делать множество добавлений и удалений (опять же через интерфейс Collection), то LinkedList может быть предпочтительнее.

Прежде всего используйте Vector вместо ArrayList, потому что вы можете перезаписать метод insureCapasity, в ArrayList является частным и добавляет 1,5 размера текущего массива https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html#ensureCapacity-int-

во многих случаях может быть лучше, что связанныйList, у las есть большое преимущество в том, что вы вставляете данные с высокой частотой, поэтому размер вашего списка меняется очень быстро, и вы не можете выделить размер для числовых элементов. Теоретически вы можете получить ошибку типа «недостаточно памяти», но в современных компьютерах у вас есть 16 ГБ и диск подкачки, поэтому, если вы перечисляете элементы, состоящие из двух частей, вы можете потерпеть неудачу, по сравнению с 15-20 годами назад.