Реализация и разница между ArrayList и LinkedList

Java опрос
Реализация и разница между ArrayList и LinkedList

слова, написанные впереди

Реализация и разница между ArrayList и LinkedList

Все они являются реализациями списка, массив реализует реализацию связанного списка, перейдите прямо к исходному коду, сначала посмотрите на класс:


public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable
{...}


public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, Serializable
{

Первый взгляд на подсказки от реализации

RandomAccess

На первый взгляд я обнаружил, что списки, унаследованные обеими сторонами, очень похожи, один — это класс AbstractSequentialList, а другой — класс AbstractList. Все они представляют собой более 1300 строк кода, что почти одинаково, сначала ArrayList. Он реализует LinkedList RandomAccess, но не

package java.util;

/**
 * Marker interface used by <tt>List</tt> implementations to indicate that
 * they support fast (generally constant time) random access.  The primary
 * purpose of this interface is to allow generic algorithms to alter their
 * behavior to provide good performance when applied to either random or
 * sequential access lists.
 *
 * <p>The best algorithms for manipulating random access lists (such as
 * <tt>ArrayList</tt>) can produce quadratic behavior when applied to
 * sequential access lists (such as <tt>LinkedList</tt>).  Generic list
 * algorithms are encouraged to check whether the given list is an
 * <tt>instanceof</tt> this interface before applying an algorithm that would
 * provide poor performance if it were applied to a sequential access list,
 * and to alter their behavior if necessary to guarantee acceptable
 * performance.
 *
 * <p>It is recognized that the distinction between random and sequential
 * access is often fuzzy.  For example, some <tt>List</tt> implementations
 * provide asymptotically linear access times if they get huge, but constant
 * access times in practice.  Such a <tt>List</tt> implementation
 * should generally implement this interface.  As a rule of thumb, a
 * <tt>List</tt> implementation should implement this interface if,
 * for typical instances of the class, this loop:
 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @since 1.4
 */
public interface RandomAccess {
}

Основная цель этого интерфейса — позволить алгоритмам общего назначения изменять свое поведение, чтобы обеспечить хорошую производительность при применении к спискам произвольного доступа или спискам последовательного доступа.Это просто графический интерфейс, используемый для аннотаций.После версии 1.5 привык делать это. Указывает, что коллекция List, реализующая этот интерфейс, поддерживается.быстрый произвольный доступиз

Экземпляр списка, реализующий этот интерфейс, будет работать быстрее, чем итератор!

из комментария выше

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

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

qeue

Угол раскрытия

  • Расширение списка массивов

Сначала задайте ArrayList начальную длину:

List a  = new ArrayList<>(4);

Массив объектов равной длины elementData будет сгенерирован внутри ArrayList, и каждый раз, когда вы добавляете его, он будет проверять, нужно ли его расширять:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        // add后的长度 - 当前容量 > 0
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }
    
     
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }


 int oldCapacity = elementData.length;
 int newCapacity = oldCapacity + (oldCapacity >> 1);

Из кода видно, что каждое расширение в 1,5 раза больше старого. Отрежьте максимальную длину, не превышающую 2 147 483 639

  • LinkedList
List a  = new LinkedList();

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

Видно, что уникальная структура связанного списка занимает больше памяти, чем массив

Исходный код:

 public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    
 void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

Исходный код связанного списка проще.Классическая структура Node определяется и добавляется в конец связанного списка.Длина связанного списка составляет +1, и то же самое верно для addFirst и addLast.

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

В заключение

Добрый Метод реализации Сценарии применения Метод расширения Максимальная длина
ArrayList динамический массив читать 1,5 раза 2147483639
LinkedList связанный список вставить, удалить нормальная вставка в конце Посмотрите на память: бесконечная
Добрый Вставка и удаление элементов временной сложности чтение временной сложности элемента
ArrayList O(n) O(1)
LinkedList O(1) O(n)

Оригинальная ссылка:GitHub.com/Вопросы и ответы в сторону/B…

Категории