An ArrayList is a list implemented based on an array. The physical storage space of an array is continuous. The complexity of modifying and viewing an array is O(1), and more operations are required to add and delete an array.
Constructor ArrayList()
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; // non-private to simplify nested class access private int size; Public ArrayList(int initialCapacity) {public ArrayList(int initialCapacity) {public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} // The default is an empty array publicArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // Specify elementData and elementData's size public ArrayList(Collection<? extends E> c) { elementData = c.toArray();if((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) notreturn Object[] (see 6260652)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else{ // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeAdd the add element (E)
Determine whether capacity expansion is required
-
Add (E E) adds objects to the end of the array
-
Add (int index, E element) Adds an object to the specified index position by moving all the objects after the index one bit later
Public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e;return true; } public void add(int index, E element) {if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
//
private void ensureCapacityInternal(int minCapacity) {
if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++;if(minCapacity - elementData.length > 0) grow(minCapacity); MinCapacity > elementdata. length}Copy the codeRemove (index) to delete
Index determines if the array is out of bounds
Retrieves elementData[index] and finally returns oldValue
If you do not remove the last object, you need to move all objects before index+1 one bit forward
ElementData [–size]=null clears references after removal
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) 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;
}
Copy the codeSet (index, element)
Index determines if the array is out of bounds
Reassign elementData[index] and return oldValue
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
Copy the codeGet (index)
Index determines if the array is out of bounds
Fetch elementData[index] and return
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
Copy the codeExpansion and turns ()
MinCapacity is the maximum value of DEFAULT_CAPACITY (10) and minCapacity (size + 1)
NewCapacity = 1.5 times oldCapacity, oldCapacity is elementData.length, which is 1/2 of the original capacity
If newCapacity > MAX_ARRAY_SIZE and if minCapacity > MAX_ARRAY_SIZE, newCapactiy is integer. MAX_VALUE; otherwise, MAX_ARRAY_SIZE is used
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Copy the codesize()
Elementdata. length size+1 elementData.length size+1 elementData.length size+1 elementData.length
public int size() {
return size;
}
Copy the codeisEmpty()
Same as above, if size==0, there are no objects in the list. Add () will do size++, remove() will do size–.
public boolean isEmpty() {
return size == 0;
}
Copy the codecontains()
Get (index) returns a value based on the index, and indexOf(Object) returns an index based on the value.
If the index returned by indexOf(Object) is greater than 0, value exists in the list; otherwise, value does not exist in the list
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if(o == null) {// Traversal matchesfor (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else{// Iterate over the matchfor (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return- 1; }Copy the codeconclusion
-
An ArrayList is a list implemented based on an array. The physical storage space of an array is continuous. The complexity of modifying and viewing an array is O(1), and more operations are required to add and delete an array.
-
Locate according to the subscript index, so set and get are convenient; Add and Remove need to be moved in batches.