深入了解Java 集合类(二):ArrayList和LinkedList 时间复杂度
List
List接口在Collection的基础上添加了大量的方法,生成了一个元素有序、可重复的集合,集合中每个元素都有其对应的顺序索引,可以通过索引来访问指定位置的集合元素,主要类型有以下两种:
-
ArrayList
ArrayList是基于数组实现的List类,它封装了一个动态的增长的、允许再分配的Object[]数组,查询、随机访问速度快,插入和移除元素时较慢(很多资料都是这样说的,真的如此吗),实现的接口有:Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
-
LinkedList
LinkedList是基于链表实现的List类,它的随机访问速度相对较慢,但是它进行删除插入操作会很快,实现的接口有Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>
另外补充一点,Vector作为一个非常古老的集合,也是List的一个典型实现类,完全支持List的全部功能,与ArrayList的主要是区别是:Vector是线程安全的,但是性能比ArrayList要低。
ArrayList和LinkedList的区别
上面简单提过,ArrayList和LinkedList的区别主要体现在访问、插入删除等操作速度上的不同,那么它们究竟是怎样的不同,各个操作的具体时间复杂度是多少呢?LinkedList的插入速度真的就比ArrayList快吗,下面我们将根据源码和一个例子来进行详细分析:
ArrayList的部分源码如下:
//获取index位置的元素值
public E get(int index) {
rangeCheck(index); //首先判断index的范围是否合法
return elementData(index);
}
//将index位置的值设为element,并返回原来的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//将element添加到ArrayList的指定位置
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index以及index之后的数据复制到index+1的位置往后,即从index开始向后挪了一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element; //然后在index处插入element
size++;
}
//删除ArrayList指定位置的元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//向左挪一位,index位置原来的数据已经被覆盖了
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//多出来的最后一位删掉
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
LinkedList的部分源码如下:
//获得第index个节点的值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//设置第index元素的值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//在index个节点之前添加新的节点
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//删除第index个节点
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//定位index处的节点
Node<E> node(int index) {
// assert isElementIndex(index);
//index<size/2时,从头开始找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //index>=size/2时,从尾开始找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
分析源码,我们可以看出,对于查询操作:
ArrayList想要查询某一个元素时,由于它的索引是排好序的,因此通过get(int index)的方法,直接返回index位置上的元素。也就是查询任意一个元素的时间复杂度都为,查询整个集合的时间复杂度为。
而基于链表实现的LinkedList类,只知道链表指针指向的下一个元素,所以需要通过for循环从头或尾开始查找(JDK中的LinkedList在查找方法上做了优化,查询时先计算index在前一半还是后一半,比如index < size / 2,则从左边开始查找,反之从右边开始查找),一共查找次数为:
LinkedList遍历元素的时间复杂度为。
对于添加删除操作:
ArrayList想要在指定位置插入或删除元素时,index后面的所有元素都需要向右移动。所以最好情况下(在尾部插入)时间复杂度是,最坏情况下(在头部插入)时间复杂度是。
LinkedList想要在指定位置插入或删除元素时,只需修改元素上下指针的指向就行,时间复杂度均为。这样是不是就可以说LinkedList在插入删除时比 ArrayList效率更高?No~,因为LinkedList在插入删除操作前需要通过for循环找到该处索引的元素。
那么,在不同索引处添加一组元素时,ArrayList和LinkedList的耗时情况如何?请看下面的例子。
随机生成长度n=100000的ArrayList和LinkedList列表,进行以下操作:
- 在索引 i=10000 处添加10000组元素;
- 在索引 i=50000 处添加10000组元素;
- 在索引 i=99999 处添加10000组元素;
代码如下:
package com.yang.list;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class ListTest {
public static void main(String[] args) {
//生成size为100000的ArrayList和LinkedList列表
ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i=0; i<100000; i++) {
arrayList.add(i);
linkedList.add(i);
}
System.out.println("添加ArrayList的时间:" + addTime(arrayList));
System.out.println("添加LinkedList的时间:" + addTime(linkedList));
System.out.println("遍历ArrayList的时间:" + traversalTime(arrayList));
System.out.println("遍历LinkedList的时间:" + traversalTime(linkedList));
}
//统计添加100000个元素的时间
public static long addTime(List<Integer> list) {
Random random = new Random();
long startTime = System.currentTimeMillis();
for (int index=0; index<10000; index++) {
list.add(99999, random.nextInt());
}
return (System.currentTimeMillis() - startTime);
}
//统计遍历100000个元素的时间
public static long traversalTime(List<Integer> list) {
long startTime = System.currentTimeMillis();
for (int index=0; index<list.size(); index++) {
list.get(index);
}
return (System.currentTimeMillis() - startTime);
}
}
输出结果:
i=10000
添加ArrayList的时间:161
添加LinkedList的时间:198
遍历ArrayList的时间:5
遍历LinkedList的时间:5402
i=50000
添加ArrayList的时间:116
添加LinkedList的时间:943
遍历ArrayList的时间:5
遍历LinkedList的时间:5497
i=90000
添加ArrayList的时间:22
添加LinkedList的时间:267
遍历ArrayList的时间:4
遍历LinkedList的时间:5402
可以看出,在遍历查询列表元素时,ArrayList耗时明显比LinkedList小很多;但是对于插入和删除,并不是LinkedList一定比ArrayList快。
为了更直观的看出它们在不同索引处的耗时情况,我们从 index=0 开始,每隔5000统计一组耗时情况,共21组,绘制成折线图:
从上图可以看出,
- 在 index=0 时,LinkedList的耗时仅为1,而ArrayList的耗时接近200,差不多是LinkedList的200倍;
- 随着index值的不断增大,ArrayList的耗时在不断变小;
- 随着index值的不断增大,LinkedList的耗时先增大,到 index=50000左右时达到最大,然后开始减小;
- 在index值等于5000-10000的某个值时,ArrayList和LinkedList的耗时一样。