ArrayList actually supports adding, deleting, modifying, querying arrays of elements and providing some methods that we are familiar with, such as add, remove, get, etc. It is dynamic, can expand capacity freely, is a more common data structure, why is it common, because it is convenient for us.
After a brief overview of the ArrayList features, officially start the source interpretation journey
(There is a large pool of English at the front, so I have time to translate it slowly, if necessary~)
First look at the inheritance relationships and declarations of ArrayList
She inherits from AbstractList and implements List, RandomAccess, Cloneable,java.io.Serializable interfaces.
ArrayList inherits AbstractList and implements List.It is an array queue that provides related add, delete, modify, traverse functions.
ArrayList implements the RandomAccess interface, which provides random access.RandomAccess is implemented in java by List to provide quick access to Lists.In ArrayList, we can quickly get an element object by its ordinal number; this is quick random access.Later, we'll compare the efficiency of Quick Random Access and Access through Iterator Iterators for Lists.
ArrayList implements the Cloneable interface, which overrides the function clone(), and can be cloned.
ArrayList implements the java.io.Serializable interface, which means that ArrayList supports serialization and can be transmitted through serialization, but one of the properties is not allowed to be serialized. Now you can see which one is.
Unlike Vector, operations in ArrayList are not thread-safe.Therefore, it is recommended that ArrayList be used in a single thread, while Vector or CopyOnWriteArrayList can be selected in a multi-threaded environment.
Properties of ArrayList
private static final long serialVersionUID = 8683452581122892189L; /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. */ private transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
The first long reshaping serialVersionUID is used for serialization, so there are only three properties defined, the object array elementData (which stores the elements of ArrayList, and the capacity of ArrayList is actually the length of the array), the integer size (which stores the actual capacity of the elements in ArrayList), and the private static final type MAX_ARRAY_SIZE is the maximum dynamic expansion capacity defined for an ArrayList.There may be questions here, why not define the maximum value of an integer directly, but the maximum value of an integer - 8?The reason is that some header information is left in the array by default in certain circumstances, and ArrayList needs to exclude the length of this information when setting the maximum capacity, otherwise an OutOfMemoryError exception may be thrown even though it does not reach the integer maximum.
It is important to note that elementData is modified with the keyword transients here, and transients are used to indicate that a field is not part of the serialization of the object, that is, when the ArrayList is serialized, the value of elementData is not included in the serialization representation, and the variable size, which is not a transients, is included in the serialization representation.Of.So the question arises, why can't elements in an ArrayList be serialized?Mark will leave it for later ~
Constructor for ArrayList
/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this(10); } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
There are three:
ArrayList(int initalCapacity): Constructor with parameters
Use initalCapacity to initialize the size of the elementData array and throw an IllegalArgumentException exception if it is less than zero;
ArrayList(): Default constructor
Initialize an ArrayList of size 10 using a parameterized constructor;
ArrayList(Collection<E> c)
The provided geometry is first converted to an array, and the c.toArray() method may not return an array of objects, in which case Arrays.copyOf is used to convert to an array of objects.
Other methods of ArrayList
1. trimToSize()
/** * Trims the capacity of this <tt>ArrayList</tt> instance to be the * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */ public void trimToSize() { modCount++; int oldCapacity = elementData.length; if (size < oldCapacity) { elementData = Arrays.copyOf(elementData, size); } }
Sometimes the object array length is not necessarily equal to the size property defined by ArrayList, then this method can be called explicitly to ensure the consistency of the two, thereby avoiding unnecessary space waste.
2.add(E): Insert an element at the end of an array
add(int, E): Insert an element at a specified location
You should all know that these two methods are common.But how did they do that?
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
add(E), insert the new element e into the position of the size, and reserve size+1 to return to the success of the addition.
add(int,E) first checks the index of the location you want to insert and throws the IndexOutOfBoundsException exception if it is less than 0 or larger than the size of ArrayList, which I believe you've all seen.Then call System.arraycopy to move the element between the index position of the original array elementData and the size-index position to the position after the start of index+1, which is a bit of a twist. To put it plainly, move the element after index in the elementData array backwards by one position, leaving the index position empty for the element elem to be addedEnt, and then add the size attribute to 1.
Comparing the two methods, we can see that both of them use the ensureCapacityInternal(size + 1) method, so this method is used to expand capacity, not to mention that you can guess.How to do this depends on the source code:
/** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { if (minCapacity > 0) ensureCapacityInternal(minCapacity); } private void ensureCapacityInternal(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ 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; }
The first way is to expose ArrayList to allow you to expand your capacity yourself, which I haven't used yet, is to have ArrayList internally help me expand my capacity.
What really works is the three remaining private methods, combined: I add one more bit to size (because I want to add an element), but I find that size+1 is larger than the length of the current object array, so I'm going to expand the array capacity and go into the group method, which logarithms according to the rules.Group objects are expanded.Let's start with two values:
A:minCapacity, which is the value after the current size+1, needs to be expanded to how large; B:newCapacity, which is the current array object length*3/2 (JKD1.7 version before was implemented by arithmetic expression, 1.7 version became bit right shift expression, the result is the same, children who are familiar with displacement should know that this change is helpful to liftHigh execution efficiency and memory usage)
The expanded rules are:
If B<A:is not enough for the capacity I need to expand, then follow A to expand.Normally not, but in special cases, such as when the current size is larger than the actual array length (not released with trimToSize().
If A<B<MAX_ARRAY_SIZE:This is the normal default expanded capacity size, which is 3/2 of the original array object, which expands half of the original length.
If B>MAX_ARRAY_SIZE: does not extend half the original length, use the upper limit to expand.
Why is an ArrayList a dynamic array? The answer lies in these methods.
The same principles of add(Collection) and add(int,Collection) implementations are the same, but there is no more than one operation that converts a Collection to an array, which is not discussed here.
3 size()
/** * Returns the number of elements in this list. * * @return the number of elements in this list */ public int size() { return size; }
This public method encapsulates the size private property, returning the current size of the ArrayList, which is also different from the length property of the array.
4 isEmpty()
/** * Returns <tt>true</tt> if this list contains no elements. * * @return <tt>true</tt> if this list contains no elements */ public boolean isEmpty() { return size == 0; }
Returns whether the ArrayList is empty.
5 contains(Object)
/** * Returns <tt>true</tt> if this list contains the specified element. * More formally, returns <tt>true</tt> if and only if this list contains * at least one element <tt>e</tt> such that * <tt>(o==null ? e==null : o.equals(e))</tt>. * * @param o element whose presence in this list is to be tested * @return <tt>true</tt> if this list contains the specified element */ public boolean contains(Object o) { return indexOf(o) >= 0; }
Use the indexOf method to determine if the current array contains the element o, and then look at the indexOf method.
6 indexOf(Object)
lastIndexOf(Object)
/** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. */ 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++) 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 this list does not contain the element. * More formally, returns the highest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. */ 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; }
An for loop is used to traverse the array, indexOf and lastIndexOf are simply from the front to the back, and the latter from the back to the front, returning the current element index if the current element is equal to o.It is important to note that ArrayList supports null lookup.
There are three ways to traverse an ArrayList
The first is iterator traversal.That is, traverse through Iterator
Integer value = null; Iterator iter = list.iterator(); while (iter.hasNext()) { value = (Integer)iter.next(); }
Second, random access, traversing through index values (since the RandomAccess interface is implemented, accessing elements through indexes is supported)
Integer value = null; int size = list.size(); for (int i=0; i<size; i++) { value = (Integer)list.get(i); }
Third, for loop traversal.
Integer value = null; for (Integer integ:list) { value = integ; }
Random access (that is, access by index number) is the most efficient and iterators the least efficient of the three traversals.As to why, interesting children's shoes can go down and study.
7 clone()
/** * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The * elements themselves are not copied.) * * @return a clone of this <tt>ArrayList</tt> instance */ public Object clone() { try { @SuppressWarnings("unchecked") ArrayList<E> v = (ArrayList<E>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(); } }
Calling the clone method of the parent class returns a copy of an object, assigning the contents of the elementData array of the returned object to the contents of the elementData array of the original object
8 toArray()
toArray(T[])
public Object[] toArray() { return Arrays.copyOf(elementData, size); } @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }
toArray() calls the Arrays.copyOf method to return an array containing size elementData elements, which copy elements from 0 to size-1 in elementData to a new array and return.
toArray(T[]) If the length of the incoming array is less than size, returns a new array of size of the same type as the incoming array; if the length of the incoming array is greater than or equal to size, all elementData is copied into a and returned, where if the length of the incoming array is greater than size, it is returned in addition to copyingThe size position in array A is set to null.
9 elementData(int)
@SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
Returns array elements index ed
10 get(int)
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { rangeCheck(index); return elementData(index); }
A check is made to see if the index is out of bounds, and if it is not, an array element with the current index of index is returned.
11 set(int, E)
/** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
First check if index is out of bounds, then save the array element indexed as index as a copy oldValue, then insert the input element into the index location and return the copy value oldValue.Was it surprising to think that the set method was called with no return value for children's shoes?
12 clear()
/** * Removes all of the elements from this list. The list will * be empty after this call returns. */ public void clear() { modCount++; // Let gc do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
Traverse with a for loop, set all elements to null, and clear the size.It is important to note that the actual length of the array elementData has not changed, at which point, although the arraylist size is 0, it still takes up space in elementData.length, which is the trimToSize method mentioned earlier to free up excess space.
13 remove(int)
/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ 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; // Let gc do its work return oldValue; }
First the index out-of-bounds check saves a copy of the old Value of the array element at the original index position, then if the index is equal to the last index value of the elementData, the last element is removed and the size is updated, otherwise all elements after the array index are moved one bit forward before the element is removed.Return removed element values after successful removal
14 remove(Object)
/** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained 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; // Let gc do its work }
This method removes an element object.Then you need to find the element's position index in the array, and then remove(index). The way to find the index is whether you're familiar with it or not. In fact, it's the indexOf(Object) method mentioned earlier, but you just find one more move to remove it later.The problem is that a new method, fastRemove, has been removed instead of the previously written remove method, because now that an index has been found, you don't need to check once for crossing the boundary like in the remove method.
15 removeRange(int,int)
protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // Let gc do its work int newSize = size - (toIndex-fromIndex); while (size != newSize) elementData[--size] = null; }
The method executes by moving the elementData element from the toIndex position forward to the fromIndex, then emptying all the elements after the toIndex position to modify size.
But why set it to a protected method?This link explains, but it doesn't seem obvious, because JDK1.7 already implements SubList in the ArrayList method, it doesn't seem useful to go around a large circle.You can share your understanding.
http://www.cnblogs.com/hzmark/archive/2012/12/19/ArrayList_removeRange.html
16 removeAll(Collection)
retainAll(Collection)
public boolean removeAll(Collection<?> c) { return batchRemove(c, false); } public boolean retainAll(Collection<?> c) { return batchRemove(c, true); } private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }
Delete or retain elements in the ArrayList that contain Collection c, both of which rely on batchRemove (Collection<?> c, Boolean complement) implementations.
Seeing here is the time to explain modCount. What kind of ghost is this?
In fact, the add(), remove(), addall(), removerange(), and clear() methods all cause modCount to grow, and the addall() and addall() methods operate on modCount in ensureCapacityInternal.ModCount is used to record the number of structural changes to the ArrayList and also for serialization.
17 writeObject(ObjectOutputStream)
/** * Save the state of the <tt>ArrayList</tt> instance to a stream (that * is, serialize it). * * @serialData The length of the array backing the <tt>ArrayList</tt> * instance is emitted (int), followed by all of its elements * (each an <tt>Object</tt>) in the proper order. */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out array length s.writeInt(elementData.length); // Write out all elements in the proper order. for (int i=0; i<size; i++) s.writeObject(elementData[i]); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
The method is to save the ArrayList as a stream, that is, to serialize modCount, array length, and elements.Or a private method, estimated to be used internally in ArrayList.
18 readObject (ObjectOutputStream)
/** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in size, and any hidden stuff s.defaultReadObject(); // Read in array length and allocate array int arrayLength = s.readInt(); Object[] a = elementData = new Object[arrayLength]; // Read in all elements in the proper order. for (int i=0; i<size; i++) a[i] = s.readObject(); }
With a writeObject, the corresponding readObject deserializes the ArrayList.
Although so much is spilled and the source code is almost glued out, there are still some ambiguous details, such as the efficiency comparison of the three traversal modes of ArrayList, why removeRange is a protection method and cannot be used directly, the internal private classes Itr, ListItr, SubList and their use, etc. The article is only shallowHighlights the methods and features of the ArrayList that are commonly used in our work, with more in-depth details to be added later.
Reprinted at: https://my.oschina.net/u/2610176/blog/600950