Вступление
Списки-это некоторые из наиболее часто используемых структур данных. В Java распространенным вопросом при использовании реализации List является:
Какую реализацию я использую?
Следует ли вам выбрать ArrayList или Связанный список ? В чем разница между этими двумя?
В этой статье мы рассмотрим обе эти реализации, понаблюдаем за их внутренней работой и обсудим их производительность. Знание того, какую реализацию Списка использовать в какой ситуации, является важным навыком.
Обзор списков на Java
Списки-это структуры данных, используемые для хранения последовательных элементов. Это означает, что у каждого элемента списка есть как предшественник, так и преемник (за исключением первого и последнего, конечно, – у них есть только один из каждого).
Таким образом, списки являются упорядоченными коллекциями (в отличие от наборов), которые также допускают дубликаты. Они удобны тем, что позволяют легко манипулировать элементами (такими как вставка или извлечение) и выполнять простую итерацию всей коллекции.
Список s часто идет рука об руку с другими механизмами, такими как потоки Java, которые предлагают простые, но эффективные способы итерации, фильтрации, сопоставления и других полезных операций.
В Java List является интерфейсом в пакете java.util . Поскольку это интерфейс, он просто предоставляет список методов, которые необходимо переопределить в реальном классе реализации.
ArrayList и LinkedList являются двумя различными реализациями этих методов. Однако LinkedList также реализует интерфейс Очередь|/.
Внутренняя работа ArrayList и LinkedList
ArrayList – это массив с возможностью изменения размера , который увеличивается по мере добавления дополнительных элементов. Связанный список -это реализация списка/очереди с двойной связью.
Это означает, что ArrayList внутренне содержит массив значений и переменную счетчика, чтобы знать текущий размер в любой точке. Если добавляется элемент, его размер увеличивается. Если элемент удален, его размер уменьшается.
Связанный список содержит не массив, а двустороннюю очередь взаимосвязанных элементов. Первый элемент указывает на второй, который указывает на третий и так далее. Поскольку это дважды -связанный список, каждый элемент также указывает на своего предшественника. Пятый элемент, например, указывает как на четвертый элемент, так и на шестой элемент.
ArrayList содержит один массив для хранения данных. Связанный список нуждается в пользовательской структуре данных. Эта пользовательская структура данных представляет собой Узел . Это небольшой внутренний класс, который служит оболочкой для каждого элемента.
Чтобы сохранить элемент B , недостаточно просто сохранить его значение, как это было бы с ArrayList .
Указатель на предыдущий и следующий элементы также необходим для того, чтобы связанный список можно было обойти. Таким образом, вся структура списка состоит из взаимосвязанных узлов. Каждый узел содержит свой элемент и два указателя: ссылку на предыдущий узел и ссылку на следующий узел. У первого узла нет предыдущего узла, а у последнего узла нет следующего узла.
Наконец, в случае связанного списка мы можем предположить существование двух указателей, которые непрерывно отслеживают первый и последний элементы списка. Первый указатель, head , указывает на первый элемент и обновляется всякий раз, когда в начале вставляется новый элемент. Второй указатель, tail , указывает на последний элемент и аналогично обновляется всякий раз, когда в конце добавляется новый элемент.
Сравнение реализаций ArrayList и LinkedList
Извлечение Элементов С Помощью get()
Извлечение Элементов С Помощью get()
Если кто-то хочет извлечь элемент из ArrayList с помощью метода get(индекс int) , реализация может просто делегировать эту задачу своему внутреннему массиву:
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Конечно, выполняется дополнительная проверка данного индекса (убедитесь, что он не меньше нуля или больше размера массива).
Мы видим, что эта операция выполняется в постоянное время, или O(1) . Это означает, что независимо от размера массива любой запрошенный элемент будет возвращен мгновенно, без необходимости просматривать список. Это связано с тем, что весь массив хранится в одном уникальном месте в памяти.
Слот для второго элемента расположен точно после первого, а слот для n -го элемента расположен точно перед n+1 -т. е. Опираясь на эту внутреннюю структуру, любой элемент может быть легко извлечен по индексу.
Список ссылок.get()
Если кто – то хочет извлечь элемент из Связанного списка , используя метод get(индекс int) – вы можете, но это действительно неэффективно.
Ранее мы упоминали, что связанный список не существует в одном месте в памяти, а содержит разные узлы, соединенные друг с другом. Чтобы извлечь элемент, список необходимо просмотреть с начала (или до конца, в зависимости от того, что ближе) и следовать соединениям каждого узла, пока не будет найден нужный элемент.
Реализация того же метода выглядит следующим образом:
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 node(int index) {
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Во-первых, производится проверка, чтобы убедиться, что индекс не 0 или выше размера Связанного списка . Затем метод node() проходит по списку, пока не встретит тот, который мы ищем.
Это делается за O(N) время по сравнению с ArrayList ‘s O(1) время.
Вставка Элементов С Помощью add()
По сути, любой вид вставки может быть обобщен и реализован с использованием одного общего метода – вставки по заданному индексу.
Если элемент необходимо вставить в начале, метод может быть вызван с индексом 0 . Если элемент необходимо вставить в конец, индекс будет соответствовать текущему размеру списка. Если элемент нужно вставить где-то посередине, то пользователь должен указать этот индекс.
ArrayList.добавить()
Вставка элемента в конце довольно проста, особенно для такой структуры, как 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 позволяет нам довольно легко добавлять элементы в любой заданный индекс. Вы просто указываете указатели head и tail предыдущего и последующего элементов на новый, соответственно. Если вы вставляете в начале или в конце списка, необходимо обновить только один указатель.
Git Essentials
Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!
Давайте взглянем на реализацию:
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
В качестве альтернативы, если мы указываем индекс, то вызываются как linkLast () , так и ссылка перед() :
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Независимо от того, насколько велик список, нужно изменить только два указателя. Это делает добавление элементов в Связанный список высокоэффективной операцией. Однако достижение позиции, в которую должен быть вставлен элемент, является неэффективным.
Поиск Элементов С индексом()
Поиск элемента списка, будь то ArrayList или Связанный список , должен быть довольно похожим. Это происходит потому, что нет никакого способа узнать априори , где хранится какой-либо конкретный элемент, если массив не отсортирован и равномерно распределен.
Список просто отслеживает свои элементы и предлагает способы манипулирования ими. Чтобы знать точно , где находится каждый из этих элементов, обе реализации должны пройти какой-то итерационный процесс, пока элемент не будет найден.
ArrayList.indexOf()
В реализации ArrayList это делается с помощью простого для цикла, идущего от 0 в размер-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;
}
Это буквально линейный поиск, который не очень эффективен, но на самом деле это единственный способ поиска элемента в перетасованной коллекции (если мы игнорируем метаэвристические алгоритмы и приближения).
Список ссылок.индекс()
Связанный список делает это немного по-другому. Вместо того, чтобы перебирать массив, он должен перемещаться по списку, переходя от одного элемента к другому с использованием указателей. В конечном счете, результат один и тот же – посещение каждого элемента по одному, пока не будет найден искомый:
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
Удаление Элементов С Помощью Функции удалить()
ArrayList.удалить()
Очень похоже на добавление элементов в заданный индекс, для их удаления требуется 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 s заключается в том, что вы можете очень легко добраться до этого элемента. elementData(индекс) возвращает элемент, который вы хотите удалить в O(1) время.
Список ссылок.удалить()
Удаление элемента из Связанного списка выполняется путем отсоединения предыдущего и последующих указателей от элемента, который мы хотели бы удалить. После этого предыдущий элемент связывается со следующим в строке. Таким образом, старый элемент “застрял”, и без каких-либо ссылок на него GC заботится о нем:
public boolean remove(Object o) {
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Это делает операцию удаления элементов из Связанного списка эффективной, поскольку, опять же, необходимо изменить только несколько пунктов. Хотя, чем длиннее список, тем больше времени потребуется, чтобы добраться до элемента, который необходимо удалить, так как мы не можем получить доступ к элементам через их индекс.
Сравнение Производительности
До сих пор мы обсуждали, как ArrayList и LinkedList работают под капотом. Мы проанализировали каждый из них, чтобы лучше понять их сходства и, что более важно, различия.
В этом разделе мы кратко сравним две реализации с точки зрения производительности:
Кредиты: Миро Медиум
Сравнение get()
Мы видим, что извлечение элементов из списка всегда O(1) для ArrayList .
Для Связанного списка выбор первого или последнего элемента равен O(1) , потому что в нем всегда есть указатели на эти два элемента. Нет необходимости в дополнительной логике обхода. Однако извлечение любого другого элемента-это O(N) , потому что мы не можем просто получить к ним доступ через индекс.
Таким образом, как правило, если вы извлекаете много элементов из списка, предпочтительнее использовать ArrayList .
Сравнение вставки()
Для ArrayList вставка равна O(1) только в том случае , если она добавлена в конце. Во всех остальных случаях (добавление в начале или в середине) сложность составляет O(N) , потому что правую часть массива необходимо скопировать и сдвинуть.
Сложность Связанного списка будет O(1) как для вставки в начале, так и в конце. Еще раз, это связано с указателями head и tail , которые можно использовать для мгновенной вставки элемента в любую из этих двух позиций.
LinkedList сложность вставки посередине составляет O(N) , такая же, как для ArrayList . Операция вставки действительно эффективна, но чтобы добраться до этой точки, она должна пройти все предыдущие элементы.
Как правило, вставка элементов выполняется одинаково как в ArrayList , так и в Связанном списке , если вы в основном не работаете с первым и последним элементами.
Сравнение удалить()
Сложности удаления в значительной степени такие же, как и сложности вставки. ArrayList s удалит элементы в O(1) , если они находятся в конце – O(N) во всех остальных случаях.
LinkedList s имеют O(1) сложность для удаления с начала или конца и O(N) в других случаях.
Таким образом, удаление элементов, как правило, одно и то же, если вы в основном не работаете с начальным и последним элементами.
Вывод
ArrayList и LinkedList являются двумя различными реализациями интерфейса List|/. У них есть свои различия, которые важно понимать, чтобы правильно их использовать.
Какая реализация должна использоваться, зависит от конкретных вариантов использования. Если элементы будут часто извлекаться, нет смысла использовать LinkedList , так как извлечение происходит медленнее по сравнению с ArrayList . С другой стороны, если требуются вставки с постоянным временем или если общий размер заранее неизвестен, то предпочтительнее LinkedList .
c