ArrayList的线性复杂度是1.想确定一个数据,直接通过索引进行访问.实际上这个过程和数组是非常相似的.ArrayList在整个使用过程中,如果想要高效操作,最好设置一个数组的大小.

在个数固定的情况下,ArrayList里面避免了重复开辟空间的问题,所以当你确定数据个数的时候,就使用ArrayList.

如果不确定的时候就使用LinkedList(链表实现). 时间复杂度是N ,而ArrayList最底层的原理就是一个数组的动态操作.

数组本身的最大问题在于数组的容量是固定的,而ArrayList通过自己的算法实现动态扩增.

ArrayList的add方法:

1     public boolean add(E e) { 2         ensureCapacityInternal(size + 1);  // Increments modCount!! 3         elementData[size++] = e; 4         return true; 5     } 6      private void ensureCapacityInternal(int minCapacity) { 7         if (elementData == EMPTY_ELEMENTDATA) { 8             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 9         }10 11         ensureExplicitCapacity(minCapacity);12     }13     private void ensureExplicitCapacity(int minCapacity) {14         modCount++;15 16         // overflow-conscious code17         if (minCapacity - elementData.length > 0)18             grow(minCapacity);19     }

ArrayList是一个相对来说比较简单的数据结构，最重要的一点就是它的自动扩容，可以认为就是我们常说的“动态数组”。

我们可以看到他的实现其实最核心的内容就是ensureCapacityInternal。这个函数其实就是自动扩容机制的核心。我们依次来看一下他的具体实现

也就是说，当增加数据的时候，如果ArrayList的大小已经不满足需求时，那么就将数组变为原长度的1.5倍，之后的操作就是把老的数组拷到新的数组里面。例如，默认的数组大小是10，也就是说当我们add10个元素之后，再进行一次add时，就会发生自动扩容，数组长度由10变为了15.