由上图可以看出ArrayList底层是根据数组实现的。
1、查询：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
通过源码可以看出get方法直接根据索引到数组中查询即可，效率高
2、插入操作：
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++;
}
查看源码可以看出，将elementData数组中的数组从index位置复制到elementData的index + 1位置。
(相当于从index开始，数组内容往后移动一位)
elementData[index] = element;将index出的数组内容，复制给新的值，这样实现了插入操作。
可以看出插入操作需要移动数组内容，效率低。
3、添加操作：
ArrayList源码
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(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);
}
上面add的代码很简单：
ensureCapacityInternal(size + 1);这一行就是保证数组的长度要大于存储元素的长度
elementData[size++] = e;这一行就是将添加的元素赋值给了数组的下一个空间。
主要要看ensureCapacityInternal方法：
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
如果默认new ArrayList();初始化的时候是给一个长度为0的空数组，
这行主要是判断如果是空数组，默认长度为DEFAULT_CAPACITY（10）
接下来进入ensureExplicitCapacity方法
如果minCapacity最小的长度大于elementData.length（数组的长度）
进入grow方法（数组扩容）
int newCapacity = oldCapacity + (oldCapacity >> 1);这行算出新的数组长度
相当于int newCapacity = oldCapacity + (oldCapacity / 2)
也就是说newCapacity = oldCapacity * (1.5)
扩容50%的意思
elementData = Arrays.copyOf(elementData, newCapacity);创建一个新的数组并elementData（旧的数组值赋值到新的数组）并赋值给elementData。
以上代码：可以看出一旦元素的内容超过ArrayList内数组的容量，那么需要进行数组内容的移动，也是效率低的操作。
4、删除操作：
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
System.arraycopy(elementData, index+1, elementData, index,numMoved);这里将index+1之后的数组内容复制到elementData
相当于将index之后的数组内容往前移一位（挤掉要删除的值）
查看源码可以得知，删除操作要移动数组内容，效率低。
5、修改操作
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
查看源码可以得知，修改操作直接通过索引操作数组内容，效率高。
总结：ArrayList底层是数组结构，查询，修改效率高。增加，插入，删除效率低。
手写模拟代码：
package com.yidu.demo;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Vector;
import org.omg.Messaging.SyncScopeHelper;
/**
* 模拟数组集合(底层数组实现)
* @author Administrator
*/
public class Array{
private Object[] elementsData;
private int size;
//构造方法，初始化数组
public Array(){
this(10);
}
public Array(int initialCapacity){
if(initialCapacity<1){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
elementsData=new Object[initialCapacity];
}
public void add(Object obj){
//数组扩容
ensureCapacityInternal();
elementsData[size++]=obj;
}
public void add(int index,Object obj){
rangeCheck(index);
//数组扩容
ensureCapacityInternal();
System.arraycopy(elementsData, index, elementsData, index+1, size-index);
elementsData[index]=obj;
size++;
}
public Object get(int index){
rangeCheck(index);
return elementsData[index];
}
public void remove(int index){
rangeCheck(index);
System.arraycopy(elementsData, index+1, elementsData, index, size-index-1);
elementsData[--size]=null;
}
public void remove(Object obj){
if(obj==null){
for (int i = 0; i < elementsData.length; i++) {
if(elementsData[i]==obj){
System.arraycopy(elementsData, i+1, elementsData, i, size-i-1);
elementsData[--size]=null;
break;
}
}
}else{
for (int i = 0; i < elementsData.length; i++) {
if(elementsData[i].equals(obj)){
System.arraycopy(elementsData, i+1, elementsData, i, size-i-1);
elementsData[--size]=null;
break;
}
}
}
}
public void set(int index,Object obj){
rangeCheck(index);
elementsData[index]=obj;
}
private void rangeCheck(int index){
if(index>=size||index<0){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
}
private void ensureCapacityInternal(){
if(size==elementsData.length){
Object[] newArr=new Object[size*2];
//将旧数组拷贝到新数组
System.arraycopy(elementsData, 0, newArr, 0, elementsData.length);
elementsData=newArr;
}
}
public static void main(String[] args) {
Array a=new Array();
for (int i = 0; i < 21; i++) {
a.add(i);
}
System.out.println(a.size);
}
}
