Because love so insist, because love so wait. Through the long days without drama to play, finally for the spring of life, mutual encouragement!!
1. ArrayList inheritance
ArrayListAlso known as dynamic array, the underlying List is implemented based on array. The difference with array is that it has dynamic expansion capability. As can be seen from the diagram of inheritance systemArrayList:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
}
Copy the codeImplement List, RandomAccess, Cloneable, Java. IO.Serializable interface
- List, with basic add, delete, traversal and other operations
- Achieve RandomAccess, have the ability to access randomly
- List. Clone ()
- Serializable is implemented and can be serialized
2. The ArrayList properties
/** * Default initial capacity. */
private static final int DEFAULT_CAPACITY = 10;
/** * Shared empty array instance used for empty instances
private static final Object[] EMPTY_ELEMENTDATA = {};
/** * Shared empty array instance used for default sized empty instances. * We distinguish this from EMPTY_ELEMENTDATA [public args] {public args [public args] {public args [public args] {public args [public args] {public args [public args] {public args [public args] {public args [public args] {public args [public args] {public args [public args] {public args [public args]}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be Expanded to DEFAULT_CAPACITY when the first element is added. * The array container in the collection that actually stores the data elements */
transient Object[] elementData; // non-private to simplify nested class access
/** * The size of The ArrayList (The number of elements it contains). * The number of elements in The set *@serial* /
private int size;
Copy the code- DEFAULT_CAPACITY: The default capacity of the collection. The default capacity is 10. The default capacity is 10 when the List collection instance is created using new ArrayList().
- EMPTY_ELEMENTDATA: The empty array used to create instances of the List collection with new ArrayList(0).
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA: The default capacity is an empty array, which is used to create collections using the new ArrayList() no-argument constructor. The difference with EMPTY_ELEMENTDATA is that using this empty array when adding the first element will initialize DEFAULT_CAPACITY(10) elements.
- ElementData: An array that stores data elements, using the transient modifier. This field is not serialized.
- Size: Number of stored data elements. The length of the elementData array is not the number of stored data elements. \
ArrayList constructor
- Construct ArrayList with parameters (int initialCapacity)
/** * Constructs an empty list with the specified initial capacity. * Constructs an empty list with the specified initial capacity@paramInitialCapacity The initial capacity of the list Initial capacity *@throwsIllegalArgumentException if the specified Initial capacity is negative * * Use the EMPTY_ELEMENTDATA empty array if it is 0, and throw an exception if it is less than 0. * /
// ArrayList(int initialCapacity) constructor
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Unreasonable capacity of first knowledge:"+ initialCapacity); }}Copy the code- Construct ArrayList() without arguments
Constructs an empty list with an initial capacity of ten ** Constructs an empty list with an initial capacity of ten ** Constructs an empty list with an initial capacity of ten Initialize to DEFAULTCAPACITY_EMPTY_ELEMENTDATA, and the * will be expanded to the default size of 10 when the first element is added. * /
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code- Construct ArrayList with parameters (Collection C)
/** * 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) {
// Convert the collection arguments in the constructor to arrays
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// Check whether c. toarray () returns an Object[]. If not, copy it back to Object[]. Class
if(elementData.getClass() ! = Object[].class)// Create and copy an array
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// If c is an empty collection, initialize the empty array EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA; }}Copy the code4. Operations related to ArrayList
Add operation
1. Add (E E) Adds elements to the collection
Adding elements to the end takes O(1) on average:
/** * 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) {
// For each element added, minCapacity is +1 and check whether it needs to be expanded
ensureCapacityInternal(size + 1); // Increments modCount!!
// Insert the element to the last digit
elementData[size++] = e;
return true;
}
// Calculate the minimum capacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Return the larger part of DEFAULT_CAPACITY and minCapacity
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// Check whether the capacity needs to be expanded
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;// The number of times the array structure is modified +1
// Overflow-conscious code stores elements with a size smaller than the required minimum
if (minCapacity - elementData.length > 0)
/ / capacity
grow(minCapacity);
}
/** * Increases the capacity to ensure that it can hold at lea * number of elements specified by the minimum Capacity ARg * Increments the capacity to ensure that it can hold at least the number of elements specified by the minimum capacity parameter *@param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// The original capacity
int oldCapacity = elementData.length;
// The new capacity is 1.5 times the old capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the new capacity is found to be smaller than the required capacity, the required capacity prevails
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the new capacity exceeds the maximum capacity, use the maximum capacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Copy a new array with the new capacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
// Use the maximum capacity
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 codeExecution process:
- Check whether capacity expansion is required.
- If elementData is equal to DEFAULTCAPACITY_EMPTY_ELEMENTDATA, initialize the capacity to DEFAULT_CAPACITY.
- The new capacity is 1.5 times of the oldCapacity (oldCapacity + (oldCapacity >> 1)). If the capacity is smaller than the required capacity, the required capacity prevails.
- Create a new size array and copy the old array into the new array.
2. Add (int index, E element) Adds an element to the specified position
Add elements to the specified location in an average time of O(n) :
/** * 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). * The average time complexity of adding an element to a specified location is O(n). * *@paramIndex Specifies the index * of the element to be inserted@paramElement Specifies the element to be inserted@throws IndexOutOfBoundsException {@inheritDoc} * /
public void add(int index, E element) {
// Check for overbounds
rangeCheckForAdd(index);
// Check whether the capacity needs to be expanded
ensureCapacityInternal(size + 1); // Increments modCount!!
// Move inex and the element after it one bit back to leave the index position empty
// ** performs the size- index operation **
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Insert the element at the index position
elementData[index] = element;
// The number of elements increases by 1
size++;
}
/** * A version of rangeCheck used by add and addAll
// Check for overbounds
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeExecution process:
- Check if the index is out of bounds;
- Check whether capacity expansion is required.
- Move all elements one bit back after insertion;
- Place the inserted element at the insert index position;
- Number of elements increased by 1;
3. AddAll (Collection C) Adds all elements in all Collection parameters
Find the union of two sets:
/** * Appends all of the elements in the specified collection to the end of * this list, in the order that they are returned by the * specified collection's Iterator. The behavior of this operation is * undefined if the specified collection is modified while the operation * is in progress. (This implies that the behavior of this call is * undefined if the specified collection is this list, And this * list is nonempty.) * Adds all elements from collection C to the current ArrayList * *@param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
// Convert collection C to an array
Object[] a = c.toArray();
int numNew = a.length;
// Check whether the capacity needs to be expanded
ensureCapacityInternal(size + numNew); // Increments modCount
// Copy all elements in c to the end of the array
System.arraycopy(a, 0, elementData, size, numNew);
// The size of the elements in the collection increases the size of c
size += numNew;
// Return true if c is not empty, false otherwise
returnnumNew ! =0;
}
Copy the codeExecution process:
- Copy elements from c into array A;
- Check whether capacity expansion is required.
- Copy elements from array A to the end of elementData;
Access operations
4. Get (int index) Gets the element at the specified index position
Gets the element at the specified index position in O(1) time.
/**
* 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) {
// Check for overbounds
rangeCheck(index);
// Return the element in the array index position
return elementData(index);
}
/** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. * check whether the given index range * / number in a set effective elements
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeExecution process:
- Check index of crossing the line, here only to check whether the upper bound, if the upper throw IndexOutOfBoundsException abnormalities, if the lower bound is an ArrayIndexOutOfBoundsException anomalies.
- Returns the element at the index position;
Delete operation
5. Remove (int index);
Removes the element at the specified index position in O(n) time.
/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (SubTRACTS one from their * indices). * Delete the element at the specified index position. The time complexity is O(n). * *@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) {
// Check for overbounds
rangeCheck(index);
// The number of changes to the underlying array structure of the collection +1
modCount++;
// Get the element at index position
E oldValue = elementData(index);
int numMoved = size - index - 1;
// If index is not the last digit, move the element after index one digit forward
if (numMoved > 0)
// ** perform the size- index-1 operation **
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
// Remove the last element to help the GC
elementData[--size] = null; // clear to let GC do its work
// Return the old value
return oldValue;
}
Copy the codeExecution process:
- Check if the index is out of bounds;
- Gets the element at the specified index position;
- If not the last bit is deleted, the other elements move forward one bit;
- Set the last position to null for GC collection;
- Returns the deleted element.
Note: From the source code, ArrayList deletes elements without shrinking.
6. Remove (Object o) Delete the element with the specified element value. The time complexity is O(n).
/** * 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). * Remove the element with the specified element value in O(n) time. * *@paramO element to be removed from this list, if present * The element to be removed from this list (if it exists) *@return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
// Walk through the array, find the first occurrence of the element, and quickly delete it
for (int index = 0; index < size; index++)
// If the element to be deleted is NULL, null is used for comparison, using ==
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
// Walk through the array, find the first occurrence of the element, and quickly delete it
for (int index = 0; index < size; index++)
// If the elements to be deleted are not null, compare them using equals()
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. And does not return the deleted value. * /
private void fastRemove(int index) {
// There is one less out-of-bounds check
modCount++;
// If index is not the last digit, move the element after index one digit forward
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
// Remove the last element to help the GC
elementData[--size] = null; // clear to let GC do its work
}
Copy the codeExecution process:
- Finds the first element equal to the specified element value;
- Fast delete, move the array;
- The last element is set to NULL and is processed by GC
Other operations
7. RetainAll (Collection C) find the intersection of two sets \
* Retains only the elements in this list that are contained in the * specified collection. In other words, removes from this list all * of its elements that are not contained in the specified collection. * *@param c collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">opti
* @throwsNullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">opti * or if the specified collection is null *@see Collection#contains(Object)
*/
public boolean retainAll(Collection
c) {
// Set C cannot be null
Objects.requireNonNull(c);
// Invoke the bulk delete method, where complement is passed true to delete elements not included in c
return batchRemove(c, true);
}
/** * Delete elements in batch. * complement true deletes elements not included in c. * Complement false deletes elements contained in C@param c
* @param complement
* @return* /
private boolean batchRemove(Collection<? > c,boolean complement) {
final Object[] elementData = this.elementData;
/** * use both Pointers to iterate over the array ** increments the read pointer each time, and increments the write pointer each time it is added to an element */
int r = 0, w = 0;
boolean modified = false;
try {
// Traverse the array. If c contains the element, put it in the same position as the pointer.
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Normally r is equal to size unless c. containes () throws an exception
if(r ! = size) {// If c. taines () throws an exception, copy the unread elements to the write pointer
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if(w ! = size) {// Set the element after the write pointer to null to help GC
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
// The new size is equal to the position of the write pointer.
size = w;
modified = true; }}// Returns true with modifications
return modified;
}
Copy the codeExecution process:
- Iterate over the elementData array;
- If the element is in C, add the element to the W position of the elementData array and move the W position back one bit;
- After traversal, everything before W is common to both, and everything after W is not common to both;
- Set elements after w to null for GC collection;
8. RemoveAll (Collection C) Calculates the difference set of two sets in one direction
Find the unidirectional difference set of two sets, reserving only the elements in the current set that are not in C, and not the elements in C that are not in the current group.
/** * Removes from this list all of its elements that are contained in the * specified collection. * Removes all elements contained in the specified collection from this collection. * *@param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throwsNullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">optional</a>), * or if the specified collection is null *@see Collection#contains(Object)
*/
public boolean removeAll(Collection
c) {
// Set c cannot be empty
Objects.requireNonNull(c);
// Call the batch delete method, here passing false to complement the element contained in c
return batchRemove(c, false);
}
Copy the code- This is similar to the retainAll(Collection C) method, except that elements that are not in C are retained. \
5. Analysis of the toString() method used by ArrayList
ToStrin () = toStrin(); toStrin() = toStrin(); Did not directly in the ArrayList source toString () method, we need to the parent class AbstractList superclass AbstractCollection looking for:
/** * Returns a string representation of this collection. The string * representation consists of a list of the collection's elements in the * order they are returned by its iterator, enclosed in square brackets * (<tt>"[]"</tt>). Adjacent elements are separated by the characters * <tt>", "</tt> (comma and space). Elements are converted to strings as * by {@link String#valueOf(Object)}. * * @return a string representation of this collection */ public String toString() { Iterator<E> it = iterator(); // Get the iterator if (! It.hasnext ())// Return "[]"; StringBuilder sb = new StringBuilder(); Sb. Append ('/'); for (;;) {/ / = = infinite loop while (true) E E = it. The next (); // The iterator next method takes the element and moves the cursor back to sb. Append (e == this? "(this Collection)" : E); / / three yuan judgment if (! It. HasNext ()) return sb. Append ('] '). The toString (); Append (',').append(' '); // There are elements}}Copy the code6. Questions about ArrayList (key)
1. Isn’t LinkedList more efficient at inserting and deleting data than ArrayList?
From the underlying data structure of the two:
- ArrayList is a data structure that implements dynamic arrays
- LinkedList is based on a LinkedList data structure.
- LinkedList is faster when the data volume is small, because ArrayList is frequently expanded. ArrayList is faster when the data volume is large, because ArrayList is expanded by its current capacity *1.5. A single expansion of a large capacity provides a lot of space. ArrayList is significantly more efficient than LinkedList when it does not need to be expanded, because direct assignment of array elements does not require new Node
- LinkedList is faster to insert data at the head, because LinkedList takes very little time to traverse the insertion location, whereas ArrayList requires a System. Arraycopy of all the elements in the original array
- The further into the middle, the less efficient the LinkedList is, because it traverses from both ends to the middle, and the longer the index traverses the middle, so ArrayList is likely to be more efficient than LinkedList
- ArrayList is more efficient the further it is inserted, because the array needs to copy less data, so arrayCopy is faster. Therefore, it is more efficient to insert data LinkedList at the head than ArrayList. Tail-inserted data ArrayList is more efficient than LinkedList
- LinkedList has the advantage of implementing data structures such as queues and stacks
2. Is ArrayList thread safe?
Therefore, ArrayList is not a thread-safe collection! If you need to be thread safe
1. Use Vector collections, which are thread-safe but less efficient than ArrayList. What makes Vector thread-safe, compared to ArrayList, is its method of adding elements to the collection:
// The Vector add method uses the synchronized keyword
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
Copy the code2. Use the Collections. SynchronizedList ()
List<String> list = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(list);
Copy the code3. Use CopyOnWriteArrayList
CopyOnWriteArrayList<Integer> cowaList = new CopyOnWriteArrayList<Integer>();
Copy the codeNote: When can I not lock an ArrayList synchronously?
First, in the case of a single thread does not need to lock, for efficiency! When an ArrayList is used as a local variable, it does not need to be locked because the local variable belongs to a thread. In the example above, ArrayList is used as a member variable. The collection of member variables needs to be shared by all threads.
3. How do I copy one ArrayList to another? How many can you name?
Using the ArrayList constructor, the ArrayList(Collection
c) extends all (Collection
c) method writes a loop to add() one by one
Next time is linkedList source code parsing, look forward to it!