Java中Arraylist的add（）和remove（）方法

Java中Arraylist的add（）和remove（）方法

虽然ArrayList是可变数组，但是为了提高性能我们在使用中应尽量提前估算容量，add()的时间复杂度为O(1),但是扩容会拉低性能，所以定义时应估算容量，减少扩容次数；remove()方法,每次删除要移动后边数组，所以时间复杂度为O(n)，为提高性能，尽可能删除最后的数据。

一.Add()源码解析 数组扩容这是对ArrayList效率影响比较大的一个因素，虽然ArrayList可以自己扩容，但是扩容过程的空间复杂度应该是O(2n)，因为 需要拷贝一个次旧的数组。

现在看一下源码：

构造函数

new ArrayList()返回的是一个空的Object,所以新建的ArrayList初始容量为零。

new ArrayList(K)当K>0时，开辟K个空间；K=0，返回空的Object。

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; 
private int size;
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);}
}

接下来看一下add()函数。ArrayList首次扩容，容量为10，以后每次扩容将新开辟空间，容量将会增加为原来的1.5倍，再将原来的数组复制到新的空间。

 public boolean add(E e) {ensureCapacityInternal(size + 1);//add，长度+1，增量后调用下边函数elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//如果数组为空的话，min=Math.max(10,1)=10;minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}//调用下方函数ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;//数组长度<10,add后的长度大于现有的数组长度,说明数组应该扩容了，调用下方函数if (minCapacity - elementData.length > 0)grow(minCapacity);}
//扩容函数private void grow(int minCapacity) {// overflow-conscious code//获取旧数组长度int oldCapacity = elementData.length;//新数组长度=原来的1.5倍；通过右移1位，即oldCapacity/2int 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://拷贝，new 新的长度的数组，赋值 elementData = pyOf(elementData, newCapacity);}

二.remove()的注意问题
每次删除一个数，后边的元素会往前移动，所以remove()方法有一些坑大家会忽略掉。

比如下面的代码，想要将偶数删除，输出结果是？

@Test
public void testRemove2(){List<Integer> integers = new ArrayList<>(5);integers.add(1);integers.add(2);integers.add(2);integers.add(4);integers.add(5);

for (int i = 0; i < integers.size(); i++) {if ((i)%2==0){ve(i);}
}System.out.println(integers);

}
结果是：

[1,2,5]
显然，结果和需求是不相符的。因为在删除第一个 2 的时候，后边的数字统一往前移动，但是下标 i 会继续+1，所以下一次循环 i 指向的是 4 ，所以第二个2根本没有执行 if 代码块，自然没有删除。

下面的代码也是很常见的错误写法：

@Test
public void testRemove5(){List<String> strings = new ArrayList<>();strings.add("a");strings.add("b");strings.add("c");strings.add("d");

int size = strings.size();
for (int i = 0; i < size; i++) {ve(i);
}

}
数组size是变化的，用遍历size长度肯定是不对的，所以运行结果会报错。

正确写法如下：使用Iterator遍历删除是最安全的。

@Test
public void testRemove7(){List<String> strings = new ArrayList<>();strings.add("a");strings.add("b");strings.add("c");strings.add("d");

Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){String next = ();ve();
}System.out.println(strings);

}

转发来源：