✨前言✨
本篇作为,java集合中 ArrayList,LinkedList,Vector常用集合的分析概括,已便大家认识这三种集合的区别,和特点
?欢迎点赞 ? 收藏 ⭐留言评论 ?私信必回哟?
?博主将持续更新学习记录收获,友友们有任何问题可以在评论区留言
@
?一,特性列举
ArrayList 集合
动态数组,使用的时候,只需要操作即可,内部已经实现扩容机制。
- 线程不安全
- 有顺序,会按照添加进去的顺序排好
- 基于数组实现,随机访问速度快,插入和删除较慢一点
- 可以插入null元素,且可以重复
LinkedList 集合
链表结构,继承了AbstractSequentialList,实现了List,Queue,Cloneable,Serializable,既可以当成列表使用,也可以当成队列,堆栈使用
- 线程不安全,不同步,如果需要同步需要使用List list = Collections.synchronizedList(new
LinkedList()); - 实现List接口,可以对它进行队列操作
- 实现Queue接口,可以当成堆栈或者双向队列使用
- 实现Cloneable接口,可以被克隆,浅拷贝
- 实现Serializable,可以被序列化和反序列化
Vector 集合
Vector和前面说的ArrayList很是类似,这里说的也是1.8版本,它是一个队列,但是本质上底层也是数组实现的。同样继承AbstractList,实现了List,RandomAcess,Cloneable, java.io.Serializable接口
- 提供随机访问的功能:实现RandomAcess接口,这个接口主要是为List提供快速访问的功能,也就是通过元素的索引,可以快速访问到。
- 可克隆:实现了Cloneable接口
- 是一个支持新增,删除,修改,查询,遍历等功能。
- 可序列化和反序列化
- 容量不够,可以触发自动扩容
- *最大的特点是:线程安全的,相当于线程安全的ArrayList
?二,底层存储结构不同
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。
测试:
1,测试三种结构在头部不断添加元素的结果
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("ArrayList:"+(endTime-startTime));
}
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("LinkedList:"+(endTime-startTime));
}
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("Vector:"+(endTime-startTime));
}
测出来的结果: LinkedList最小,Vector费时最多,基本验证了结果:
ArrayList:514182
LinkedList:8364
Vector:551264
2,测试get的时间性能,往每一个里面初始化10w个数据,然后每次get出来:
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("ArrayList:"+(endTime-startTime)/1000);
}
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("LinkedList:"+(endTime-startTime)/1000);
}
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("Vector:"+(endTime-startTime)/1000);
}
测出来的时间如下,LinkedList 执行get操作确实耗时巨大,Vector和ArrayList在单线程环境其实差不多。
ArrayList:1341
LinkedList:4204161
Vector:1899
3,测试删除操作的代码如下,删除的时候我们是不断删除第0个元素:
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("ArrayList:"+(endTime-startTime)/1000);
}
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("LinkedList:"+(endTime-startTime)/1000);
}
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("Vector:"+(endTime-startTime)/1000);
}
测试结果: LinkedList确实效率最高,但是Vector比ArrayList效率还要高。因为是单线程的环境,没有触发竞争的关系。
ArrayList:558208
LinkedList:2523
Vector:450226
?八,总结
ArrayList
- 底层是数组,扩容就是申请新的数组空间,复制
- 线程不安全
- 默认初始化容量是10,扩容是变成之前的1.5倍
- 查询比较快
LinkedList
- 底层是双向链表,可以往前或者往后遍历
- 没有扩容的说法,可以当成双向队列使用
- 增删比较快
- 查找做了优化,index如果在前面一半,从前面开始遍历,index在后面一半,从后往前遍历
Vector
- 底层是数组,几乎所有方法都加了Synchronize
- 线程安全
- 有个扩容增长系数,如果不设置,默认是增加原来长度的一倍,设置则增长的大小为增长系数的大小。
✨最后✨
总结不易,希望uu们不要吝啬你们的?哟(^U^)ノ~YO!!
如有问题,欢迎评论区批评指正?
- 相同点 LinkedList ArrayList Vector Java相同点linkedlist arraylist vector linkedlist arraylist vector java 相同点linkedlist arravlist vector linkedlist arraylist框架vector linkedlist arraylist vector list linkedlist arraylist vector linkedlist arraylist java linkedlist arraylist java p11 linkedlist arraylist arraylist机制vector