ArrayList Vs LinkedList

это плохой бенчмарк ИМО.

• нужно повторить в цикле несколько раз, чтобы разогреть jvm
• нужно что-то сделать в итерационном цикле или это может быть оптимизированный массив
• ArrayList изменяет размер, что является дорогостоящим. Если бы вы построили ArrayList как new ArrayList(500000) вы построили бы одним ударом, и тогда все распределения были бы довольно дешевыми (один предварительно выделенный резервированный массив)
• вы не указываете свой JVM памяти - он должен быть запущен с помощью -xMs = = - Xmx (все предварительно распределено) и достаточно высоко, что никакой GC, вероятно, не будет запущен
• этот тест не охватывает самый неприятный аспект LinkedList-произвольный доступ. (итератор не обязательно одно и то же). Если вы кормите скажем 10% от размера большой коллекции как случайный выбор list.get вы найдете linkedlists ужасны для захвата ничего кроме первого или последнего элемента.

для arraylist: JDK get is чего и следовало ожидать:

public E get(int index) {
    RangeCheck(index);

    return elementData[index];
}

(в основном просто возвращает элемент индексированного массива.,

для linkedlist:

public E get(int index) {
    return entry(index).element;
}

похож? Не совсем. entry-это метод, а не примитивный массив, и посмотрите, что он должен делать:

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

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

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

LinkedList состоит из цепочки узлов; каждый узел разделен выделенными и имеет передние и задние указатели на другие узлы.

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

чтобы понять, почему полученные результаты не противоречат характеристике "big O". Мы должны вернуться к первым принципам; т. е. определение.

пусть f(x) и g (x) - две функции, определенные на некотором подмножестве вещественных чисел. Один пишет

f(x) = O(g(x)) as x -> infinity

тогда и только тогда, когда для достаточно больших значений x f(x) является не более чем константой, умноженной на g(x) в абсолютном значении. То есть f (x) = O(g (x)) тогда и только тогда, когда существует a положительное вещественное число M и вещественное число x0 такое, что

|f(x)| <= M |g(x)| for all x > x_0.

во многих контекстах предположение о том, что нас интересует скорость роста, когда переменная x переходит в бесконечность, остается неустановленным, и более просто пишется, что f(x) = O(g(x)).

таким образом, заявление add1 is O(1), означает, что стоимость времени add1 операция над списком размера N стремится к константе C_{добавьте 1} как N стремится к бесконечности.

и заявление add2 is O(1) amortized over N operations означает, что в среднем стоимость времени одного из последовательности N add2 операции стремятся к постоянной C_add2 как N стремится к бесконечности.

то, что не говорит, это то, что эти константы C_{добавьте 1} и C_add2 есть. На самом деле причина, по которой LinkedList медленнее, чем ArrayList в вашем бенчмарке, заключается в том, что C_{добавьте 1} больше, чем C_add2.

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

big-O-notation-это не абсолютные тайминги, а относительные тайминги, и вы не можете сравнивать числа одного алгоритма с другим.

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

один алгоритм может занять час для одной операции и 2h для двух операций и равен O(n), а другой-O(n) тоже и занимает одну миллисекунду для одной операции и две миллисекунды для двух операций.

еще одна проблема при измерении с помощью JVM-это оптимизация hotspot-компилятора. Цикл do-nothing может быть устранен JIT-компилятором.

третье, что нужно учитывать, это ОС и JVM, используя Кеши и запустив сборку мусора между тем.

трудно найти хороший вариант использования для LinkedList. Если вам нужно только использовать интерфейс Dequeu, вы, вероятно, должны использовать ArrayDeque. Если вам действительно нужно использовать интерфейс List, вы часто будете слышать предложение использовать всегда ArrayList, потому что LinkedList ведет себя очень плохо при доступе к случайному элементу.

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

однако существует новая реализация списка под названием GapList, которая сочетает в себе сильные стороны как ArrayList, так и LinkedList. Он был разработан как drop-in замена для ArrayList и LinkedList и поэтому реализует как список интерфейсов, так и Deque. Также реализованы все открытые методы, предоставляемые ArrayList (ensureCapacty, trimToSize).

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

вы найдете дополнительную информацию о GapList в http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list.

1) Базовая Структура Данных Первое различие между ArrayList и LinkedList связано с тем, что ArrayList поддерживается массивом, а LinkedList поддерживается LinkedList. Это приведет к дальнейшим различиям в производительности.

2) LinkedList реализует Deque Еще одно различие между ArrayList и LinkedList заключается в том, что помимо интерфейса List LinkedList также реализует интерфейс Deque, который предоставляет first in 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, так как ему нужно пройти до этой записи. Хотя, в большой o нотации O(n/2) просто O (n), потому что мы игнорируем константы там.

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

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

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

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

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

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

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

o нотационный анализ предоставляет важную информацию, но он имеет свои ограничения. По определению o нотационный анализ считает, что каждая операция занимает примерно одинаковое время для выполнения, что неверно. Как отметил @seand, связанные списки внутренне используют более сложную логику для вставки и извлечения элементов (взгляните на исходный код, вы можете щелкнуть ctrl+в своей IDE). ArrayList внутренне нужно только вставить элементы в массив и увеличить его размер один раз в то время (что даже будучи операцией o(n), на практике может быть выполнена довольно быстро).

Ура

вы можете отделить добавление или удаление как двухэтапная операция.

LinkedList: если вы добавляете элемент в индекс n, вы можете переместить указатель с 0 на n-1, затем вы можете выполнить так называемую операцию O(1) add. Операция удаления такая же.

---

ArraryList: ArrayList реализует интерфейс RandomAccess, что означает, что он может получить доступ к элементу в O(1).
Если вы добавите элемент в индекс n, он можно перейти к индексу n-1 в O(1), переместить элементы после n-1, добавить установить элемент в слот n.
Движущиеся операция выполняется с помощью собственного метода под названием System.arraycopy, Это довольно быстро.

public static void main(String[] args) {

    List<Integer> arrayList = new ArrayList<Integer>();
    for (int i = 0; i < 100000; i++) {
        arrayList.add(i);
    }

    List<Integer> linkList = new LinkedList<Integer>();

    long start = 0;
    long end = 0;
    Random random = new Random();

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,index == 0" + (end - start));

}