结果：ArrayList----time:2493
public static void main(String[] args) {
List list = new ArrayList<>(1100 * 10000);
int size = 1000 * 10000;
Long time1 = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
Long time2 = System.currentTimeMillis();
System.out.println(“ArrayList----time:” + (time2 - time1));
}
结果：ArrayList----time:560
public static void main(String[] args) {
List list = new linkedList<>();
int size = 1000 * 10000;
Long time1 = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
Long time2 = System.currentTimeMillis();
System.out.println(“linkedList----time:” + (time2 - time1));
}
结果：linkedList----time:6302
结论：在数据量足够大的情况下，设置ArrayList的初始值要比没设置的添加速度快。但是初始值n并不是越大越好，如果设置过大，有可能会造成内存溢出，反而添加速度更慢。
但是如果ArrayList数据量特别小的情况下，二则相差无几，当然对计算机而言，如果没触发扩容二者都一样，如果触发了，就要比对谁触发的次数多，移动的数据量大。
相对ArrayList而言，linkedList的添加速度慢，慢了差不多三倍。
1.2、添加和删除哪一个更加高效？
public static void main(String[] args) {
List list = new ArrayList<>();
int size = 10 * 10000;
Long time1 = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
Long time2 = System.currentTimeMillis();
System.out.println(“add----time:” + (time2 - time1));
for (int i = 0; i < list.size(); i++) {
list.remove(i);
i–;
}
Long time3 = System.currentTimeMillis();
System.out.println(“remove----time:” + (time3 - time2));
}
结果：
add----time:5
remove----time:566
// linkedList正序坐标删除
public static void main(String[] args) {
List list = new linkedList<>();
int size = 10 * 10000;
Long time1 = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
Long time2 = System.currentTimeMillis();
System.out.println(“add----time:” + (time2 - time1));
for (int i = 0; i < list.size(); i++) {
list.remove(i);
i–;
}
Long time3 = System.currentTimeMillis();
System.out.println(“remove----time:” + (time3 - time2));
}
结果：
add----time:4
remove----time:3
// linkedList逆序坐标删除
public static void main(String[] args) {
List list = new linkedList<>();
int size = 10 * 10000;
Long time1 = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》
【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享
Long time2 = System.currentTimeMillis();
System.out.println(“add----time:” + (time2 - time1));
for (int i = 0; i < list.size(); i++) {
list.remove(list.size() - i - 1);
i–;
}
Long time3 = System.currentTimeMillis();
System.out.println(“remove----time:” + (time3 - time2));
}
结果：
add----time:6
remove----time:3
// linkedList逆序对象删除
public static void main(String[] args) {
List list = new linkedList<>();
int size = 10 * 10000;
Long time1 = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
Long time2 = System.currentTimeMillis();
System.out.println(“add----time:” + (time2 - time1));
for (int i = 0; i < list.size(); i++) {
Integer integer = list.get(list.size() - i - 1);
list.remove(integer);
i–;
}
Long time3 = System.currentTimeMillis();
System.out.println(“remove----time:” + (time3 - time2));
}
结果：
add----time:6
remove----time:12107
ArrayList因为添加触发到扩容，最终执行的是System.arraycopy本地方法，执行速度相对较快，但删除需要进行数据移动，所以执行效率低。
linkedList正序坐标删除和逆序坐标删除，时间效率都一样，逆序坐标删除是因为程序做了特殊处理，但是如果是逆序对象删除的话，运行效率就会特别差，原理后面再介绍。
1.3、内存使用情况如何？
public static void main(String[] args) {
List list = new ArrayList<>();
int size = 100 * 10000;
for (int i = 0; i < size; i++) {
list.add(i);
}
System.out.println(“memory:”+ RamUsageEstimator.humanSizeOf(list));
}
结果：memory:19.9 MB
public static void main(String[] args) {
List list = new linkedList<>();
int size = 100 * 10000;
for (int i = 0; i < size; i++) {
list.add(i);
}
System.out.println(“memory:”+ RamUsageEstimator.humanSizeOf(list));
}
结果：memory:38.1 MB
同等size大小的集合，显然linkedList要比ArrayList更吃内存，所以如果是超大集合存储的话，要留意内存使用情况。
二、源码分析
2.1、ArrayList源码
2.1.1、add()
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, 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);
}
public static
@SuppressWarnings(“unchecked”)
T[] copy = ((Object)newType == (Object)Object[].class)
-
? (T[]) new Object[newLength]
- (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
ArrayList的add()方法本质就是数组中设置值，这没什么好说的，重点在于扩容，当数组size达到扩容标准后，就会触发System.arraycopy进行数组复制，这对时间和空间上都会有一定的影响。
2.1.2、remove()
// 坐标删除
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;
}
// 对象删除
public boolean remove(Object o) {
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;
}
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
}
