Click for an in-depth understanding of the Java Collections Framework series, – (゜- ゜) feeling ロ Cheers ~

What is the ArrayList



ArrayList is a Java collection frameworkThe List interfaceAn implementation class of.

ArrayList is arguably the most used List collection, and it has the following characteristics:

  • Capacity is not fixed, put as much as you want to put (of course there is a maximum threshold, but generally can not reach)
  • Ordered (element output order is the same as input order)
  • The element can be null
  • High efficiency

    • Size (), isEmpty(), get(), set() iterator(), ListIterator() all have O(1) time complexity
    • The average time complexity of add() operations is O(n).
    • Everything else is almost O(n) time.
  • It takes up less space

    • Compare LinkedList without taking up extra space to maintain a LinkedList structure

So why does ArrayList have these advantages? We parse the source code one by one.

Member variables of ArrayList

1. Underlying data structure, array:

transient Object[] elementData
Copy the code

Since the array type is Object, null is allowed. Transient indicates that the array cannot be serialized. Initial value is DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

2. Default empty array:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private static final Object[] EMPTY_ELEMENTDATA = {};
Copy the code

I don’t know what the difference is.

3. The initial size of array is 10:

private static final int DEFAULT_CAPACITY = 10;
Copy the code

4. Current number of elements in array:

private int size;
Copy the code

size <= capacity<=”” p=””>

5. Array maximum size:

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the code

Integer.MAX_VALUE = 0x7fffffff

Converted to binary: 2 ^ 31-1111111111111111111111111

Decimal is: 2147483647, more than two billion.

Some virtualizers require a header label in front of the array, so subtract 8. OutOfMemoryError is raised when you want to allocate a number greater than MAX_ARRAY_SIZE.

The key method of ArrayList

1. Constructor

ArrayList has three constructors:

Public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // According to the specified capacity, Create an object array 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(Collection C) {elementData = c.toarray (); if ((size = elementData.length) ! = 0) {// c.toarray may not return an Object array if (elementData.getClass()! ElementData = array.copyof (elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

2. Add elements:

Public Boolean add(E E) {// Adjust the size of array ensureCapacityInternal(size + 1); // 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; size++; Public Boolean addAll(Collection c) {public Boolean addAll(Collection C) {Object[] a = c.toarray (); int numNew = a.length; EnsureCapacityInternal (size + numNew); // Increments modCount // Migrate system. arrayCopy (a, 0, elementData, size, numNew); size += numNew; // If the new array has elements, return true numNew! = 0; } public Boolean addAll(int index, Collection C) {rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; If (numMoved > 0) system. arrayCopy (elementData, index, elementData, index + numNew, numMoved); System. arrayCopy (a, 0, elementData, index, numNew); size += numNew; return numNew ! = 0; }Copy the code

Although System.arrayCopy is the underlying method, it’s not a good idea to move it one bit after each addition.

3. Adjust the size of the array:

public void ensureCapacity(int minCapacity) { int minExpand = (elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // This is not the default array. 0 // Default capacity: DEFAULT_CAPACITY; If (minCapacity > minExpand) {// The current number of elements is larger than the default capacity ensureExplicitCapacity(minCapacity); }} private void ensureCapacityInternal(int minCapacity) {// If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// Minimum capacity Take the default capacity and the maximum number of elements minCapacity = math. Max (DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; If (minCapacity -elementdata. length > 0) grow(minCapacity); }Copy the code

We can proactively call ensureCapcity to increase the capacity of the ArrayList object, so that we don’t have to expand when the added elements are full, copy them back, and so on.

4. Capacity:

private void grow(int minCapacity) { int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); If (newCapacity < 0) newCapacity = minCapacity; if (newCapacity < 0) newCapacity = minCapacity; MAX_ARRAY_SIZE if (newCapacity - MAX_ARRAY_SIZE > 0) // The maximum capacity can be Integer.MAX_VALUE 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

5. Query, modify and other operations, directly according to the corner label array operation, are very fast:

E elementData(int index) { return (E) elementData[index]; } // get public E get(int index) {rangeCheck(index); Return elementData(index); return elementData(index); } public E set(int index, E element) {rangeCheck(index); E oldValue = elementData(index); ElementData [index] = element; // return oldValue; }Copy the code

6. Delete, still a little slow:

Public E remove(int index) {rangeCheck(index); modCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // Delete 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++; private void fastRemove(int index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; Public Boolean retainAll(Collection C) {object.requirenonnull (c); return batchRemove(c, true); } private Boolean batchRemove(Collection c, boolean complement) { final Object[] elementData = this.elementData; Int r = 0, w = 0; int r = 0, w = 0; boolean modified = false; Try {// iterate through the ArrayList collection for (; r < size; R++) // if you specify whether this element exists in the collection, If (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally {// if (r! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w ! = size) {// Clear to let GC do its work for (int I = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; } public void clear() {modCount++; For (int I = 0; int I = 0; i < size; i++) elementData[i] = null; size = 0; }Copy the code

7. Judgment status:

public boolean contains(Object o) { return indexOf(o) >= 0; Public int indexOf(Object o) {if (o == null) {for (int I = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; Public int lastIndexOf(Object o) {if (o == null) {for (int I = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }Copy the code

8. Convert to array:

public Object[] toArray() { return Arrays.copyOf(elementData, size); } public T[] toArray(T[] a) {// Make a new array of a runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System. Arraycopy (elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }Copy the code

Take a look at the array.copyof () method:

public static  T[] copyOf(U[] original, int newLength, Class newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
Copy the code

If newType is an object pair, copy the elements of Original directly into the object array. Otherwise, create a new array of type newType.

An internal implementation of ArrayList

ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator

private class ListItr extends Itr implements ListIterator { ListItr(int index) { super(); cursor = index; } public boolean hasPrevious() { return cursor ! = 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}}Copy the code

inJava collections in depth: AbstractListRandomAccess can be used faster than iterators to iterate over objects that support RandomAccess.

Since ArrayList inherits RandomAccess, and its iterators are based on ArrayList methods and direct array operations, the efficiency of traverse GET is greater than the iterator.

int i=0, n=list.size(); i < n; i++)
      list.get(i);
Copy the code

Faster than using iterators:

for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();
Copy the code

Also, since ArrayList is not synchronous, when accessed concurrently, If you have any other threads at the same time in the iteration of the modified the ArrayList, fail – fast Iterator Iterator/ListIterator ConcurrentModificationException wrong.

So we need external to the ArrayList in a concurrent environment add a synchronization locks, or directly in the initialization time with Collections. SynchronizedList method for packaging:

List list = Collections.synchronizedList(new ArrayList(...) );Copy the code

Thanks

www.trinea.cn/android/arr…

Blog.csdn.net/u011518120/…

Blog.csdn.net/wl_ldy/arti…

Blog.csdn.net/zhangerqing…