Всем привет, я второй брат.
Это 60-я статья рубрики «Дорога продвинутого Java-программиста», поговорим о разнице между ArrayList и LinkedList. Каждый может зайти на GitHub, чтобы дать второму брату звезду и 500 звезд.
Если кто-то снова скажет тебе "Нижний слой ArrayList представляет собой массив, который выполняется быстро в запросе и медленно добавляется и удаляется; нижний слой LinkedList представляет собой связанный список, который медленно обрабатывает запросы и быстро добавляется и удаляется.", вы можете отпустить его!
Это чрезвычайно безответственное резюме, и дело в том, что вы увидите его во многих местах.
Черт, когда я впервые начал изучать Java, я тоже спросил одного здоровяка: «В чем разница между ArrayList и LinkedList?» Он сказал: «Нижний слой ArrayList — это массив, и запрос выполняется быстро, а добавление и удаление медленный; нижний слой LinkedList представляет собой связанный список, и запросы выполняются медленно, а добавления и удаления выполняются медленно. «Быстро бросьте это в меня, в то время, — подумал я, — босс такой классный!
Позже я изучил исходный код ArrayList и LinkedList и обнаружил, что первый — это массив, а второй — LinkedList, так что я восхищаюсь этим большим парнем еще больше!
Только позже, когда я сам запустил программу, чтобы проверить это, я обнаружил, что вывод босса был слишком поспешным! Это совсем не так!
Во-первых, давайте популяризируем концепцию для всех -временная сложность.
В информатике временная сложность алгоритма — это функция, качественно описывающая время выполнения алгоритма. Это функция длины строки, представляющей входное значение алгоритма. Временная сложность часто выражается в нотации big-O, исключая младшие члены и старшие коэффициенты функции. При таком использовании можно сказать, что временная сложность является асимптотической, то есть рассматривается случай, когда величина входного значения приближается к бесконечности. Например, если алгоритм для любого размера n (должен быть быстрее, чембольшой) ввод, требуется не болееПосле запуска во времени его асимптотическая временная сложность равна.
Добавление, удаление, изменение и поиск соответствуют ArrayList и LinkedList, а именно add(E e), remove(int index), add(int index, E element), get(int index), позвольте мне разобрать их один за другим. сложности, мы также понимаем абсурдность вывода о том, что «нижний слой ArrayList — массив, и запрос быстрый, а добавления и удаления — медленные; нижний слой LinkedList — связанный список, и запрос медленный , а добавления и удаления выполняются быстро».
для списка массивов:
1)get(int index)Временная сложность метода, так как он получается непосредственно из базового массива по индексу вне зависимости от длины массива.
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
Это также самое большое преимущество ArrayList.
2)add(E e)Метод будет добавлять элементы в конец массива по умолчанию, но необходимо учитывать расширение массива.Если расширение не требуется, временная сложность равна.
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
Если нужно расшириться, а это уже не первый раз(oldCapacity > 0) при расширении емкости внутреннее исполнениеArrays.copyOf()Этот метод требует много времени, и необходимо скопировать элементы исходного массива в новый расширенный массив.
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
3)add(int index, E element)Метод вставляет новые элементы в указанную позицию, учитывая, что базовый массив нужно копировать (согласно предыдущему суждению, если массив расширяется, возможно, массив нужно скопировать один раз), по наихудшему плану (будь то нужно или нет расширять,System.arraycopy()должно быть выполнено), поэтому временная сложность.
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
Чтобы выполнить следующий код, вставьте Silent King в позицию с индексом 2.
ArrayList<String> list = new ArrayList<>();
list.add("沉默王二");
list.add("沉默王三");
list.add("沉默王四");
list.add("沉默王五");
list.add("沉默王六");
list.add("沉默王七");
list.add(2, "沉默王八");
System.arraycopy()После завершения исполнения элемент с индексом 2 является Безмолвным Королем Четверки, требующим внимания. То есть при вставке элементов в массив элементы после позиции вставки будут последовательно скопированы обратно, поэтому элементы с нижним индексом 2 и нижним индексом 3 являются молчаливыми королями четырех.
затем пройтиelementData[index] = elementНазначьте элемент с индексом 2 молчаливому королю, затем выполнитеsize = s + 1, длина массива становится равной 7.
4) remove(int index)Метод удаляет элемент в указанной позиции, учитывая, что базовый массив необходимо скопировать, поэтому временная сложность составляет.
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
Для LinkedList:
1)get(int index)Временная сложность метода, потому что ему нужно перебрать весь связанный список.
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Когда нижний индекс меньше половины длины связанного списка, выполняется переход от начала к концу, в противном случае — от конца к началу, что теоретически экономит половину времени.
если индекс равен 0 илиlist.size() - 1, временная сложность. В этом случае вы можете использоватьgetFirst()а такжеgetLast()метод.
public E getFirst() {
final LinkedList.Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final LinkedList.Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
первый и последний хранятся непосредственно в связанном списке, поэтому временная сложность.
2)add(E e)Метод по умолчанию добавляет элементы в конец связанного списка, поэтому временная сложность составляет.
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
3)add(int index, E element)Метод вставляет новый элемент в указанную позицию, ему нужно сначала пройти, чтобы найти элемент, а затем вставить его, поэтому временная сложность.
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
если индекс равен 0 илиlist.size() - 1, временная сложность. В этом случае вы можете использоватьaddFirst()а такжеaddLast()метод.
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final LinkedList.Node<E> f = first;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
linkFirst()Только сначала обнови.
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
linkLast()Просто обновите в последнюю очередь.
Следует отметить, что в некоторых статьях говорится, что временная сложность вставки элементов в LinkedList аналогична, на самом деле проблематично, потому чтоadd(int index, E element)Метод вызывается при вставке элементаnode(index)Найдите элементы, этот метод был подтвержден между нами ранее, а временная сложность, даже если потом звонитьlinkBefore()Временная сложность метода вставки равна, общая временная сложность по-прежнемуВот так.
void linkBefore(E e, LinkedList.Node<E> succ) {
// assert succ != null;
final LinkedList.Node<E> pred = succ.prev;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
4) remove(int index)Метод удаляет элемент в указанной позиции с учетом необходимости вызоваnode(index)метод поиска элементов, поэтому временная сложность.
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(LinkedList.Node<E> x) {
// assert x != null;
final E element = x.item;
final LinkedList.Node<E> next = x.next;
final LinkedList.Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Благодаря сравнению временной сложности и анализу исходного кода я считаю, что у каждого есть идея при выборе, верно?
Следует отметить, что если список очень большой, ArrayList и LinkedListОЗУиспользование тоже разное. Каждый элемент LinkedList имеет больше накладных расходов, поскольку сохраняются адреса предыдущего и следующего элементов. ArrayList не имеет таких накладных расходов.
При запросе ArrayList быстрее, чем LinkedList, нет никаких сомнений; при вставке и удалении LinkedList не быстрее, чем ArrayList, потому что ему нужно пройти по списку. Вместо этого ArrayList более легкий, и ему не нужно поддерживать адрес предыдущего и следующего элемента для каждого элемента.
Однако обратите внимание, что если ArrayList требует большого количества копий массивов при добавлении, удалении и изменении, эффективность — это другой вопрос, потому что этот процесс занимает довольно много времени.
Для новичков, как правило, не требуется миллионы операций с данными.Если вы не знаете, как использовать ArrayList или LinkedList, у вас есть мозги, чтобы выбрать ArrayList!
Это 60-я статья в рубрике «Дорога к продвинутому Java-программисту». Продвинутый путь программистов Java, юмористический, простой для понимания, чрезвычайно дружелюбный и удобный для начинающих Java😘, включая, помимо прочего, синтаксис Java, структуру сбора Java, Java IO, параллельное программирование Java, виртуальную машину Java и другие основные знания 60 статей были сериализованы до сих пор.
Если вы чувствуете, что в статье есть какая-то проблема, вы также можете высказать свое мнение и мысли в области сообщений.