ArrayList Summary

Data_Structure

---

ArrayList

1. Fields:

        private transient Object[] elementData; 
            //** transient is a Java keyword which marks a member variable not to be serialized when it is persisted to streams of bytes.
        private int size;
            //** size is volumn of ArrayList，but not the length of elementData
        protected transient int modCount = 0;
            //** This field is inheriented from Abtract List, which is for recording the times of structrual change. Like add(), remove(), addall(), removerange() and clear() can increase the number of modCount. The specific modCout increase operations are in ensureCapacityInternal which is called by add() and addall().

2. Contructors:

        /**By given initial length**/
        public ArrayList(int initialCapacity) {  
            super();  
            if (initialCapacity < 0)  
                throw new IllegalArgumentException("Illegal Capacity: "+  
                                                   initialCapacity);  
            this.elementData = new Object[initialCapacity];  
        }  
        /**By default initial length (10)**/
        // in newest 1.8 it shows that  "this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;"
        // with " private static final Object[] EMPTY_ELEMENTDATA = {}; "
        // but the length 10 will be initalized when checking the capacity;
        public ArrayList() {  
            this(10);  
        }  
        public ArrayList(Collection<? extends E> c) {  
            elementData = c.toArray();  
            size = elementData.length;  
            if (elementData.getClass() != Object[].class)  
                elementData = Arrays.copyOf(elementData, size, Object[].class);  
        }  

3. Dynamic Capacity Ensurance Mechanism

3.1 ArrayList通过ensureCapacityInternal(int minCapacity)方法实现自身容量的增加，在add()和addAll()方法里面都调用了改方法。

        private void ensureCapacityInternal(int minCapacity) {  
            modCount++;  
            if (minCapacity - elementData.length > 0)  
            // minCapacity means the minimal capacity need to be checked
                grow(minCapacity);  
        } 

3.2 Grow() method is mainly for capacity expansion, which expands the 1.5 times than orginal capacity each time.

        private void grow(int minCapacity) {  
            int oldCapacity = elementData.length;  
            int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5 times of array length!!
            // newCapacity is allowed
            if (newCapacity - minCapacity < 0)  
                newCapacity = minCapacity;  
            // newCapacity is larger than MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)
            if (newCapacity - MAX_ARRAY_SIZE > 0)  
                newCapacity = hugeCapacity(minCapacity); 
            elementData = Arrays.copyOf(elementData, newCapacity);  
        }  
        private static int hugeCapacity(int minCapacity) {  
            if (minCapacity < 0)   
                throw new OutOfMemoryError();  
            return (minCapacity > MAX_ARRAY_SIZE) ?  
                Integer.MAX_VALUE :  
                MAX_ARRAY_SIZE;  
        }  
        /**This is mainly for checking if the value of minCapacity is overflow**/
        private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

3.3 TrimToSize() method is mainly for reduce the lenght to fit the size

        public void trimToSize() {  
            modCount++;  
            int oldCapacity = elementData.length;  
            if (size < oldCapacity) {  
                elementData = Arrays.copyOf(elementData, size);  
            }  
        } 

4. Add Element

4.1 Add the element in the last of array

        public boolean add(E e) {  
            ensureCapacityInternal(size + 1);   
            elementData[size++] = e;  
            return true;  
        } 

4.2 Add the element with index

Notice: System.arraycopy is "Native" method which means the quite low level and high efficiency. If arraycopy operated on the same array(like elementData to elementData), the temporary array should be set up for transfer, however it doesn't work when the object is not primitive type, which is only copying the reference.

        public void add(int index, E element) {  
            rangeCheckForAdd(index);  // check the input index is inside the arrange
            ensureCapacityInternal(size + 1);   
            System.arraycopy(elementData, index, elementData, index + 1,  
                             size - index);  
            elementData[index] = element;  
            size++;  
        }  
        private void rangeCheckForAdd(int index) {  
            if (index > size || index < 0)  
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
        } 

5. Remove Element

5.1 Remove and return element with index:

        public E remove(int index) {  
            rangeCheck(index);  
            modCount++;  
            E oldValue = elementData(index);  
            int numMoved = size - index - 1;  // also can check if the remove is in the last position of array
            if (numMoved > 0)  
                System.arraycopy(elementData, index+1, elementData, index,  
                                 numMoved);  
                // start from index+1, target to start form index(removing index elem), with numMoved length! 
            elementData[--size] = null;  
            return oldValue;  
        }  

5.2 Remove with boolean return

Just check if the index-th element on array is null

        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;  
        }    

6. Batch Operation

6.1 Add All Elements

        //directly insert Collection c into ArrayList  
        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;  
             return numNew != 0;  
        }  
         //insert Collection c into ArrayList with index pointer 
         public boolean addAll(int index, Collection<? extends E> c) {  
             rangeCheckForAdd(index);  
             Object[] a = c.toArray(); // based on collection to Array 
             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;  
        } 

7. Iterator:

7.0 Initialization

        public Iterator<E> iterator() {  
            return new Itr();  // as the inner class
        }  

7.1 Fields for iterator

        int cursor;       // index of next element to return  
        int lastRet = -1; // index of last element returned; -1 if no such  
        int expectedModCount = modCount; 
        //expectedModCount的值为Itr初始化时候ArrayList的modCount的值，前面将过modCount用于记录ArrayList内发生结构性改变的次数，而Itr每次进行next或remove的时候都会去检查expectedModCount值是否还和现在的modCount值一直，从而保证了迭代器和ArrayList内数据的一致性。

        public E next() {  
            checkForComodification();  
            int i = cursor;  // thread safe??
            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];  
        }  
        final void checkForComodification() {  
            if (modCount != expectedModCount)  
                throw new ConcurrentModificationException();  
        }  

Conclusion:

1. Be sure about learning enough knowledge on Array, especially on Array copy operation!

        public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
        // all position arguments are point to the begining index 

1. Don't confused on several size variables with capacities and array length;
3.