Сначала посмотрите, а потом лайкните, дайте себе время подумать, поиск в WeChat [Тихий король 2】Подпишитесь на этого талантливого программиста.
эта статьяGitHub github.com/itwangerОн был включен, а также есть вопросы для интервью, организованные ведущими производителями, а также моя серия статей.
ArrayListа такжеLinkedList— это две разные реализации интерфейса List, и ни одна из них не является потокобезопасной. Но новички часто не знают разницы между ними и не знают, когда использовать ArrayList и когда использовать LinkedList, поэтому эта статья здесь, чтобы проповедовать и учиться.
ArrayList использует динамические массивы для хранения элементов, а LinkedList использует для хранения элементов двусвязные списки.Это также самое существенное различие между ArrayList и LinkedList.
Примечание. Версия исходного кода JDK, используемая в этой статье, — 14. Если вы обнаружите, что исходный код в статье отличается от вашего собственного, не волнуйтесь, это не значит, что мой исходный код неверен или ваш локальный исходный код неверен. неправильно, просто версия другая.
Из-за различных методов хранения, используемых внутри ArrayList и LinkedList, их различные методы имеют разную временную сложность. Давайте сначала разберемся с концепцией временной сложности через Википедию.
В информатике временная сложность алгоритма — это функция, качественно описывающая время выполнения алгоритма. Это функция длины строки, представляющей входное значение алгоритма. Временная сложность часто выражается в нотации big-O, исключая младшие члены и старшие коэффициенты функции. При таком использовании можно сказать, что временная сложность является асимптотической, то есть рассматривается случай, когда величина входного значения приближается к бесконечности. Например, если алгоритм для любого размера n (должен быть меньшебольшой) ввод, требуется не болееработает во времени, то его асимптотическая временная сложность равна.
Для списка массивов:
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, определяется в момент объявления (размер по умолчанию равен 10), независимо от того, добавляются ли элементы на самом деле или нет, поскольку массивы сложных объектов заполняются нулями. LinkedList не нужно указывать размер при объявлении, и размер меняется при добавлении или удалении элементов.
Кроме того, ArrayList можно использовать только как список, а LinkedList можно использовать как список или очередь, поскольку он также реализует интерфейс Deque.
Когда я писал эту статью, я столкнулся с некоторыми проблемами, поэтому я обратился к некоторым техническим специалистам крупных производителей, и в результате мой друг сказал: «Если вы действительно не знаете, что использовать: ArrayList или LinkedList, выберите ArrayList!»
В то время я думал, что он шутит надо мной, но анализ временной сложности показал, что он был прав. При запросе ArrayList быстрее, чем LinkedList, сомнений нет, при вставке и удалении много данных, что LinkedList быстрее, а временная сложность, но это не так, потому что вы перебираете список, верно?
Вместо этого ArrayList более легкий, и ему не нужно поддерживать адрес предыдущего и следующего элемента для каждого элемента.
Мой вывод может не совпадать с выводами, сделанными большинством статей, поэтому я думаю, что право выбора остается за друзьями.Вы должны хорошо подумать в процессе использования, и я надеюсь, что вы изложите свои собственные мысли в области комментариев. .
Я Тихий Король Эр, программист с красивой внешностью, но полагающийся на талант.Подпишитесь, чтобы повысить эффективность обучения, не забудьте три последовательных ах, лайкните, любимый, оставьте сообщение, я не выбираю, Олли дает его.
Примечание. Если в статье есть какие-либо проблемы, пожалуйста, исправьте их.
Если вы считаете, что статья полезна для вас, добро пожаловать в поиск WeChat »Тихий король 2"Первый раз читаю, отвечаю"новичек«Кроме того, руководство по Java Xiaobai версии 2.0, содержащее более 40 000 слов, эта статьяGitHub github.com/itwangerОн был записан, добро пожаловать в звезду.