An overview of the

  1. An ArrayList, a List class based on an array implementation, is a dynamically growing and shrinking sequence of indexes

  2. This class encapsulates a dynamically allocatable array of Objects []. Each class Object has a capacity for the length of the Object[] array they encapsulate, which is automatically increased when an element is added to the ArrayList.

  3. ArrayList is used similarly to Vector, but Vector is an older collection with many drawbacks and is not recommended. The difference is that ArrayList is thread-safe, whereas Vector is thread-safe.

  4. ArrayList and Collection diagram:

The data structure of ArrayList

The underlying data structure is the array. The element type of the array is Object, that is, it can store all types of data.

ArrayList source code analysis

Inheritance structure and hierarchy

ArrayList first inherits AbstractList abstract class and implements the List interface. But AbstractList also implements the List interface, so why not ArrayList directly?

The idea is that an interface is full of abstract methods, and an abstract class can have abstract methods as well as concrete implementation methods. This is how AbstractList implements some general methods in the interface, and concrete classes like ArrayList inherit this class. Get some common methods, and then in their own implementation of some unique methods, so that the code is more concise, on the inheritance structure of the bottom class of the common method are extracted, 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.

Attributes in a class

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Java.io.Serializable {// Version number private static Final Long serialVersionUID = 8683452581122892189L; Private static final int DEFAULT_CAPACITY = 10; private static final int DEFAULT_CAPACITY = 10; private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; // A shared empty array instance for empty instances of the default size. // We distinguish it from EMPTY_ELEMENTDATA to see how much to inflate when adding the first element. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // ArrayList the array buffer in which the elements are stored. // The size of the ArrayList is the size of the array buffer. Any empty ArrayList with // elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA // will be expanded to DEFAULT_CAPACITY when the first element is added. transient Object[] elementData; // Actual element size, default is 0 private int size; Private static final Int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; private static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; }Copy the code

A constructor

An 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; private transient Object[] elementData; Public ArrayList () {super (); This. ElementData = EMPTY_ELEMENTDATA; // Call the null constructor in the parent class. //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

2) Parametric construction 1

/** * constructs an empty list with a specified initialCapacity ** @param initialCapacity the initialCapacity of the list * @throws if the specified initialCapacity is negative, IllegalArgumentException */ 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); }}Copy the code

Summary: The constructor of an arrayList does one thing: it initializes the container that stores the data, which is essentially an array, called elementData.

Core approach:

1. Add method

1) Boolean add(E); // By default, the element is added directly to the end

Public Boolean add(E E) {// Determine if the array size is sufficient, so + 1.ensurecapAcityInternal (size +1); // add the element e to the correct position in the array, and size++ elementData[size++] = e; return true; }Copy the code

EnsureCapacityInternal (XXX); Method for determining internal capacity

Private void ensureCapacityInternal(int minCapacity) {// Initialize elementData as an empty array if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { Obtain the maximum value between Default capacity and incoming parameter minCapacity = math. Max (DEFAULT_CAPACITY, minCapacity); } // Determine whether to expand the actual capacity ensureExplicitCapacity(minCapacity); }Copy the code

EnsureExplicitCapacity (XXX);

Private void ensureExplicitCapacity(int minCapacity) {modCount++; If (minCapacity - elementData.length > 0) // Enter the capacity expansion mechanism grow(minCapacity); }Copy the code

grow(xxx); The method at the heart of arrayList is the real secret to expanding the size of arrays.

/** * ArrayList core method of expansion. */ private void grow(int minCapacity) { OldCapacity int oldCapacity = elementData. Length; newCapacity = elementData. // Move oldCapacity one bit to the right, OldCapacity /2 //newCapacity is 1.5 times oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); If (newcapacity-mincapacity < 0) newCapacity = minCapacity; // check whether the newCapacity is larger than the minimum required capacity. /** * Check if the new capacity exceeds the maximum capacity defined by ArrayList. * If it does, call hugeCapacity() to compare minCapacity with MAX_ARRAY_SIZE. * If minCapacity is greater than MAX_ARRAY_SIZE, the new capacity is interger.max_value; otherwise, the new capacity is MAX_ARRAY_SIZE. */ if (newCapacity -max_array_size > 0) // Compare minCapacity with MAX_ARRAY_SIZE newCapacity = hugeCapacity(minCapacity); ElementData = array.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 (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

/** * Inserts the specified element at the specified position in this list. * Call rangeCheckForAdd to check the bounds of the index; Then call the ensureCapacityInternal method to ensure that capacity is large enough; * Move all members from index back one place; Insert element into index; And then finally size plus 1. */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! // arrayCopy () Arraycopy (elementData, index, elementData, index + 1, size-index); elementData[index] = element; size++; }Copy the code

rangeCheckForAdd(index)

Private void rangeCheckForAdd (int index) {if (index > size | | index < 0) / / insert position must be not greater than the size, and less than zero / / if it is, So the cross-border abnormal throw new IndexOutOfBoundsException (outOfBoundsMsg (index)); }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 and actually makes a series of calls, possibly to Grow, which calls hugeCapacity.

Remove () 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.

Remove (int) Removes the element at the specified position

public E remove(int index) { rangeCheck(index); ModCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; // Calculate the number of bits to move. If (numMoved > 0) // This method is used to move elements. 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 return oldValue; }Copy the code

remove(Object)

This method can be seen that the arrayList is able to store null values.

If there is an element, pass the index of the element to fastRemobe(index). Use this method to delete the 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; }Copy the code

clear()

Assign each element in elementData to null and wait for the garbage collection to collect this, so it is called 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

Conclusion:

The remove function moves the element with the specified subscript to the end of the array forward by one unit, and sets the last element of the array to NULL. This is to facilitate GC when the entire array is not used later. It can be used as a small trick.

The set () method

Sets the value of the element with the specified subscript index

Public E set(int index, E element) {// check whether the index is valid rangeCheck(index); E oldValue = elementData(index); // assign new value elementData[index] = element; // return oldValue; }Copy the code

IndexOf () method

Start by looking for elements equal to the specified element. Note that null elements can be found, meaning that an ArrayList can hold null elements. The lastIndexOf corresponding to this function means that the search starts at the tail.

Public int indexOf(Object o) {if (o == null) {for (int I = 0; i < size; If (elementData[I]==null) return I; if (elementData[I]==null) return I; } else {for (int I = 0; i < size; If (o.cube (elementData[I])) return I; } // If no, return -1; }Copy the code

The get () method

Public E get(int index) {// Check whether the index is valid rangeCheck(index); return elementData(index); }Copy the code

The get function checks if the index value is valid (only if it is greater than size, but not less than 0). It is notable that there is an element function in the get function, which returns the specific element as follows:

E elementData(int index) {
    return (E) elementData[index];
}
Copy the code

The returned values are all cast down (Object -> E), and these are the small details that mask our application.

conclusion

  1. An ArrayList can hold 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 grow() method
  4. The difference between removeAll(Collection C) and clear() in arrayList is that removeAll removes elements specified in a batch, while clear removes all elements in the collection.
  5. ArrayList is an array in nature, so it is fast at querying data, but it is slow at inserting and deleting data, so it has to move a lot of data to achieve the desired effect
  6. ArrayList implements RandomAccess, so the for loop is recommended when iterating through it.