Note: The Source code for ArrayList parsed in this article is based on Java 1.8.

Header

Now that WE’ve talked about how hashMaps work, let’s look at ArrayList.

ArrayList is also a very common collection class. It is ordered and can store repeating elements. An ArrayList is essentially an array, and it expands dynamically.

Source code analysis

A constructor

Public ArrayList(int initialCapacity) {if (initialCapacity > 0) {// create an array of initialCapacity this.elementdata = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) ! If (elementdata.getClass ()! = 0) {// c. toarray might (incorrectly) not return Object[] (see 6260652) = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

The code in the constructor is short, so you can understand it.

add()

Public Boolean add(E E) {public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! ElementData [size++] = e; return true; }Copy the code

Notice that in the Add () method, the code is short. So you can see that all of the pre-operations that we did before are put into the ensureCapacityInternal method, which is going to make sure that this element has a place to put it in the array.

So let’s look at this method:

Private void ensureCapacityInternal(int minCapacity) {// If array is empty, If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {DEFAULT_CAPACITY = 10, Max (DEFAULT_CAPACITY, minCapacity) = math.max (DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; If (minCapacity -elementData. length > 0) grow(minCapacity); }Copy the code

After looking around, the expansion is done in the Grow method, so we follow up.

Private void grow(int minCapacity) {oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); If (newcapacity-mincapacity < 0) newCapacity = minCapacity; if (newcapacity-mincapacity < 0) newCapacity = minCapacity; if (newcapacity-mincapacity < 0) newCapacity = minCapacity; // Determine whether the new array size has exceeded the maximum array size, MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // Copy elements into new Arrays elementData = array.copyof (elementData, newCapacity); }Copy the code

The expansion method is to create a new array, and then copy the elements of the old array into the new array.

Of course, add also has an overloaded method called add(int index, E element), which we’ll look at as well.

Public void add(int index, E element) {rangeCheckForAdd(index); EnsureCapacityInternal (size + 1); // Increments modCount!! Arraycopy (elementData, index, elementData, index + 1, size-index); // Add the element to the specified array location elementData[index] = element; // ArrayList changes size to size++; }Copy the code

Ok, so we’re done with the add method, and we’re left with addAll(Collection
c) extends E> c) extends E> C) extends E> C) extends E> C) extends E> C

get()

The get method is as simple as returning the element at the specified position in the array.

Public E get(int index) {// Check if the index exceeds the range of the index rangeCheck(index); // Return elementData(index); }Copy the code

remove()

Public E remove(int index) {// Check if the index exceeds the range of the index rangeCheck(index); modCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; 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 code

Remove essentially moves all subsequent elements one bit forward and sets the value of the last bit to null. Finally, the deleted value is returned.

Similarly, remove has an overloaded method called remove(Object O).

Public Boolean remove(Object o) {if (o == null) {public Boolean remove(Object o) {if (o == null) { Remove (int index) for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; }} else {// If there is an element equal to o, remove the element for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }Copy the code

clear()

The clear method simply iterates through the array and sets all values to NULL.

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

Footer

That concludes the main methods of ArrayList. The source code of ArrayList is relatively simple, and basically can be read.

Let’s sum it up:

  1. ArrayList is based on arrays, so get is efficient and add or remove is inefficient.
  2. To call the default ArrayList no-argument constructor, the initial size of the array is 10;
  3. The ArrayList is automatically expanded, and when it is expanded, its capacity is increased by 1.5 times.
  4. ArrayList is not thread-safe;

So that’s it for today, and I’ll talk to you about LinkedList later.