Вступление

Списки - одни из наиболее часто используемых структур данных. В Java частый вопрос при использовании реализации List

Какую реализацию я использую?

Что выбрать: ArrayList или LinkedList ? В чем разница между этими двумя?

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

Обзор списков в Java

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

• у них только по одному).

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

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

В Java List - это интерфейс в пакете java.util Поскольку это интерфейс, он просто предоставляет список методов, которые необходимо переопределить в фактическом классе реализации.

ArrayList и LinkedList - две разные реализации этих методов. Однако LinkedList также реализует интерфейс Queue

Внутренняя работа ArrayList и LinkedList

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

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

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

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

Чтобы сохранить элемент B , недостаточно просто сохранить его значение, как в случае с ArrayList .

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

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

Сравнение реализаций ArrayList и LinkedList

Получение элементов с помощью get ()

ArrayList.get ()

Если кто-то хочет получить элемент из ArrayList с помощью метода get(int index) , реализация может просто делегировать эту задачу своему внутреннему массиву:

 public E get(int index) { 
 rangeCheck(index); 
 
 return elementData(index); 
 } 

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

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

Слот для второго элемента находится точно после первого, а слот для n-го элемента расположен точно перед n + 1 -м. Опираясь на эту внутреннюю структуру, любой элемент можно легко получить по индексу.

LinkedList.get ()

Если кто-то хочет получить элемент из LinkedList , используя метод get(int index) - вы можете, но это действительно неэффективно.

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

Реализация этого же метода выглядит так:

 public E get(int index) { 
 checkElementIndex(index); 
 return node(index).item; 
 } 
 
 private void checkElementIndex(int index) { 
 if (!isElementIndex(index)) 
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
 } 
 
 private boolean isElementIndex(int index) { 
 return index >= 0 && index < size; 
 } 
 
 Node<E> node(int index) { 
 if (index < (size >> 1)) { 
 Node<E> x = first; 
 for (int i = 0; i < index; i++) 
 x = x.next; 
 return x; 
 } else { 
 Node<E> x = last; 
 for (int i = size - 1; i > index; i--) 
 x = x.prev; 
 return x; 
 } 
 } 

Сначала выполняется проверка, чтобы убедиться, что индекс не равен 0 или превышает размер LinkedList . Затем метод node() просматривает список, пока не встретит тот, который мы ищем.

Это делается за время O (N) по сравнению с временем O (1) ArrayList .

Вставка элементов с помощью add ()

По сути, любой вид вставки можно обобщить и реализовать с помощью одного общего метода - вставки по заданному индексу.

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

ArrayList.add ()

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

 public boolean add(E e) { 
 ensureCapacityInternal(size + 1); // Increments modCount!! 
 elementData[size++] = e; 
 return true; 
 } 

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

 public void add(int index, E element) { 
 rangeCheckForAdd(index); 
 
 ensureCapacityInternal(size + 1); // Increments modCount!! 
 System.arraycopy(elementData, index, elementData, index + 1, size - index); 
 elementData[index] = element; 
 size++; 
 } 

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

LinkedList.add ()

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

{.ezlazyload}

Давайте посмотрим на реализацию:

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

В качестве альтернативы, если мы укажем индекс, будут linkLast() и linkBefore() :

 public void add(int index, E element) { 
 checkPositionIndex(index); 
 if (index == size) 
 linkLast(element); 
 else 
 linkBefore(element, node(index)); 
 } 
 
 void linkBefore(E e, Node<E> succ) { 
 // assert succ != null; 
 final Node<E> pred = succ.prev; 
 final Node<E> newNode = new Node<>(pred, e, succ); 
 succ.prev = newNode; 
 if (pred == null) 
 first = newNode; 
 else 
 pred.next = newNode; 
 size++; 
 modCount++; 
 } 

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

Поиск элементов с помощью indexOf ()

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

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

ArrayList.indexOf ()

В ArrayList это делается с помощью простого for переходящего от 0 до size-1 и проверяющего, соответствует ли элемент в текущем индексе заданному значению:

 public int indexOf(Object o) { 
 if (o == null) { 
 for (int i = 0; i < size; i++) 
 if (elementData[i]==null) 
 return i; 
 } else { 
 for (int i = 0; i < size; i++) 
 if (o.equals(elementData[i])) 
 return i; 
 } 
 return -1; 
 } 

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

LinkedList.indexOf ()

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

 public int indexOf(Object o) { 
 int index = 0; 
 if (o == null) { 
 for (Node<E> x = first; x != null; x = x.next) { 
 if (x.item == null) 
 return index; 
 index++; 
 } 
 } else { 
 for (Node<E> x = first; x != null; x = x.next) { 
 if (o.equals(x.item)) 
 return index; 
 index++; 
 } 
 } 
 return -1; 
 } 

Удаление элементов с помощью remove ()

ArrayList.remove ()

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

 public E remove(int index) { 
 rangeCheck(index); 
 
 modCount++; 
 E oldValue = elementData(index); 
 
 int numMoved = size - index - 1; 
 if (numMoved > 0) 
 System.arraycopy(elementData, index+1, elementData, index, numMoved); 
 elementData[--size] = null; // clear to let GC do its work 
 
 return oldValue; 
 } 

Чем больше размер копируемой детали, тем медленнее эта операция. Опять же, это делает удаление элементов из ArrayList неэффективной операцией. Однако ArrayList заключается в том, что вы можете очень легко добраться до этого элемента. elementData(index) возвращает элемент, который вы хотите удалить, за время O (1) .

LinkedList.remove ()

При удалении элемента из LinkedList предыдущий и последующие указатели отсоединяются от элемента, который мы хотим удалить. После этого предыдущий элемент связывается со следующим в строке. Таким образом, старый элемент "застрял", и без ссылок на него GC позаботится о нем:

 public boolean remove(Object o) { 
 if (o == null) { 
 for (Node<E> x = first; x != null; x = x.next) { 
 if (x.item == null) { 
 unlink(x); 
 return true; 
 } 
 } 
 } else { 
 for (Node<E> x = first; x != null; x = x.next) { 
 if (o.equals(x.item)) { 
 unlink(x); 
 return true; 
 } 
 } 
 } 
 return false; 
 } 

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

Сравнение производительности

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

В этом разделе мы кратко сравним две реализации с точки зрения производительности:

{.ezlazyload}

[Кредиты: Miro Medium]{.small}

Сравнение get ()

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

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

Таким образом, обычно, если вы извлекаете много элементов из списка, предпочтительнее ArrayList

Сравнение вставки ()

Для ArrayList вставка O (1), только если добавлена в конце. Во всех остальных случаях (добавление в начале или в середине) сложность равна O (N) , потому что правая часть массива должна быть скопирована и сдвинута.

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

Сложность вставки в LinkedList в середину O (N) , такая же, как и для ArrayList . Операция вставки действительно эффективна, но чтобы добраться до этой точки, она должна пройти через все предыдущие элементы.

Как правило, вставка элементов выполняется одинаково как для ArrayList и для LinkedList , если вы в основном не работаете с первым и последним элементами.

Сравнение remove ()

Сложность удаления почти такая же, как и сложность вставки. ArrayList удалит элементы в O (1), если они находятся в конце - O (N) во всех остальных случаях.

LinkedList имеют сложность O (1) для удаления с начала или конца и O (N) в других случаях.

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

Заключение

ArrayList и LinkedList - две разные реализации интерфейса List У них есть свои различия, которые важно понимать, чтобы правильно их использовать.

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

c