Introduction to ArrayList

An ArrayList is an array queue, the equivalent of a dynamic array. Compared to arrays in Java, its size can grow dynamically. It inherits AbstractList and implements List, RandomAccess, Cloneable, java.io.Serializable interfaces.

  1. AbstractList, List provides add, delete, modify, iterate, etc.
  2. RandmoAccess provides random access
  3. Cloneable provides functionality that can be cloned
  4. Serializable provides serialization functionality
  5. Unlike Vector, operations in ArrayList are not thread-safe! Therefore, ArrayList is recommended for single-threaded applications, whereas Vector or CopyOnWriteArrayList can be used for multi-threaded applications.

Properties of ArrayList

1234567891011121314151617181920212223242526272829303132Copy the code
 
Private static final int DEFAULT_CAPACITY = 10; private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; /** * Buffer with ArrayList(int initialCapacity) constructor and initialCapacity 0 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * Transient Object[] elementData; // Non-private to simplify class access /** * List actual size */ 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; */ protected transient int modCount = 0;Copy the code

ArrayList constructor

1234567891011121314151617181920212223242526272829303132333435Copy the code
 
/** * Initializes elementData */ public with no argument constructorArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * Build a constructor with an initial size based on arguments */ 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); }}/** * create an ArrayList containing a collection */ public ArrayList(collection <? extends E> c) { elementData = c.toArray();if((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) notreturn Object[] (see 6260652)    
    if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {        //replace with empty array.     
   this.elementData = EMPTY_ELEMENTDATA; 
   }}Copy the code

Method of ArrayList

Let’s take a look at how ArrayList is designed using a few of the more classic methods.

The first is to add methods, adding methods a total of three:

123456789101112131415161718192021222324252627282930313233343536Copy the code
 
/** * add element */ public Boolean add(E E) {/** * add element */ public Boolean add(E E) { // Increments modCount!! elementData[size++] = e;return true; } /** * public void add(int index, E element) {rangeCheckForAdd(index); EnsureCapacityInternal (size + 1); // Increments modCount!! Arraycopy (elementData, index, elementData, index + 1, size-index); arrayCopy (elementData, index, elementData, index + 1, size-index); elementData[index] = element; //List length +1 size++; } /** * public Boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew;returnnumNew ! = 0; }Copy the code

If you look closely at the top three added methods, they all call the ensureCapacityInternal method, which takes the array capacity required to perform the current add operation. It calculates whether the array needs to be expanded based on the parameters passed and completes the expansion if so. The difference is that the top two methods add only one element, so addAll passes size+1, whereas addAll passes size+ the length of the collection because it is an added collection.

Then look at the implementation of this method:

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152Copy the code
 
@param minCapacity */ private void ensureCapacityInternal(int minCapacity) {// If the size of the ArrayList is specified as 0 when creating the ArrayListif(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { Use the added size as the initial capacity. MinCapacity = math. Max (DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } @param minCapacity */ private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious codeif(mincapacity-elementdata. length > 0) // Expand grow(minCapacity); } private void grow(int minCapacity) {oldCapacity = elementdata.length; // set the newCapacity to 1.5 times the oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); // If the new capacity is not enough to store the size to be added, directly expand the capacity to the size to be addedif(newCapacity - minCapacity < 0) newCapacity = minCapacity; // If the new capacity exceeds the array's maximum capacityif(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); } 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 code

That’s how ArrayList dynamically expands. Note that ArrayList dynamically expands by replacing the original array with a new one:

1Copy the code
 
elementData = Arrays.copyOf(elementData, newCapacity);Copy the code

Next, delete:

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152Copy the code
 
Public Boolean remove(Object o) {public Boolean remove(Object o) {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; }/** * remove the index element ** / public E remove(int index) { ModCount++; E oldValue = elementData(index); Int numMoved = size-index - 1;ifArraycopy (elementData, index+1, elementData, index, numMoved); ElementData [--size] = null; elementData[--size] = null; // clear tolet GC do its work       returnoldValue; } private void fastRemove(int index) {modCount++; 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   }Copy the code

Note that deleting an element is also done through the underlying methods.

Now it’s relatively easy to look at get and set.

1234567891011121314151617181920Copy the code
 
Public E get(int index) {// Check whether the index exceeds the rangeCheck(index);returnelementData(index); Private void rangeCheck(int index) {private void rangeCheck(int index) {if (index >= size)           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));   }   public E set(int index, E element) {// Check whether the index is out of bounds rangeCheck(index); E oldValue = elementData(index); elementData[index] = element;return oldValue;   }Copy the code

You can see why you’ve been told that ArrayList queries are more efficient to modify and less efficient to add and delete.

Serializable ArrayList can be serialized, but the array elementData is transient. ArrayList can be Serializable, but the array elementData is transient.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748Copy the code
 
/** * write List to s Then write data in * * @ @ param s throws Java IO, IOException * / private void writeObject (Java. IO. ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // first write the size of the array. // Iterate over the elements in the arrayfor (int i=0; i<size; i++) {          s.writeObject(elementData[i]);      }      if(modCount ! = expectedModCount) { throw new ConcurrentModificationException(); }} / read a List of s * * * * / private voidreadObject(java.io.ObjectInputStream s)          throws java.io.IOException, ClassNotFoundException {      elementData = EMPTY_ELEMENTDATA;      // Read insize, and any hidden stuff s.defaultReadObject(); // first read group capacity s.readint (); // ignoredif (size > 0) {          // be like clone(), allocate array based upon size not capacity          ensureCapacityInternal(size);          Object[] a = elementData;          // Read in all elements in the proper order.          for(int i=0; i<size; i++) { a[i] = s.readObject(); }}}Copy the code

Due to limited space, this article only lists the above code. The full source code of ArrayList can be found at github.com/shiyujun/sy… !!!!!!!!!

Blog all articles first published in the public number “Java learning record” reprint please keep scan code concern public number can receive 2000GJava learning resources