前言
List家族常用的类有3个,ArrayList、LinkedList、Vector。
ArrayList和Vector的底层是基于数组实现的,LinkedList的底层是基于链表实现的。
三者的比较如下:
- ArrayList和LinkedList不是线程安全的,Vector是线程安全的。
- 对于随机访问(get和set),ArrayList的性能要优于LinkedList。
- 对于add和remove操作,LinkedList和ArrayList性能差距不是很大。
- 三者均实现了Collection接口。
分析
UML图
三者与其他类的继承实现关系UML图如下。
ArrayList:
LinkedList:
Vector:
源码分析
核心实现
ArrayList是基于数组实现。
1 | transient Object[] elementData; |
LinkedList是基于链表实现。
1 | transient int size = 0; |
Vector是基于数组实现。
1 | protected Object[] elementData; |
核心参数
ArrayList 可以设置初始大小(由于数组实现的原因),不设置默认为10。
LinkedList不需要设置参数(由于使用链表实现,无界)。
Vector不仅可以设置初始大小,还可以设置容量增幅。
1 | //ArrayList传参构造函数 |
关于初始化大小和扩容机制下面讲。
核心方法
我们主要分析get、set、add、remove这几个方法。对于ArrayList和Vector,还要分析扩容方法。
get、set方法
ArrayList get,set方法:
1 | public E get(int index) { |
Vector get,set方法:
1 | public synchronized E get(int index) { |
二者的逻辑一样,get方法判断是否下标越界,不越界返回index下的数值。set方法判断是否越界,不越界将新值放到指定下标上。它俩的区别在与synchronized关键字,正好说明了Vector是线程安全的。
LinkedList get,set方法:
1 | public E get(int index) { |
可以看到LinkedList的get方法会先检查是否越界,不越界返回指定下标node的item值。
set方法也是先检查越界情况,不越界将该点的node的item赋为新值。取node指定位置上的值时要循环遍历,所以对于随机的get,set,ArrayList的性能要优于LinkedList的。
add、remove方法
ArrayList add、remove方法:
1 | public boolean add(E e) { |
Vector add、remove方法:
1 | public synchronized boolean add(E e) { |
它们里面有add、remove方法不止一个,我们只拿一个来举例。
可以看到,Vector和ArrayList十分相近了,除了synchronized关键字。
add方法当elementData.length和elementCount相等时(容量满),会执行扩容操作,并将元素放到指定位置。
remove方法先判断下标是否越界,不越界会删除指定位置的元素,并且将数组重新拷贝合并。
同时它们有一个计数器modCount,在HashMap那边已经讲过,是用来fast-fail的,当多个线程同时操作,modCount不一致,就会抛出异常。
LinkedList的add、remove方法:
1 | public void add(int index, E element) { |
可以看到,LinkedList的add方法开始也会校验指针位置,然后如果在末尾,就在链表最后面添加节点,否则就插入到链表指定位置上。
remove方法校验指针位置后,会删除指定位置上的node。
上面可以看到,对于add和remove,ArrayList数组要进行扩容或者删除部分长度,执行Sysetm.arraycopy方法,这是要消耗一些性能的,对于LinkedList,不需要维护容量问题,但是每次新增或者删除时,都会创建或删除一个Node对象,也是要消耗一些性能的。
扩容方法
对于ArrayList或者Vector,扩容方法如下:
ArrayList 扩容方法:
1 | private static final int DEFAULT_CAPACITY = 10; |
Vector扩容方法:
1 | public Vector() { |
上面代码可以看到,对于ArrayList,如果不传入初始容量,默认为10。容量达到最值,执行扩容,每次扩容 int newCapacity = oldCapacity + (oldCapacity >> 1);
默认原容量的1.5倍。
Vector,如果不传入初始容量和自增容量,默认初始容量也为10.扩容时执行
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);
默认为原容量的2倍。
两者的最大值容量均为Integer.MAX_VALUE.
LinkedList由于是链表实现,没有容量限制。无需扩容。
代码
我们从代码的角度比较下ArrayList和LinkedList,Vector。
我们构建一个有200W数据的ArrayList和LinkedList。
1 | public static void main(String[] args){ |
某一次的结果:
数组 | forEach遍历 | Iterator遍历 | for遍历 |
---|---|---|---|
ArrayList | 9ms | 9ms | 12ms |
LinkedList | 17ms | 16ms | ??? |
Vector | 44ms | 55ms | 41ms |
由于for循环遍历是随机访问,故LinkedList在数据量很大的情况下时间消耗会很长,基本不能接受。由于Vector线程安全,synchronized,故其整体效率会比ArrayList低些。在实际开发中,应用的ArrayList还是比较多的。
结语
以上就是对ArrayList、LinkedList、Vector的全部分析。对于不同的应用场景,合理的选择List的类型也是至关重要的。三种List都是比较基础的知识,应当学习和掌握。