TOC
要想回答这个问题,可以先把各种都讲特性,然后再从底层存储结构,线程安全,默认大小,扩容机制,迭代器,增删改查效率这几个方向入手。
ArrayList
:动态数组,使用的时候,只需要操作即可,内部已经实现扩容机制。null
元素,且可以重复Vector
和前面说的ArrayList
很是类似,这里说的也是1.8版本,它是一个队列,但是本质上底层也是数组实现的。同样继承AbstractList
,实现了List
,RandomAcess
,Cloneable
, java.io.Serializable
接口。具有以下特点:RandomAcess
接口,这个接口主要是为List
提供快速访问的功能,也就是通过元素的索引,可以快速访问到。Cloneable
接口ArrayList
。AbstractSequentialList
,实现了List
,Queue
,Cloneable
,Serializable
,既可以当成列表使用,也可以当成队列,堆栈使用。主要特点有:List list = Collections.synchronizedList(new LinkedList());
List
接口,可以对它进行队列操作Queue
接口,可以当成堆栈或者双向队列使用Serializable
,可以被序列化和反序列化ArrayList
和Vector
底层都是数组结构,而LinkedList
在底层是双向链表结构。
ArrayList和LinkedList都不是线程安全的,但是Vector是线程安全的,其底层是用了大量的synchronized关键字,效率不是很高。
如果需要ArrayList和LinkedList是线程安全的,可以使用Collections类中的静态方法synchronizedList(),获取线程安全的容器。
ArrayList如果我们创建的时候不指定大小,那么就会初始化一个默认大小为10,DEFAULT_CAPACITY
就是默认大小。
private static final int DEFAULT_CAPACITY = 10;
Vector也一样,如果我们初始化,不传递容量大小,什么都不指定,默认给的容量是10:
public Vector() {
this(10);
}
而LinkedList底层是链表结构,是不连续的存储空间,没有默认的大小的说法。
ArrayList和Vector底层都是使用数组Object[]
来存储,当向集合中添加元素的时候,容量不够了,会触发扩容机制,ArrayList扩容后的容量是按照1.5倍扩容,而Vector默认是扩容2倍。两种扩容都是申请新的数组空间,然后调用数组复制的native函数,将数组复制过去。
Vector可以设置每次扩容的增加容量,但是ArrayList不可以。Vector有一个参数capacityIncrement,如果capacityIncrement大于0,那么扩容后的容量,是以前的容量加上扩展系数,如果扩展系数小于等于0,那么,就是以前的容量的两倍。
LinkedList
源码中一共定义了三个迭代器:
Itr
:实现了Iterator
接口,是AbstractList.Itr
的优化版本。ListItr
:继承了Itr
,实现了ListIterator
,是AbstractList.ListItr
优化版本。ArrayListSpliterator
:继承于Spliterator
,Java 8 新增的迭代器,基于索引,二分的,懒加载器。Vector
和ArrayList
基本差不多,都是定义了三个迭代器:
Itr
:实现接口Iterator
,有简单的功能:判断是否有下一个元素,获取下一个元素,删除,遍历剩下的元素ListItr
:继承Itr
,实现ListIterator
,在Itr
的基础上有了更加丰富的功能。VectorSpliterator
:可以分割的迭代器,主要是为了分割以适应并行处理。和ArrayList
里面的ArrayListSpliterator
类似。LinkedList
里面定义了三种迭代器,都是以内部类的方式实现,分别是:
ListItr
:列表的经典迭代器DescendingIterator
:倒序迭代器LLSpliterator
:可分割迭代器理论上,ArrayList
和Vector
检索元素,由于是数组,时间复杂度是O(1)
,在集合的尾部插入或者删除是O(1)
,但是其他的地方增加,删除,都是O(n)
,因为涉及到了数组元素的移动。但是LinkedList
不一样,LinkedList
不管在任何位置,插入,删除都是O(1)
的时间复杂度,但是LinkedList
在查找的时候,是O(n)
的复杂度,即使底层做了优化,可以从头部/尾部开始索引(根据下标在前一半还是后面一半)。
如果插入删除比较多,那么建议使用LinkedList
,但是它并不是线程安全的,如果查找比较多,那么建议使用ArrayList
,如果需要线程安全,先考虑使用Collections
的api
获取线程安全的容器,再考虑使用Vector
。
测试三种结构在头部不断添加元素的结果:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
addArrayList();
addLinkedList();
addVector();
}
public static void addArrayList(){
List list = new ArrayList();
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
public static void addLinkedList(){
List list = new LinkedList();
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
public static void addVector(){
List list = new Vector();
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
}
测出来的结果,LinkedList最小,Vector费时最多,基本验证了结果:
ArrayList:7715
LinkedList:111
Vector:8106
测试get的时间性能,往每一个里面初始化10w个数据,然后每次get出来:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
getArrayList();
getLinkedList();
getVector();
}
public static void getArrayList(){
List list = new ArrayList();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.get(i);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
public static void getLinkedList(){
List list = new LinkedList();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.get(i);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
public static void getVector(){
List list = new Vector();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.get(i);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
}
测出来的时间如下,LinkedList
执行get
操作确实耗时巨大,Vector
和ArrayList
在单线程环境其实差不多,多线程环境会比较明显,这里就不测试了:
ArrayList : 18
LinkedList : 61480
Vector : 21
测试删除操作的代码如下,删除的时候我们是不断删除第0个元素:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
removeArrayList();
removeLinkedList();
removeVector();
}
public static void removeArrayList(){
List list = new ArrayList();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.remove(0);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
public static void removeLinkedList(){
List list = new LinkedList();
for(int i=0;i<100000;i++){
list.add(0,i);
}
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.remove(0);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
public static void removeVector(){
List list = new Vector();
for(int i=0;i<100000;i++){
list.add(i);
}
long startTime = System.nanoTime();
for(int i=0;i<100000;i++){
list.remove(0);
}
long endTime = System.nanoTime();
System.out.println((endTime-startTime)/1000/60);
}
}
测试结果,LinkedList确实效率最高,但是Vector
比ArrayList
效率还要高。因为是单线程的环境,没有触发竞争的关系。
ArrayList: 7177
LinkedList: 34
Vector: 6713
下面来测试一下,vector多线程的环境,首先两个线程,每个删除5w元素:
package com.aphysia.offer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
removeVector();
}
public static void removeVector() {
List list = new Vector();
for (int i = 0; i < 100000; i++) {
list.add(i);
}
Thread thread1 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 50000; i++) {
list.remove(0);
}
}
});
Thread thread2 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 50000; i++) {
list.remove(0);
}
}
});
long startTime = System.nanoTime();
thread1.start();
thread2.start();
while (!list.isEmpty()) {
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000 / 60);
}
}
测试时间为:12668
如果只使用一个线程,测试的时间是:8216,这也从结果说明了确实Vector
在多线程的环境下,会竞争锁,导致执行时间变长。
【刷题笔记】 Github仓库地址:https://github.com/Damaer/codeSolutionundefined笔记地址:https://damaer.github.io/codeSolution/
【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:Java源码解析,JDBC,Mybatis,Spring,redis,分布式,剑指Offer,LeetCode等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。
平日时间宝贵,只能使用晚上以及周末时间学习写作,关注我,我们一起成长吧~
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。