ArrayList source code analysis

1.1 Member Variables

Private static final int DEFAULT_CAPACITY = 10; [] elementData; Private int size; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; private static final Object[] EMPTY_ELEMENTDATA = {};Copy the code

1.2 Construction method

/** * 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); } /** * Public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 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

1.3 the add operation

Public Boolean add(E E) {public Boolean add(E E) {ensureCapacityInternal(size + 1); ElementData [size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); //calculateCapacity(elementData, minCapacity) = 10 or size+1} // If the array is empty take the greater of 10 and size+1, Private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; If (minCapacity -elementdata. length > 0) grow(minCapacity); } private void grow(int minCapacity) { int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); // newCapacity = oldCapacity + half of oldCapacity If (newcapacity-mincapacity < 0) newCapacity = minCapacity; // If (newcapacity-mincapacity < 0) newCapacity = minCapacity; If (newCapacity -max_array_size > 0) newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); }Copy the code

The add process:

  1. Calculate the required capacity first, if not enough go to 2, otherwise go to 3.
  2. Copy the elements of the old array to the new array and go to 3.
  3. Adds the new element to the end of the array.
  4. Returns true.

1.4 get operation

Public E get(int index) {// If the index exceeds size, raise an exception rangeCheck(index); return elementData(index); }Copy the code

1.5 remove operation

Public E remove(int index) {// Check if the index exceeds size. If the index exceeds size, raise an exception. // change the number of times plus 1 modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; // If the deleted element is not the last element, If (numMoved > 0) System. Arraycopy (elementData, index+1, elementData, index, numMoved); ElementData [--size] = null; // clear to let GC do its work return oldValue; 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; } 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

Process for removing elements by subscript:

  1. Check whether the subscript is less than size.
  2. If the element to be deleted is not the last one, the system.arrayCopy () method is called to copy all elements following the deleted element to the previous one.
  3. The last element is left blank.

The process for removing elements by element:

  1. If the element to be deleted is null, traverse the array and use an equal sign to determine whether the elements are equal or not. If they are equal, delete as above.
  2. If the element to be deleted is not null, traverse the array and use equals to determine whether the elements are equal. If they are equal, delete them as above.

1.6 Capacity Reduction Operations

Public void trimToSize() {modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the code

ArrayList common interview questions

2.1 What is the default initial length of an ArrayList?

The default initial length of an ArrayList is 10.

2.2 How can I Expand ArrayList?

Generally, the capacity after expansion is 1.5 times the original capacity. If the capacity exceeds the maximum value of the Integer, the value is integer.max_value. Once the capacity is determined, the bottom layer calls the system.arrayCopy () method to copy the old array into the new one.

2.3 Traversing the Deletion Problem

Delete all “b” elements from ArrayList:

Public static void main (String [] args) {/ / in the ArrayList {" a ", "b", "b", "c", "d", "b", "e", "e", "e",} / / delete all the "b" ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("b"); list.add("c"); list.add("d"); list.add("b"); list.add("e"); list.add("e"); list.add("e"); System.out.println(" delete before :"+list); for(int i = 0; i < list.size(); i++) { if ("b".equals(list.get(i))){ list.remove(i); }} system.out.println (" after delete :"+list); }Copy the code
Public static void main (String [] args) {/ / in the ArrayList {" a ", "b", "b", "c", "d", "b", "e", "e", "e",} / / delete all the "b" ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("b"); list.add("c"); list.add("d"); list.add("b"); list.add("e"); list.add("e"); list.add("e"); System.out.println(" delete before :"+list); for (String str : list) { if (str.equals("b")) { list.remove(str); }} system.out.println (" after delete :"+list); }Copy the code

Results:

Before the delete operation: [a, b, b, c, d, b, e, e, e] after deletion: [a, b, c, d, e, e, e]Copy the code
[a, b, b, c, d, b, e, e, e] Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911) at java.util.ArrayList$Itr.next(ArrayList.java:861) at com.example.demo.thread.ArrayListTest.main(ArrayListTest.java:22)Copy the code

The foreach loop reported an error when the for loop element B was not completely deleted.

Reason: The remove() method will move the position of the element forward by one. If there are identical and adjacent elements, the same element will replace the deleted element in front of it. If you continue to iterate, the next element will be determined.

Solutions:

  1. Normal loop flashback traversal removed. Because the displacement of the following element does not affect the preceding element.
for (int i = list.size() - 1; i > 0; i--) { if ("b".equals(list.get(i))) { list.remove(i); }}Copy the code
  1. Use iterators.
Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { String next = iterator.next(); if (next.equals("b")) { iterator.remove(); }}Copy the code
  1. The removeIf() method is used.
    list.removeIf(a -> a.equals("b"));
Copy the code

2.4 Is ArrayList thread safe? Is there a thread-safe list?

ArrayList thread is not safe, CopyOnWriteArrayList is a thread-safe list.

3: add

Iterators in an ArrayList

Consider: Why does using foreach in 2.3 throw an exception?

Source:

public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { int cursor; // int lastRet = -1; ExpectedModCount = expectedModCount; expectedModCount = expectedModCount; Itr() {} public Boolean hasNext() {return cursor! = size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }} // omit final void checkForComodification() {if (modCount! = expectedModCount) throw new ConcurrentModificationException(); }}Copy the code

  • hasNext

    If the subscript of the next element reaches the size of the array, we are at the end.

  • next

    Test whether the expectedModCount and The expectedModCount are equal. Note that the expectedModCount is a member variable unique to the Itr class

ModCount is a member variable of the entire ArrayList. If the number of changes made through the iterator is not the same as the number of changes made through the ArrayList, an exception will be thrown. If it is equal, it continues to judge whether the cursor exceeds size and length. If it exceeds size and length, it throws an exception. If it does not, it assigns the cursor to lastRet and takes out the corresponding element.

  • remove

    First check whether lastRet is less than 0, then check whether the expectedModCount and modCount are equal, if they are equal, call

The remove() method of ArrayList removes the element with subscript lastRet, then assigns lastRet to cursor, resets lastRet to -1, and reassigns modCount to expectedModCount, Because calling the remove() method of ArrayList modifies modCount.

Now say the 2.3 foreach this loop method is used to delete the elements in the ArrayList will throw ConcurrentModificationException this exception:

First of all, foreach is an iterator, which means the iterator is iterated, but the iterator is iterated using the remove() method of ArrayList, which means the modCount is updated but the expectedModCount in the iterator is not. So when the iterator calls the next() method for traversal, the checkForComodification() method is called first to judge whether the expectedModCount and modCount are equal. Found that the anomaly would throw ConcurrentModificationException unequal. The solution is to iterate over the iterator and call the iterator’s remove() method, which synchronizes modCount to the expectedModCount.

Four:

  • ArrayList is a dynamically expanded array. Elements can be repeated according to the order in which they are entered. It is slow to add and delete and fast to query.
  • It is best to specify an initial size for ArrayList to reduce the overhead of frequent expansion.
  • Iterators are best used to iterate over deletes.