ArrayList is a common data structure in Java Collection framework, which inherits AbstractList and implements List interface. The bottom layer implements dynamic change of capacity size based on array. Allow NULL. The RandomAccess, Cloneable and Serializable interfaces are also implemented, so ArrayList supports fast access, replication, and serialization

An easy detail to ask is that ArrayList and LinkedList both implement List. Is List an interface or an abstract class? (I was asked to cry several times in the interview before), this question is not difficult, it is a detail problem, usually pay attention to it.

About this, we start from its characteristics analysis will be relatively quick and easy to master.

An array variable

Initialize the default values

Because ArrayLIst is a mutable array, there must be an initial default value,

private static final int DEFAULT_CAPACITY = 10;
Copy the code

The default size for ArrayList initialization in JDK 1.8 is 10.

Dynamic capacity

Once we are familiar with the default values, we need to know how to expand them. At this point we need to know how to implement the expansion functions. In JDK 1.8, the expansion functions are shown in the summer code block.

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);
}
Copy the code

Its capacity expansion mechanism is very simple, take the old capacity, in the old capacity based on the operation. OldCapacity + (oldCapacity >> 1) is equivalent to oldCapacity + (oldCapacity * 0.5). Then perform two judgments and complete capacity expansion.

1) The first judgment is to prevent the capacity still unable to store data after expansion, and the minimum capacity that can store data is taken as the new capacity.

2) If the new capacity is greater than the array limit, the maximum capacity is assigned as the new capacity.

Create a way

ArrayList provides three ways to construct and initialize objects.

1) Build an ArrayList by default

public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

The ArrayList built in this way is the default ArrayList, that is, the capacity defaults to 0.

2) Specify the capacity of the way to build

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

This method can create ArrayList data of a specified capacity, or a default ArrayList if initialCapacity is 0.

3) Specify the collection build

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if((size = a.length) ! =0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else{ elementData = Arrays.copyOf(a, size, Object[].class); }}else {
        // replace with empty array.elementData = EMPTY_ELEMENTDATA; }}Copy the code

This is easy to understand, it’s just another List inserted into this.

example

ArrayList<String> arrayList1 = new ArrayList<String>();
arrayList1.add("A");
ArrayList<String> arrayList2 = new ArrayList<String>(1);
arrayList2.add("B");
ArrayList<String> arrayList3 = new ArrayList<String>(arrayList1);
Copy the code

The above is a demo written in three different ways, with the output shown below.

Obviously 1 and 3 are the same, and 2 is different from everything else.

The mechanism of fail – fast

The fail-fast mechanism is an error detection mechanism in Java collections. When in the process of iterative collection of the collection at the time of change in structure, it is possible to fail – will happen fast, namely throw ConcurrentModificationException. In layman’s terms, using the above containers in multithreaded situations can cause some problems.

Through modCount variable control in the ArrayList, every operation modCount + 1 or 1, so it is easy to understand why can appear in a multi-threaded cases ConcurrentModificationException the problem.

protected transient int modCount = 0;
Copy the code

Add and remove

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

This is one of our most frequently added apis, and as you can see, the implementation is quite simple:

1) Ensure that the capacity is normal and legal (ensure that the capacity can be automatically expanded if the capacity is insufficient).

2) Append data.

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
Copy the code

This is the function for capacity detection, very intuitive, which modCount in the fail-fast section has been covered, not to mention.

public void remove(a) {
  // If the deletion is complete, an exception is thrown
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
      // Remove by index
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

Delete logic is mainly to use their own implementation of remove index to achieve, if lastRet is illegal, directly throw an exception.

sublist

Is an inner class of ArrayList. It is used to slice a List and dynamically return a part of the ArrayList (view). It returns a part of the parent collection (view, view, view). Those of you who have studied Mysql know that views are characteristic, and whenever you change that set, the other one will follow. Here is a simple demo.

ArrayList<String> arrayList1 = new ArrayList<String>();
arrayList1.add("A");
arrayList1.add("B");
arrayList1.add("C");
System.out.println("arrayLis1 params : " + arrayList1.toString());
// Generate a view
List<String> subList = arrayList1.subList(0.1);
System.out.println("subList params : " + subList.toString());
// Update the parameters of view A
subList.set(0."D");
System.out.println("subList params : " + subList.toString());
// Print the original object to see if it has changed
System.out.println("update arrayLis1 params : " + arrayList1.toString());
Copy the code

And this demo really helps us understand what that does.

conclusion

This is the third article of relearning Java, and the first of Collection framework. As one of the most important parts of Java, we need to spend enough energy in this part to learn. ArrayList, as the beginning of Java Collection, is the simplest part of Collection framework. So make sure you get it. Finally, my knowledge is limited, if there are fallacies please correct, thank you.