Introduction to ArrayList
1.1 overview of ArrayList
1) ArrayList is a dynamically growing and shrinking sequence of indexes, which is a List class based on an array implementation.
2) This class encapsulates a dynamically reallocated Object[] array. Each class Object has a capacity property, representing the length of the Object[] array they encapsulate. The value of this property is automatically increased when an element is added to the ArrayList.
If you want to add a large number of elements to the ArrayList, you can use the ensureCapacity method to increase capacity at once, which improves performance by reducing the number of reallocations.
3) ArrayList is similar to Vector, but Vector is an older collection with many drawbacks and is not recommended.
In addition, the difference between ArrayList and Vector is that ArrayList is thread-safe. When multiple threads access the same ArrayList collection, the program needs to manually synchronize the collection. Vector is thread-safe.
4) Relationship between ArrayList and Collection:
1.2. Data structure of ArrayList
When analyzing a class, data structure is often the soul of it. To understand the underlying data structure is to understand the implementation of the class, and the specific implementation details will be analyzed in detail.
The data structure of ArrayList is:
Note: The underlying data structure is an array, array element type for Object type, that is, can store all types of data. All of our operations on instances of the ArrayList class are array-based at the bottom.
Go to top
ArrayList source code analysis
2.1. Inheritance structure and hierarchy
Let’s look at the inheritance structure of ArrayList:
ArrayList extends AbstractList
AbstractList extends AbstractCollection
All classes inherit from Object, so ArrayList’s inheritance structure looks like the one shown above.
Analysis:
1) why do you want to inherit AbstractList first, and let AbstractList implementation List < E >? Instead of having ArrayList implement List<E> directly?
So the idea here is that an interface is full of abstract methods, and an abstract class can have abstract methods, and an abstract class can have concrete implementation methods, and that’s why AbstractList is a generic way to implement an interface, and a concrete class,
ArrayList, for example, inherits this AbstractList class, gets some generic methods, and then implements some of its own. In this way, to simplify the code, it extracts all generic methods from the classes at the bottom of the inheritance structure.
First implemented together, reduce repeated code. So when you see a class with an abstract class on top of it, that’s what it does.
2) What interfaces does ArrayList implement?
AbstractList implements the List<E> interface. AbstractList implements the List<E> interface.
Some people say it is for the convenience of viewing the code, so that viewers can see at a glance. There are different opinions, but each one makes me feel reasonable, but I found the answer in stackOverFlow, which is actually very interesting.
Web site posted stackoverflow.com/questions/2… “Says Josh, author of The Book.
This is actually a mistake, because he thought it would be useful when he wrote the code, but it didn’t work, but because it didn’t make any difference, he kept it until now.
RandomAccess interface: this is a markup interface, through the API documentation, it is used for fast RandomAccess, efficiency issues, in the implementation of this interface, then use ordinary for loop to iterate, such as arrayList, performance is higher.
Instead of implementing this interface, use iterators for better performance, such as linkedList. So this notation is just to let us know what way we can get the data to perform better.
Cloneable interface: With this interface implemented, you can use the object.clone () method.
Serializable interface: Implements the serialization interface, indicating that the class can be serialized. What is serialization? Simply put, the ability to transfer from a class to a byte stream, and then from a byte stream to the original class.
2.2. Attributes in a class
Press Ctrl+C to copy the code
Press Ctrl+C to copy the code
2.3. Construction method
ArrayList has three constructors:
1) No-parameter construction method
/** * Constructs an empty list with an initial capacity of ten. Constructs an empty list with an initial capacity of ten
Private transient Object[] elementData; private transient Object[] elementData;
publicArrayList () {super ();// Call an empty constructor in the parent class
this.elementData = EMPTY_ELEMENTDATA;//EMPTY_ELEMENTDATA: an empty Object[] initializes elementData, which is also an Object[] type. An empty Object[] is given a default size of 10, which will be explained later when it is assigned.
}
Copy the code
Remark:
2) Constructor one with parameters
/**
* 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(); // The parent class hollow constructor
if (initialCapacity < 0) // Determine if the capacity of the custom size is less than 0, then the following illegal data exception is reported
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity]; // Use the custom capacity size as the size to initialize elementData
}
Copy the code
3) Parameter construction method 3 (not commonly used)
// This constructor is not commonly used
/* Strudent exends Person ArrayList
, Person I can convert this Collection
to ArrayList
and that's what this constructor does */
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); // Convert to an array
size = elementData.length; // The number of data in the array
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elementData.getClass() ! =Object[].class) // Toarray () is implemented differently for each collection, so if it is not an Object[]. Class, then it will need to be modified using methods from ArrayList.
elementData = Arrays.copyOf(elementData, size, Object[].class); }Copy the code
Summary: The constructor of an arrayList does just that: it initializes the container in which the data is stored, which is essentially an array, called elementData.
2.4. Core methods
2.4.1 Add () method (there are four)
1) Boolean add(E); // By default, the element is added directly to the end
/** * Appends the specified element to the end of this list. Add a specific element to the end of the 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) {
Size +1: size+1: size+1: size+1: size+1: size+1: size+1: size+1
ensureCapacityInternal(size + 1); // Increments modCount!!
// place the element e at the correct position in the data, and size++
elementData[size++] = e;
return true;
}
Copy the code
Analysis:
EnsureCapacityInternal (XXX); Method for determining internal capacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) { // See if the initialized elementData is an empty array with no length
MinCapacity =size+1; So we changed minCapacity to 10, which is the default size, but we haven't really initialized the size of elementData yet.
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// Check the actual capacity, above just set minCapacity=10, this method is really to determine whether elementData is sufficient
ensureExplicitCapacity(minCapacity);
}
Copy the code
EnsureExplicitCapacity (XXX);
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// If minCapacity is greater than the actual length of elementData, the length of the elementData array is insufficient and the length of elementData must be increased. What is minCapacity? What is minCapacity
/* minCapacity=size+1 when elementData is initialized as an empty array; So minCapacity=1. The previous method (ensureCapacityInternal) would have determined that the array was empty and given minCapacity=10. So far, we have not changed the size of elementData. MinCapacity =size+1; elementData is not an empty array. MinCapacity represents the actual amount of data added to elementData. Use it to determine whether the length of elementData is sufficient. If the length is insufficient, you must expand the capacity or the added element will overflow. * /
if (minCapacity - elementData.length > 0)
//arrayList can automatically expand the size of the key method here
grow(minCapacity);
}
Copy the code
grow(xxx); The method at the heart of arrayList is the real secret to expanding the size of arrays.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // Add the size of elementData to oldCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity is 1.5 times oldCapacity
if (newCapacity - minCapacity < 0)NewCapacity =0; oldCapacity=0; newCapacity=0; elementData = 10; The work ahead is all preparatory work.
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)// If newCapacity exceeds the maximum capacity limit, hugeCapacity is called, that is, the maximum that can be given to newCapacity
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// The new size is set, so copy the array and change the size.
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code
hugeCapacity();
// This is the method used above, very simple, is to assign the maximum value.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// If minCapacity is greater than MAX_ARRAY_SIZE, integer. MAX_VALUE is returned; otherwise, MAX_ARRAY_SIZE is returned. Because maxCapacity is three times of minCapacity, the expansion may be too large, so we can use minCapacity to judge.
// integer. MAX_VALUE:2147483647 MAX_ARRAY_SIZE: 2147483639 It still exceeds this limit and it's going to overflow. Arraylist provides two layers of protection.
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Copy the code
2) void add(int, E); To add an element at a particular location is to insert an element
public void add(int index, E element) {
rangeCheckForAdd(index);// Check the insertion position of index.
// As with the above analysis, see above
ensureCapacityInternal(size + 1); // Increments modCount!!
// After the index element is inserted, the index element is moved back one bit.
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Place the element at the target location
elementData[index] = element;
size++;/ / the size 1
}
Copy the code
Analysis:
rangeCheckForAdd(index)
private void rangeCheckForAdd(int index) {
if (index > size || index < 0) // The insertion position must not be greater than size or less than 0
// If so, report the out-of-bounds exception
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeSystem.arraycopy(…) : moves all elements of elementData one bit after the insertion position. View THE API documentation
public static void arraycopy(Object src,
int srcPos,
Object dest,
int destPos,
intLength) SRC: indicates the source object. SrcPos: indicates the start position of the source object. Dest: indicates the start position of the target object.// copy SRC to dest from srcPost, srcPost+length-1, and copy to destPost. From destPost to destPost+length-1
Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. A subsequence of array components are copied from
the source array referenced by src to the destination array referenced by dest. The number of components copied is equal to the length argument. The components at positions srcPos through srcPos+length-1
in the source array are copied into positions destPos through destPos+length-1, respectively, of the destination array.
If A and B are the same, copy A to the temporary array C and then through C to B, using A third party argument
If the src and dest arguments refer to the same array object, then the copying is performed as if the components at positions srcPos through srcPos+length-1 were first copied to
a temporary array with length components and then the contents of the temporary array were copied into positions destPos through destPos+length-1 of the destination array.
/ / this long, that is, to some problems in the presentation, NullPointerException and IndexOutOfBoundsException ArrayStoreException these three unusual reason.
If dest is null, then a NullPointerException is thrown.
If src is null, then a NullPointerException is thrown and the destination array is not modified.
Otherwise, if any of the following is true, an ArrayStoreException is thrown and the destination is not modified:
The src argument refers to an object that is not an array.
The dest argument refers to an object that is not an array.
The src argument and dest argument refer to arrays whose component types are different primitive types.
The src argument refers to an array with a primitive component type and the dest argument refers to an array with a reference component type.
The src argument refers to an array with a reference component type and the dest argument refers to an array with a primitive component type.
Otherwise, if any of the following is true, an IndexOutOfBoundsException is thrown and the destination is not modified:
The srcPos argument is negative.
The destPos argument is negative.
The length argument is negative.
srcPos+length is greater than src.length, the length of the source array.
destPos+length is greater than dest.length, the length of the destination array.
// If the length of A is greater than the length of B, some copies will be made instead of completely failing.
Otherwise, if any actual component of the source array from position srcPos through srcPos+length-1 cannot be converted to the component type of the destination array by assignment conversion, an ArrayStoreException is thrown.
In this case, let k be the smallest nonnegative integer less than length such that src[srcPos+k] cannot be converted to the component type of the destination array; when the exception is thrown, source array components from positions
srcPos through srcPos+k-1 will already have been copied to destination array positions destPos through destPos+k-1 and no other positions of the destination array will have been modified. (Because of the restrictions already itemized,
this paragraph effectively applies only to the situation where both arrays have component types that are reference types.)
// The argument list is explained at the beginning by saying,
Parameters:
src - the source array.
srcPos - starting position in the source array.
dest - the destination array.
destPos - starting position in the destination data.
length - the number of array elements to be copied.
Copy the code
Conclusion:
In normal cases, the array will be expanded by 1.5 times. In special cases (the size of the new array has reached the maximum value), only the maximum value is used.
When we call the add method, the actual function call looks like this:
Note: The program calls Add, which actually makes a series of calls, possibly to Grow, which might call hugeCapacity.
Example 1:
List<Integer> lists = new ArrayList<Integer> (6); lists.add(8);
Copy the codeInitialize ArrayList() constructor with lists size 0, so what steps will go through when calling lists. Add (8)? The following figure shows the program execution process and the initial and final sizes of elementData.
Note: We can see that we start elementData = {}; The add method is called and continues until grow, where elementData becomes 10, after which it returns to the add function and places 8 in elementData[0].
Example 2:
List<Integer> lists = new ArrayList<Integer> (6); lists.add(8);
Copy the codeCall the ArrayList(int) constructor, so elementData is initialized as an Object array of size 6. When add(8) is called, the steps are as follows:
Note: We know that elementData is already 6 before the add method is called, and will be passed without expansion.
2.4.2 Deletion method
In fact, these deletion methods are similar. Let’s pick a few, of which the fastRemove(int) method is private and is provided for the remove(Object) method.
1) remove(int) : Removes the element at the specified position
public E remove(int index) {
rangeCheck(index);// check the validity of index
modCount++;// This can be used for many purposes, such as a flag to detect rapid failure.
E oldValue = elementData(index);// Find the element directly by index
int numMoved = size - index - 1;// Calculate the number of bits to move.
if (numMoved > 0)
// This method is used to move elements, as already explained.
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Assign the position on --size to null for gc to collect it faster.
elementData[--size] = null; // clear to let GC do its work
// Returns the deleted element.
return oldValue;
}
Copy the code
2) remove(Object) : arrayList can store null values.
If there is an element, pass the index to fastRemobe(index), use this method to delete the element.
// The interior of the fastRemove(index) method is almost the same as the implementation of remove(index), except that arrayList can store null values
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;
}
Copy the code
3) Clear () : Assign null to each element in elementData and wait for the garbage collection to collect it, so clear
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the code
4) removeAll(Collection C)
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);// Batch delete
}
Copy the code5) batchRemove(xx,xx) : for two methods, a removeAll() : it only explicitly specifies the elements in the collection, and retainAll() tests if two collections have an intersection.
// This method is used in two places. If complement is false, removeAll is used; if true, retainAll() is used to check if two sets overlap.
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData; // Call the original set A
int r = 0, w = 0; //r is used to control the loop and w is used to record how many intersections there are
boolean modified = false;
try {
for (; r < size; r++)
// Check if there are elements in set A.
if (c.contains(elementData[r]) == complement)
// If there is, call set A
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// If contains uses the procedure, an exception is reported
if(r ! = size) {// Assign the rest of the elements to set A,
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if(w ! = size) {When removeAll() is removed, w is always 0, just as clear is always null.
/ / retainAll () : No intersection returns true, overlap, but not all pay returns true, the two collections are equal, returns false, so can't according to the return value to confirm whether there is overlap between two sets, but by the original collection of judging whether the size of the change, if there are elements in the original collection, represents a intersection, and yuan set has no elements, Indicates that the two sets do not intersect.
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true; }}return modified;
}
Copy the code
When the user removes the element with the specified index, the element with the specified index at the end of the array is moved forward by one unit and the last element in the array is set to NULL.
This is done so that when the entire array is not used later, it will be GC and can be used as a small trick.
2.4.3 set() method
public E set(int index, E element) {
// Check whether the index is valid
rangeCheck(index);
/ / the old value
E oldValue = elementData(index);
/ / assign a new value
elementData[index] = element;
// Return the old value
return oldValue;
}
Copy the code
Description: Sets the element value of the specified subscript index
2.4.4 indexOf() method
// Find the element in the array starting at the beginning
public int indexOf(Object o) {
if (o == null) { // The element is empty
for (int i = 0; i < size; i++) // Walk through the array, find the first empty element, return the index
if (elementData[i]==null)
return i;
} else { // The element to be searched is not empty
for (int i = 0; i < size; i++) // Find the first element that is equal to the specified element and return the index
if (o.equals(elementData[i]))
return i;
}
// Not found, return null
return -1;
}
Copy the code
Note: Null elements can be found, meaning that the ArrayList can store null elements. The lastIndexOf corresponding to this function means that the search starts at the tail.
2.4.5 Get () method
public E get(int index) {
// Check whether the index is valid
rangeCheck(index);
return elementData(index);
}
Copy the codeThe get function checks if the index value is greater than size, but does not check if the index value is less than 0. There is an element function in the get function, which returns an element.
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeNote: The returned values are all cast down (Object -> E), these are small details that are shielded from our application.
Go to top
Third, summary
1) arrayList can store NULL. 2) An arrayList is essentially an array of elementData. 3) ArrayLists differ from arrays in that they automatically scale, and the key method is the gorw() method. 4) The difference between removeAll(Collection C) and Clear () in arrayList is that removeAll removes a batch of specified elements, while clear removes all elements in arrayList. ArrayList implements RandomAccess, so it is recommended to use the for loop when iterating through it.