/** * 默认初始化容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 如果自定义容量为0,则会默认用它来初始化ArrayList。或者用于空数组替换。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 如果没有自定义容量,则会使用它来初始化ArrayList。或者用于空数组比对。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 这就是ArrayList底层用到的数组 * 非私有,以简化嵌套类访问 * transient 在已经实现序列化的类中,不允许某变量序列化 */ transient Object[] elementData; /** * 实际ArrayList集合大小 */ private int size; /** * 可分配的最大容量 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** * 根据initialCapacity 初始化一个空数组 */ 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); } }
/** * 不带参数初始化,默认容量为10 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
/** * 通过集合做参数的形式初始化 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
/** * 这个方法用来最小化实例存储。 */ public void trimToSize() { modCount ; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }
/** * 在数组末尾添加元素 */ public boolean add(E e) { ensureCapacityInternal(size 1); // Increments modCount!! elementData[size ] = e; return true; }
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
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 ; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
public static void main(String[] args) { ArrayList arrayList = new ArrayList(); System.out.println(arrayList.size()); } 输出:0
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] = element; size ; }
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } E elementData(int index) { return (E) elementData[index]; }
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 E get(int index) { rangeCheck(index); return elementData(index); }
public E remove(int index) { // 检测index是否合法 rangeCheck(index); // 数据结构修改次数 modCount ; E oldValue = elementData(index); // 记住这个算法 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 return oldValue; }
public class MyArrayList { // 非私有,以简化嵌套类访问 // transient 在已经实现序列化的类中,不允许某变量序列化 transient Object[] elementData; //默认容量 private static final int DEFAULT_CAPACITY = 10; // 用于空实例的 空数组实例 private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 实际ArrayList集合大小 private int size; /** * 构造方法 */ public MyArrayList(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 MyArrayList(){ this(DEFAULT_CAPACITY); } public void add(Object o){ //1. 判断数据容量是否大于 elementData ensureExplicitCapacity(size 1); //2. 使用下标进行赋值 elementData[size ] = o; } private void ensureExplicitCapacity(int minCapacity){ if (size == elementData.length){ // 需要扩容,扩容1.5倍(ArrayList默认扩容1.5倍) // 注意:如果oldCapacity值为1 int oldCapacity = elementData.length; int newCapacity = oldCapacity (oldCapacity >> 1); // 如果新容量 < 最小容量, 则将最小容量赋值给新容量 // 如果 oldCapacity=1, 则 minCapacity=1 1=2 newCapacity=1 (1>>1)=1 if (newCapacity - minCapacity < 0){ newCapacity = minCapacity; } // 创建新数组 Object[] objects = new Object[newCapacity]; // 将数据复制给新数组 System.arraycopy(elementData, 0, objects, 0, elementData.length); // 修改引用 elementData = objects; } } public Object get(int index) { rangeCheck(index); return elementData[index]; } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException("下标越界"); } /** * 通过下标删除 * @param index * @return */ public Object remove(int index) { rangeCheck(index); // modCount ; // 先查出元素 Object oldValue = elementData[index]; // 找出置换结束位置 int numMoved = size - index - 1; if (numMoved > 0) // 从 index 1 开始 将值覆盖为 index-numMoved 的值 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) { for (int index = 0; index < size; index ){ if (o.equals(elementData[index])) { remove(index); return true; } } return false; } }