ArrayList用数组实现了线性表。它用数组存储线性表的元素：
transient Object[] elementData;它也存储了线性表中元素的个数：private int size;接下来讲讲线性表的常见操作在ArrayList中的实现。
（1）查询线性表中是否包含某一个元素
public boolean contains(Object o) {return indexOf(o) >= 0;}contains(Object o)调用indexOf(Object o)来判断线性表是否包含某个元素，indexOf(Object o)的实现如下： public int indexOf(Object o) {// 分o等于和不等于null两种情况if (o == null) {// 遍历数组中的所有线性表元素，索引范围是[0，size)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;}// 如果不包含指定元素就返回-1return -1;}查询是否包含某一个元素需要遍历整个线性表，所以时间复杂度是O(n)。
（2）向线性表中插入元素
可以直接把一个元素添加到线性表的尾部：
public boolean add(E e) {// 保证数组的容量不小于线性表的长度ensureCapacityInternal(size + 1); // Increments modCount!!// 把元素添加到线性表最后一个元素的后面，并把线性表的长度加1elementData[size++] = e;return true;}也可以向线性表的指定位置添加元素： public void add(int index, E element) {// 保证index大于等于0，小于等于sizerangeCheckForAdd(index);// 保证数组容量不小于线性表长度ensureCapacityInternal(size + 1); // Increments modCount!!// 把elementData中index及后面的所有元素都移动一个位置System.arraycopy(elementData, index, elementData, index + 1,size – index);// 把待插入元素放到index处elementData[index] = element;size++;}把元素放到指定位置的操作的时间复杂度为O（n），，只要开销是移动元素。
（3）从线性表删除元素
删除指定位置的元素：
public E remove(int index) {// 保证index小于sizerangeCheck(index);modCount++;// 返回index处的元素E oldValue = elementData(index);// 需要移动的元素数目int numMoved = size – index – 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);// 线性表长度减1，并把size处的元素设置为null，让gc回收elementData[–size] = null; // clear to let GC do its workreturn oldValue;}elementData(int index)实现如下： E elementData(int index) {return (E) elementData[index];}删除指定元素： public boolean remove(Object o) {// 分o等于和不等于null两种if (o == null) {// 遍历线性表，如果找到与指定元素相等的元素，就将它删除for (int index = 0; index < size; index++)if (elementData[index] == null) {// 因为可以保证index合法，所以可以调用fastRemove(int index)fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}fastRemove(int index)实现如下： 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; // clear to let GC do its work}fastRemove(int index)和remove(int index)相比，只是少了边界验证和返回值。
两种删除元素的方式的时间复杂度都是O(n)，时间开销主要还是移动元素。
有时，明知错了，却欲罢不能，
