Разница между ArrayList и LinkedList?

Node.js задняя часть Element обеспечить регресс


Как видно из рисунка,ArrayListиLinkedListВсе они являются классами реализации интерфейса List, поэтому все они реализуют все нереализованные методы List, но способ реализации отличается (из чего вы можете увидеть преимущества ориентированности на интерфейс, существуют разные реализации для разных нужд! ), интерфейс List наследует интерфейс Collection, а интерфейс Collection наследует интерфейс Iterable, поэтому видно, что List обладает характеристиками как интерфейса Collection, так и интерфейса Iterable.

ArrayList

ArrayList — это реализация изменяемого массива интерфейса List. Реализует все необязательные операции со списками и позволяет использовать все элементы, включая null. В дополнение к реализации интерфейса List этот класс предоставляет методы для управления размером массива, используемого внутри для хранения списка.
Каждый экземпляр ArrayList имеет емкость, которая представляет собой размер массива, используемого для хранения элементов списка. Он всегда как минимум равен размеру списка. По мере добавления элементов в список ArrayList его емкость также автоматически увеличивается. Автоматический рост приведет к созданию новой копии данных в новом массиве, поэтому, если вы можете предсказать объем данных, вы можете указать его емкость при построении ArrayList. Приложения также могут использовать операцию sureCapacity для увеличения емкости экземпляра ArrayList перед добавлением большого количества элементов, что может уменьшить количество добавочных перераспределений.
Обратите внимание, что это реализацияНе синхронизированоиз.如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。这通常是通过同步那些用来封装列表的对象来实现的。但如果没有这样的对象存在，则该列表需要运用{@link Collections#synchronizedList Collections.synchronizedList}来进行“包装”，该方法最好是在创建列表对象时完成，为了避免对列表进行突发的非同步操作。

List list = Collections.synchronizedList(new ArrayList(...));

Рекомендуется использовать ArrayList только в одном потоке, а в многопоточности можно выбрать Vector или CopyOnWriteArrayList.

Расширение

Очевидной особенностью массива является то, что его емкостьстабильныйДа, после создания массива емкость изменить нельзя. Поэтому, прежде чем добавлять указанный элемент в массив, первое, что нужно учитывать, — не насыщена ли его емкость.

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

Здесь мы берем операцию добавления ArrayList в качестве примера, чтобы увидеть процесс расширения внутреннего массива ArrayList.

public boolean add(E e) {
	// 关键 -> 添加之前，校验容量
	ensureCapacityInternal(size + 1); 
	
	// 修改 size，并在数组末尾添加指定元素
	elementData[size++] = e;
	return true;
}

Можно обнаружить, что ArrayList проверит внутреннюю емкость массива ивыборочноРасширьте массив. В ArrayList через приватный методensureCapacityInternalдля расширения массива. Рассмотрим конкретный процесс реализации:

  • Первый шаг операции раскрытия — определить, пуст ли внутренний массив текущего ArrayList, и если он пуст, установить для минимальной емкости minCapacity значение 10.
// 内部数组的默认容量
private static final int DEFAULT_CAPACITY = 10;

// 空的内部数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 关键 -> minCapacity = seize+1，即表示执行完添加操作后，数组中的元素个数 
private void ensureCapacityInternal(int minCapacity) {
	// 判断内部数组是否为空
	if (elementData == EMPTY_ELEMENTDATA) {
		// 设置数组最小容量（>=10）
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}
  • Затем оцените, приведет ли операция сложения к насыщению емкости внутреннего массива.
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	
	// 判断结果为 true，则表示接下来的添加操作会导致元素数量超出数组容量
	if (minCapacity - elementData.length > 0){
		// 真正的扩容操作
		grow(minCapacity);
	}
}
  • Если емкости массива недостаточно, выполняется операция расширения.Основных моментов два:Формула расширения, Завершите операцию расширения, скопировав элементы из старого массива в новый массив.
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
	
	int oldCapacity = elementData.length;
	
	// 关键-> 容量扩充公式
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	
	// 针对新容量的一系列判断
	if (newCapacity - minCapacity < 0){
		newCapacity = minCapacity;
	}
	if (newCapacity - MAX_ARRAY_SIZE > 0){
		newCapacity = hugeCapacity(minCapacity);
	}
		
	// 关键 -> 复制旧数组元素到新数组中去
	elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0){
		throw new OutOfMemoryError();
	}
			
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

Что касается операции расширения ArrayList, весь процесс выглядит следующим образом:


LinkedList

  1. LinkedList — это двусвязный список, который наследуется от AbstractSequentialList. Им также можно манипулировать как стеком, очередью или очередью.
  2. LinkedList реализует интерфейс List и может выполнять над ним операции с очередью.
  3. LinkedList реализует интерфейс Deque, что означает, что LinkedList можно использовать как двустороннюю очередь.
  4. LinkedList реализует интерфейс Cloneable, то есть переопределяет функцию clone() и может быть клонирован.
  5. LinkedList реализует интерфейс java.io.Serializable, что означает, что LinkedList поддерживает сериализацию и может передаваться посредством сериализации.
  6. LinkedList является асинхронным.

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

private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;

Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

Суммировать

1. ArrayList — это структура данных, основанная на динамических массивах, а LinkedList — структура данных, основанная на связанных списках.
2. Для получения и установки произвольного доступа ArrayList лучше, чем LinkedList, потому что LinkedList должен перемещать указатель.
3. Для операций по добавлению и удалению LinedList более доминируют, потому что ArrayList должен перемещать данные.



Категории