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

骑猪看日落 2024-04-17 05:47 90阅读 0赞

在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

![format_png][]

![format_png 1][]

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

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

![format_png 2][]

![20190823214315848.gif][]

![format_png 3][]

![format_png 4][]

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

2.ArrayList

![format_png 5][]

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

![format_png 6][]

![20190823214315852.gif][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

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

3.LinkedList

![format_png 10][]

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

![format_png 11][]

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

![format_png 12][]

![format_png 13][]

![format_png 14][]

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

![format_png 15][]

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

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

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

![format_png 20][]

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

![format_png 21][]

![format_png 22][]

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

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

![format_png 23][]

![format_png 24][]

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

![format_png 25][]

感兴趣的小伙伴可以关注我的公众号【IT技术之旅】，每天更新干货内容。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvY193ZWk_size_16_color_FFFFFF_t_70][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TmliUG41MWY5eXA3WmljbXVpY2ljMlFORXZtOTR5MjRxbm10RG9MclpCQThscHppYUFCcUtLUnFGeHZ3LzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TlpIdDVnYnk1QXlIcVByemtiMTZSSHBSYzNmeEdCYXB6dG5ibVAxNWRMUU14eWlhbUJMWDBIaWN3LzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TjlidG5aWWtvSUdVclJMa2ljVExmQXJsUGlhNnN5UXRsSnh3OWJxdzVpYll5WVpWcjZBVFZwZUdtQS82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[20190823214315848.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/a7efff07f1f84607b623bd667ba35cd3.gif
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TmZhU0RiSWliQU5aNlhaZGJydkQ4c0wyaWFjcTgzM25MTlFoaWN5UFZQTmhiSUJxaWJpYUJrZzhSb3ZRLzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TjVOQUNydG5BQTk2cEtVZDRsMnlEZUdLb1ZTMkcxa0QxSVc4SEFrQTl4OVhpYnUxMjJ6OFlRMkEvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TllwdVZMdG1PWUJSU1FFVnp6cnd1dTNZekJ6aWJ5QTNYYVJpY1Q3S0FpYmo4WHJuTTV2VFA3cVZUdy82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TlZqcUZBcjBLSVlRcXcxYnNqeVBIdGxTamdqRW1kNGt1Tmx2dHo5cWg3WXVJb3NFR2VibFYzUS82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[20190823214315852.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/bd7eefdf3af948c39ec9a32c8423a21f.gif
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TlBUOUFDakQ4MlBqSHdDUWN6RVBweGw5ZU82NDJPVzRjMTE1aWJwMjVQdHlCeGdzS1I2aWNyT05BLzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TnFMS3JGM1lkcjJGV0V3ZkdPUmVVWjhUSGNVd2NId1laSGxiTzdrYnBwMWtsQ2ljaE0zUkpIUkEvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1Tm5pYXNubkljbTAweEdhZGRzY0RVUnc5QWZJNmY2YkxzcEVkdXh4b1NFaDVLRGlhdVBKNVA4S0ZRLzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TnQ0OU9YNndCTzJyRVJ3OUR3dzAyRnZDYnlGd0k1bkpNNlVtTXRaa3cxSHZEZ0Z0ZHgxaWNPdncvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TlMyT2o0REVPbXdTMk9lUHlSSzByaWJwRldFTmZCWEhqRHJKWkFpYkRMTW13cmsxY2R5b1JpYmZldy82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TkV5UlNvRGljR0t0WENuWldoQ2I0RkJuR1QyaWN4UlplQ2h4UlI5MVNzaWFPWHhybDloOGtBUmJXQS82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TjFMTHJXV2dZTmc4QXRSUkNhVHloNGliN1hIekdnd2J5a3o0a3pUeWhNSkJFT0FkcWlicE15cDB3LzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1Tk9VMVlESWhKclFkQ0dlUXZybGxMUTFRckdiWVIzc2FoNlZ3eTRwd0t6MXp2azN4WVpMcGxQQS82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TnBsbFFXdE9kQTF2eWtCVW1wWE9IdlFySWptMk04anhEY01waWFsTXdBeEFKZ3p2cnIza0V6dlEvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TlJLeFM5Y1lDUEtFVzg1WGtFZmtzVE1MdTJLVlBxZXRLTUx4dFFpYUVsUGVVYmw5dGVsYm5LUGcvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TjRaZXE2UG9pY0d0MHZvVXNQZm4zR3ZHWk9pYnZCY3FWbFU0d1dreVYwem4wRkl2M2ZoUEZpY0hhQS82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TkFad0xhQmJlNFpGMXVpYUR4UnNLU2phSmcxdzREOGdFbkdYMWlhdUxkcENHTzJZaWNpYmt2MHRWREEvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TmVVUGpnaWNZWWtGWll6ajZXVzQ2ZW56VUVHRTNuclVXNVVjcmRNd3VEOHdGU1hpYjBjTnNwZGN3LzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1Tk9TbnBzczh3Tnh2V0dpYlRyQ2hsRktMTG9MNlRGVG1pYjA3QkJuZGlib3RKM3gyZmc5aWNiZEdyeVEvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TmZuZUFYWVNJd2ExU3N2R0d2YWNWSTZBQVhKRktqOVBiSmV5QzZmYklmTzJmMlY0SzE3ODNyUS82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TjFSanAzSWxDOTFWa1hMOU1pYW50QVdqR3cwaWFPUXFXelllT1lING1UaGdGTjl4ZjVxSjFkRmdRLzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TnJ5VVMxRTlraWJHY0Y3UzNXNDVyeGhYNWlhTUNDQm1jUU9pYWFpYU4waWFwbUYzd2lhUG5zTkhZYWFkZy82NDA_d3hfZm10PXBuZyZ0cD13ZWJwJnd4ZnJvbT01Jnd4X2xhenk9MSZ3eF9jbz0x?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TlJ5T1U2TkM2WEtlQ01jNG9mRWE0QmpGRkUwUlkyU0F5cFJPS2RVSlJCcG9ubnNXNXZHaWJ1YkEvNjQwP3d4X2ZtdD1wbmcmdHA9d2VicCZ3eGZyb209NSZ3eF9sYXp5PTEmd3hfY289MQ?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NRHRGQ2toOUlDNVJ1RzNaejY0QzVxTTFrT1RoZ2N1TkxFMUJRYWhjVlRBWTQydDZmT3V4cmZpY1pJMXZuUXUwc0FMRGU2amZheUd4NVppYmFIOHFZZUtRLzY0MD93eF9mbXQ9cG5nJnRwPXdlYnAmd3hmcm9tPTUmd3hfbGF6eT0xJnd4X2NvPTE?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvY193ZWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190823214601911.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvY193ZWk=,size_16,color_FFFFFF,t_70