android ArrayList

ArrayList是一基于动态数组实现的

 @Override 
public boolean add(E object) {
     Object[] a = array;
     int s = size;
     if (s == a.length) {
        Object[] newArray = new Object[s +
            (s < (MIN_CAPACITY_INCREMENT / 2) ?
            MIN_CAPACITY_INCREMENT : s >> 1)];
     System.arraycopy(a, 0, newArray, 0, s);
     array = a = newArray;
     }
     a[s] = object;
     size = s + 1;
     modCount++;
     return true;
}

如果一直使用的是add方法增加数据，它的默认长度是12

 private static final int MIN_CAPACITY_INCREMENT = 12;

当没次达到容量是，就会扩容，大概是增长50%，即

s+s>>1

所以容量的长度变化是0，12，18，27，40...以此类推（但具体值不一定是这样，因为还存在addAll方法，两者同时使用就不是这样了），扩容后会讲原先数据通过System.arraycopy复制一份给newArray，那么newArray就是扩容后并且有原先数据的新数组，随后再对变量array赋值，供下次使用

但如果其中使用addAll方法时，原先数组的剩余容量小于新数据的长度的话，则会进行扩容，这次它的基数是原先数组已有的数据长度加上新数据的长度

@Override public boolean addAll(Collection<? extends E> collection) {
     Object[] newPart = collection.toArray();
     int newPartSize = newPart.length;
     if (newPartSize == 0) {
         return false;
     }
     Object[] a = array;
     int s = size;
     int newSize = s + newPartSize; // If add overflows, arraycopy will fail
     if (newSize > a.length) {
         int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
         Object[] newArray = new Object[newCapacity];
         System.arraycopy(a, 0, newArray, 0, s);
         array = a = newArray;
     }
     System.arraycopy(newPart, 0, a, s, newPartSize);
     size = newSize;
     modCount++;
     return true;
}

 private static int newCapacity(int currentCapacity) {
     int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
             MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
     return currentCapacity + increment;
}

这边源码中虽然写的注释是33%左右的增加，但是我感觉还是50%左右，因为只是减了1，再去执行currentCapacity+currentCapacity >> 1，我也试过几个数字，这个increment值基本还是50%左右

remove方法使用的原理是将index之后的数据拷贝了一份，并放在原先数组中，而这些数据存放的起始位置就是原先的index，拷贝完成后将最后一位（这里的最后一位并不是指整个数组的最后一位，而是排在末尾的数据，是有值的）置空

@Override 
public E remove(int index) {
     Object[] a = array;
     int s = size;
     if (index >= s) {
         throwIndexOutOfBoundsException(index, s);
     }
     @SuppressWarnings("unchecked") E result = (E) a[index];
     System.arraycopy(a, index + 1, a, index, --s - index);
     a[s] = null;  // Prevent memory leak
     size = s;
     modCount++;
     return result;
}

remove方法并不会改变已有数据的长度

android ArrayList

推荐阅读更多精彩内容