Java深究之Vector、ArrayList、LinkedList的区别

Wesley13
• 阅读 593

        在java开发中除了上文经常用的对字符串的操作外,还有使用居多的当属集合了。在基础的java学习时,相信很多同学都学习了List、Set、Map这些,他们之间的区别和基本的使用方法也是很了解了,本文是详细的去分析List中Vector、ArrayList、LinkedList之间的区别和底层实现原理以及使用场景

首先说下这三者的区别:

1.基本区别:三个类都实现了List接口,都是有序集合,数据是允许重复的;ArrayList 和Vector都是基于数组实现存储的,集合中的元素的位置都是有顺序即连续的;LinkedList是基于双向链表实现存储的集合中的元素的位置是不连续的

2.性能区别:Vector和ArrayList底层实现原理一致,但是Vector是线程安全的,因此性能比ArrayList差很多;LinkedList相比于集合Vector和ArrayList在插入,修改,删除等操作上速度较快,但是随机访问的性能较差

3.安全区别:Vector是使用了synchronized同步锁是线程安全的,ArrayList和LinkedList都是线程不安全的

4.原理区别:ArrayList与Vector都有初始的容量大小,当存储的元素的个数超过了容量时,就需要增加存储空间,Vector默认增长为原来两倍,而ArrayList的增长为原来的1.5倍;ArrayList与Vector都可以设置初始空间大小,Vector还可以设置增长的空间大小,而ArrayList没有提供设置增长空间的方法

然后详细分析每一个的原理:

1.Vector

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

从源码可以看出Vector的初始默认空间大小为10,底层使用protected Object[] elementData;存储数据,使用protected int elementCount;存储元素数量,Vector的方法都被synchronized关键字修饰,因此是线程安全的。

接下来我们从源码上看下Vector的添加元素时以及初始容量不足时的扩容机制:

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

当创建一个Vector容器,向其中添加一个元素是,首先会调用ensureCapacityHelper函数判断容器存储容量,如果容量不足则会调用grow函数扩容,上面我们说的扩展为原来的两倍,其实不是非常准确,因为当设置了扩容参数值,则就不是扩展为两倍了,而是原来的长度加上扩容参数值,默认情况下还是扩展为原来的两倍。

2.ArrayList

Java深究之Vector、ArrayList、LinkedList的区别

ArrayList的初始容量大小也是10,和Vector的原理是完全一样的,只是不是线程安全的,我们这里主要看下ArrayList的扩容原理:

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

ArrayList也是会先判断容器的容量大小,如果容量不足,则调用扩容方法grow函数,将容量扩展原来加原来一半也就是1.5倍

3.LinkedList

Java深究之Vector、ArrayList、LinkedList的区别

LinkedList是一个继承于AbstractSequentialList的双向链表,它也可以被当作堆栈、队列或双向队列进行操作。LinkedList实现 List 接口,能对它进行队列操作。LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。LinkedList 是非同步的(线程不安全的)。因为是双向链表,所以它的顺序访问会非常高效,而随机访问效率比较低。

Java深究之Vector、ArrayList、LinkedList的区别

下面我们先看下LinkedList的添加元素的原理:

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

我们从源码可以看到其实add添加元素的操作就是在容器的最后新增一个数据节点,具体分析:先把当前最后一个节点存档到l数据节点中,然后新增一个数据节点,这里有一个判断,如果l为空那就是说改链表是空的,这样这个新增元素即是第一个也是最后一个节点;如果l不为空,将当前最后一个节点变成新增的前一个节点,然后last存放新增节点使其变成最后一个元素节点,这样一个新增的操作就完成了。

Java深究之Vector、ArrayList、LinkedList的区别

我们再来看看向制定位置添加数据节点的原理,看下面源码:

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

首先是位置是否存在,添加元素的位置必须是大于等于0小于等于链表的大小;然后判断如果要添加元素的位置等于链表的大小,则该元素插入最有一个即可,否则在指点的位置前插入节点,先将该位置前的阶段存起来到pred,然后判断如果pred为空说明该链表是空的,则将新增数据节点写入第一个节点中,如果pred不为空,将原来的前一个节点的下一个节点指向新添加的节点,将新添加节点的下一个节点指向原来位置的下一个节点即可

Java深究之Vector、ArrayList、LinkedList的区别

接下来我们看下删除第一个节点元素:

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

删除时是先把原来的第一个节点的下一个节点存到first中,然后将第一个节点的指向都设置为null(删除),然后将first指向next就可以了,然后判断如果next为空则last设置为空,这时候整个链表也就是空的;反之释放next内存;然后将链表大小减小一个,将此列表已被结构修改的次数减一

接下来我们看下删除最后一个节点元素:

Java深究之Vector、ArrayList、LinkedList的区别

Java深究之Vector、ArrayList、LinkedList的区别

删除最后一个元素是相对简单一些,删除最后一个节点,然后释放该节点指向前一个节点的指针空间和释放前一个节点指向下一个节点的指针空间,然后将链表大小减小一个,将此列表已被结构修改的次数减一

Java深究之Vector、ArrayList、LinkedList的区别

点赞
收藏
评论区
推荐文章
技术小男生 技术小男生
1个月前
linux环境jdk环境变量配置
1:编辑系统配置文件vi /etc/profile2:按字母键i进入编辑模式,在最底部添加内容: JAVAHOME/opt/jdk1.8.0152 CLASSPATH.:$JAVAHOME/lib/dt.jar:$JAVAHOME/lib/tools.jar PATH$JAVAHOME/bin:$PATH3:生效配置
光头强的博客 光头强的博客
1个月前
Java面向对象试题
1、 请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。 创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现 接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿 吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
Wesley13 Wesley13
1年前
Java常见面试题总结
一、Java基础 1、String类为什么是final的。 2、HashMap的源码,实现原理,底层结构。 3、说说你知道的几个Java集合类:list、set、queue、map实现类咯。。。 4、描述一下ArrayList和LinkedList各自实现和区别 5、Java中的队列都有哪些,有什么区别。 6、反射中,Class.forName和
Stella981 Stella981
1年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置 1、virsh edit centos7 找到“memory”和“vcpu”标签,将 <name>centos7</name> <uuid>2220a6d1-a36a-4fbb-8523-e078b3dfe795</uuid>
Wesley13 Wesley13
1年前
Java集合面试题
**Collection** Set和hashCode以及equals方法的联系 Set内存放的元素为什么不可以重复,内部是如何保证和实现的? List 和 Set 区别 List 和 Map 区别 Arraylist 与 LinkedList 区别 ArrayList 与 Vector 区别 Arraylist与LinkedList默认空间是
Easter79 Easter79
1年前
Twitter的分布式自增ID算法snowflake (Java版)
概述 == 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。 有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。 而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
1年前
java 面试
###### 1 、ArrayList、Vector、LinkedList 之间的 区别? ArrayList:底层数组,查询快,增删慢,线程不安全,效率高 Vector:底层数组,查询快(由于线程安全,其实查询也不快),增删慢,线程安全,效率低 LinkedList:底层双重链表,查询慢,增删快,线程不安全,效率高。 ###### 3、列举Co
Stella981 Stella981
1年前
Django中Admin中的一些参数配置
### **设置在列表中显示的字段,id为django模型默认的主键** list_display = ('id', 'name', 'sex', 'profession', 'email', 'qq', 'phone', 'status', 'create_time') ### **设置在列表可编辑字段** list_editable
Wesley13 Wesley13
1年前
java集合基础复习
温故知新,好一段学习时间过后到了收割的季节。 java中集合java.util包下的一个集合根接口collection,其子接口list和set,map接口定义key-value键值对。 ArrayList、linkedlist、vector实现了list接口。也称线性集合。数据有序可重复。 ArrayList:底层实现的数组,线程不安全的,效率