List of Collection sub interfaces
What is the difference between Arraylist and Vector?
- ArrayList ， is the main implementation class of ， List ， which is stored in ， Object [] at the bottom. It is suitable for frequent search work, and the thread is unsafe;
- Vector ， is an ancient implementation class of ， List ， which is stored in Object [] at the bottom and thread safe.
What is the difference between Arraylist and LinkedList?
- Whether thread safety is guaranteed: ArrayList and LinkedList are not synchronized, that is, thread safety is not guaranteed;
- Underlying data structure: Arraylist uses an array of objects; The LinkedList ， bottom layer uses the ， two-way linked list ， data structure (before JDK1.6, it was a circular linked list, and JDK1.7 canceled the cycle. Pay attention to the difference between the two-way linked list and the two-way circular linked list)
- Whether insertion and deletion are affected by element position:
- ArrayList} uses array storage, so the time complexity of inserting and deleting elements is affected by the position of elements. For example, when the add (E) method is executed, ArrayList ， will append the specified element to the end of the list by default. In this case, the time complexity is O(1). However, if you want to insert and delete elements at the specified position I, the time complexity of (add(int index, E element)) is O(n-i). Because when performing the above operations, the (n-i) elements after the I and I elements in the set must perform the operation of moving backward / forward one bit.
- LinkedList ＾ is stored in a linked list. Therefore, if the insertion or deletion of elements at the beginning and end is not affected by the element position (add(E e), addFirst(E e), addlast (E), removeFirst(), removeLast()), it is approximate to O(1). If the insertion and deletion of elements are to be performed at the pointing position (add(int index, E element), remove(Object o)), the time complexity is approximate to O(n), Because you need to move to the specified position before inserting.
- Whether it supports fast random access: LinkedList does not support efficient random element access, while ArrayList does. Fast random access is to quickly obtain the element object (corresponding to the get(int index) method) through the element sequence number.
- Memory space occupation: the space waste of ArrayList is mainly reflected in that a certain capacity space is reserved at the end of the list, while the space cost of LinkedList is reflected in that each element needs to consume more space than ArrayList (because it needs to store direct successors, direct precursors and data).
Supplementary content: bidirectional linked list and bidirectional circular linked list
Bidirectional linked list: contains two pointers, one prev points to the previous node and one next points to the next node.
Bidirectional circular linked list: the next of the last node points to the head, and the prev of the head points to the last node, forming a ring.
Capacity expansion mechanism of ArrayList
Interpretation of ArrayList source code:
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity size
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Empty array (for empty instances).
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
//Shared empty array instance for empty instances of default size.
//We took it from empty_ Element data array to know how much capacity needs to be increased when the first element is added.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* An array that holds ArrayList data
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList Number of elements contained
*/
private int size;
/**
* Constructor with initial capacity parameter (the user can specify the initial size of the collection when creating the ArrayList object)
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//If the passed in parameter is greater than 0, create an array of initialCapacity size
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//If the passed in parameter is equal to 0, an empty array is created
this.elementData = EMPTY_ELEMENTDATA;
} else {
//In other cases, an exception is thrown
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*Default parameterless constructor
*DEFAULTCAPACITY_EMPTY_ELEMENTDATA Is 0 Initialize to 10, that is, the initial is actually an empty array. When the first element is added, the array capacity becomes 10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
*/
public ArrayList(Collection<? extends E> c) {
//Converts the specified collection to an array
elementData = c.toArray();
//If the length of the elementData array is not 0
if ((size = elementData.length) != 0) {
// If elementData is not Object type data (c.toArray may not return an array of Object type, so the following statement is added for judgment)
if (elementData.getClass() != Object[].class)
//Assign the contents of the original elementData array that is not of Object type to the elementData array of new Object type
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// In other cases, use an empty array instead
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* Modify the capacity of this ArrayList instance to be the current size of the list. Applications can use this operation to minimize the storage of ArrayList instances.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//The following is the capacity expansion mechanism of ArrayList
//The capacity expansion mechanism of ArrayList improves the performance. If only one is expanded at a time,
//Frequent inserts will lead to frequent copies and reduce performance, which is avoided by the capacity expansion mechanism of ArrayList.
/**
* If necessary, increase the capacity of this ArrayList instance to ensure that it can accommodate at least the number of elements
* @param minCapacity Minimum capacity required
*/
public void ensureCapacity(int minCapacity) {
//If true, the value of minExpand is 0. If false, the value of minExpand is 10
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
//If the minimum capacity is greater than the existing maximum capacity
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//1. Obtain the minimum expansion capacity
//2. Capacity expansion through minimum capacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Gets the maximum value between default capacity and incoming parameters
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//Determine whether capacity expansion is required
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//Call the grow th method for capacity expansion. Calling this method means that capacity expansion has started
grow(minCapacity);
}
/**
* Maximum array size to allocate
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList The core method of capacity expansion.
*/
private void grow(int minCapacity) {
// oldCapacity is the old capacity and newCapacity is the new capacity
int oldCapacity = elementData.length;
//Move oldCapacity one bit to the right, which is equivalent to oldCapacity /2,
//We know that bit operation is much faster than integer division. The result of the whole sentence expression is to update the new capacity to 1.5 times the old capacity,
int newCapacity = oldCapacity + (oldCapacity >> 1);
//Then check whether the new capacity is greater than the minimum required capacity. If it is still less than the minimum required capacity, take the minimum required capacity as the new capacity of the array,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//Then check whether the new capacity exceeds the maximum capacity defined by ArrayList,
//If it exceeds, hugeCapacity() is called to compare minCapacity with MAX_ARRAY_SIZE，
//If minCapacity is greater than MAX_ARRAY_SIZE, the new capacity is integer MAX_ Value, otherwise, the new capacity size is MAX_ARRAY_SIZE.
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
//Compare minCapacity and MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
*Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Returns true if the list does not contain elements.
*/
public boolean isEmpty() {
//Note the difference between = and = =
return size == 0;
}
/**
* Returns true if the list contains the specified element.
*/
public boolean contains(Object o) {
//indexOf() method: returns the index of the first occurrence of the specified element in the list. If the list does not contain this element, it is - 1
return indexOf(o) >= 0;
}
/**
*Returns the index of the first occurrence of the specified element in this list, or - 1 if the list does not contain this element
*/
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++)
//equals() method comparison
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified element in this list, or - 1 if the list does not contain an element
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns a shallow copy of this ArrayList instance. (the element itself is not copied.)
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
//Arrays. The copyof function is to copy the array and return the copied array. Parameters are the copied array and the copied length
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// This should not happen because we can clone
throw new InternalError(e);
}
}
/**
*Returns an array containing all the elements in this list in the correct order (from the first to the last element).
*The returned array will be "safe" because the list does not retain a reference to it. In other words, this method must allocate a new array.
*Therefore, the caller is free to modify the returned array. This method acts as a bridge between array based and collection based API s.
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* Return an array containing all the elements in this list (from the first to the last element) in the correct order;
*The runtime type of the returned array is the runtime type of the specified array. Returns the list if it fits the specified array.
*Otherwise, a new array is allocated for the runtime type of the specified array and the size of this list.
*If the list applies to the specified array and the remaining space (i.e. the array has more lists than this element), the element in the array immediately after the end of the collection is set to null.
*(This determines the length of the list only if the caller knows that the list does not contain any empty elements.)
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Create an array of runtime type, but the contents of ArrayList array
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//Call the arraycopy() method provided by System to copy arrays
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* Returns the element at the specified location in this list.
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* Replaces the element at the specified location in this list with the specified element.
*/
public E set(int index, E element) {
//Perform a boundary check on the index
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
//Returns the original element at this location
return oldValue;
}
/**
* Appends the specified element to the end of this list.
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//Here we see that adding elements to ArrayList is equivalent to assigning values to arrays
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified location in this list.
*First, call rangeCheckForAdd to check the limit of index; Then the ensureCapacityInternal method is called to ensure that capacity is large enough.
*Then move all members from index back to one position; Insert the element into the index position; Finally, add 1.
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy() is a method to copy arrays. We must take a look. Next, we use the arraycopy() method to copy arrays themselves
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* Deletes the element at the specified location in the list. Move any subsequent elements to the left (subtract one element from its index).
*/
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
//Elements removed from the list
return oldValue;
}
/**
* Removes the first occurrence (if any) of the specified element from the list. If the list does not contain the element, it does not change.
*Returns true if the list contains the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
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
}
/**
* Removes all elements from the list.
*/
public void clear() {
modCount++;
// Set the values of all elements in the array to null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* Appends all elements in the specified collection to the end of this list in the order returned by the Iterator of the specified collection.
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* Inserts all elements in the specified collection into this list, starting at the specified location.
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* Remove all elements indexed between fromIndex (inclusive) and toIndex from this list.
*Move any subsequent elements to the left (reduce their index).
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* Checks whether the given index is in range.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* add And addAll use a version of rangeCheck
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Return IndexOutOfBoundsException details
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* Removes all elements contained in the specified collection from this list.
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
//Returns true if the list is modified
return batchRemove(c, false);
}
/**
* Keep only the elements in this list that are included in the specified collection.
*In other words, remove all elements from this list that are not included in the specified collection.
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* Returns the list iterator of the elements in the list (in the correct order) starting at the specified position in the list.
*The specified index indicates that the first element returned by the initial call is next. The initial call to previous returns the element with the specified index minus 1.
*The list iterator returned is fail fast.
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
*Returns the list iterators in the list in the appropriate order.
*The list iterator returned is fail fast.
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
*Returns iterators for the elements in the list in the correct order.
*The iterator returned is fail fast.
*/
public Iterator<E> iterator() {
return new Itr();
}
Analysis of ArrayList capacity expansion mechanism:
When you create an ArrayList with a parameterless construction method, you actually initialize and assign an empty array. When you really add elements to the array, you really allocate capacity. That is, when the first element is added to the array, the capacity of the array is expanded to 10
- When we want to add the first element to the ArrayList, elementdata The length is 0 (because it is still an empty list), and the minCapacity is 10 because the {ensureCapacityInternal() method is executed. At this point, minCapacity - elementdata If length > 0 is true, it will enter the} growth (minCapacity) method.
- When the second element is added, minCapacity is 2, and E lementdata Length (capacity) is expanded to 10 after adding the first element. At this point, minCapacity - elementdata Length > 0 ， does not hold, so it will not enter (execute) the growth (minCapacity) method.
- When adding elements 3, 4... To 10, the grow method will not be executed, and the array capacity is 10.
Until the 11th element is added, minCapacity(11) is better than elementdata Length (10) should be larger. Enter the grow th method for capacity expansion.
After each expansion, the capacity of ArrayList will be about 1.5 times of the original capacity