源码
/** * The maximum size of array to allocate. 数组可以分配的最大空间 * Some VMs reserve some header words in an array. 一些虚拟机会保存一些头文字在数组中 * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit 试图分配最大空间将会导致内存溢出（因为需要的数组容量大于了虚拟机的限制） */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * Default initial capacity. 初始容量 */ private static final int DEFAULT_CAPACITY = 10; /** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure（确保） that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity 预期需要最小的容量 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != EMPTY_ELEMENTDATA) // any size if real element table ? 0 // larger than default for empty table. It's already supposed to be // at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } /** * int newCapacity = oldCapacity + (oldCapacity >> 1); * 新容量为原来的1.5倍 */ 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); } /** * */ private static int hugeCapacity(int minCapacity) { //如果因为二进制的移位而导致溢出变为负数 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //如果大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8） //返回Interger的最大值0x7fffffff(2147483647) //否则返回MAX_ARRAY_SIZE return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }2017.03.05 新增
ArrayList的初始容量为10 那么在添加10个元素之后，再添加第11个元素的时候会进行依次扩容
Created with Raphaël 2.1.0 1.client添加一个元素 2.如果当前的容量小与增加完元素的所需容量 3.增加之1.5*old容量，并拷贝至当前新建的数组 4.添加成功 yes no所涉及到的源码
//客户端调用的add方法 public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } //上面函数的第一步，确保容量可以容纳下新加的元素 private void ensureCapacityInternal(int minCapacity) { //修改次数加1，因为是添加，所以修改次数+1 modCount++; // 如果添加这个元素会导致数组溢出 if (minCapacity - elementData.length > 0) grow(minCapacity);//增加最小的容量 } //grow() private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5倍 if (newCapacity - minCapacity < 0) //防止溢出int型，溢出之后是负数 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) //如果新的容量大于数组系统默认容量 newCapacity = hugeCapacity(minCapacity); // 拷贝原来的数组至新开辟空间的数组内，是一个native方法 elementData = Arrays.copyOf(elementData, newCapacity); } //hugeCapacity private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // int型溢出 throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;//int类型和数组系统默认容量取最大 } //java中默认最大为（2^31-1）-8 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;set方法设置固定下标位置为指定的元素。
public E set(int index, E e) { //判断下标是否在数组范围内，如果不在 会抛出下标溢出边界异常IndexOutOfBoundsException(); rangeCheck(index); E oldValue = ArrayList.this.elementData(offset + index); ArrayList.this.elementData[offset + index] = e; return oldValue; }这是种什么方法呢 remove(int index) remove(Object o)
既能根据下标删除，又能根据元素删除，乍一看没什么关系吧， 仔细想一想好像没什么问题
但是int与Integer有什么不一样。。。
如果是删除Integer方法必须要手动包装int
根据对象删除的时候只会删除第一个
public boolean remove(Object o) { //如果是null 不能调用equals方法，如果是对象可以调用equals方法 //先找出下标再删除 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; } //fastremove与根据下标删除，与下面的方法仅仅少了一步rangeCheck 不知为何不使用此方法。 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; // Let gc do its work }根据下标删除
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);//调用native方法通过复制内存块来复制数组 elementData[--size] = null; // 手动设置gc return oldValue; }2017.12.16 新增
随机读写测试
public class ListCompare { public static final int N = 10000000; public static void main(String[] args) { Random random = new Random(); List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < N; i++) { arrayList.add(1); } for (int i = 0; i < N; i++) { linkedList.add(1); } System.out.println("初始化ArrayList与LinkList成功"); long begin1 = System.currentTimeMillis(); randomGetAndSet(random, arrayList); long end1 = System.currentTimeMillis(); System.out.println("ArrayList: " + (end1 - begin1) + " ms"); long begin2 = System.currentTimeMillis(); randomGetAndSet(random, linkedList); long end2 = System.currentTimeMillis(); System.out.println("LinkedList: " + (end2 - begin2) + " ms"); } private static void randomGetAndSet(Random random, List<Integer> list) { for (int i = 0; i < N; i++) { if (i % 10000 == 0) { System.out.println("--------------我还活着-----------------"); } if (random.nextBoolean()) { list.set(random.nextInt(N), 10); } else { list.get(random.nextInt(N)); } } } }顺序读写的情况下，明显是ArrayList快，因为相对于O（1）的读取速度，和每次都是O（n）的读取速度。ArrayList的扩容导致的system.arraycopy()的性能可以忽略
如果是大数量顺序写的话LinkedList 明显要比ArrayList快，因为它不需要扩容。当然如果每一次都能预知到ArrayList的初始容量的话，复杂度也是一样的。
顺序读的话两种数据结构复杂度是O(n)
