ToB企服应用市场:ToB评测及商务社交产业平台

标题: ArrayList与LinkedList、Vector的区别 [打印本页]

作者: 鼠扑 时间: 昨天 00:44
标题: ArrayList与LinkedList、Vector的区别
一、ArrayList 和 LinkedList区别：

（1）两者都是线程不安全，都实现了Collection接口。
（2）数据结构：ArrayList是基于动态数组的数据结构，LinkedList是基于双向链表的数据结构。
（3）性能：ArrayList支持随机访问，查询快，增删慢，查询的时间复杂度为O(1)，插入和删除的时间复杂度为O(n)，由于对插入和删除位置后面的元素进行移动位置，以包管内存的一连性
LinkedList不支持随机访问，查询慢，增删快，查询的时间复杂度为O(n)，插入和删除的时间复杂度为O(1)
ArrayList：

get() 直接读取第几个下标，复杂度 O(1)；
add(E) 添加元素，直接在后面添加，复杂度O（1）；
add(index, E) 添加元素，在第几个元素后面插入，后面的元素须要向后移动，复杂度O（n）；
remove（）删除元素，后面的元素须要逐个移动，复杂度O(n)。

  LinkedList：

get() 获取第几个元素，依次遍历，复杂度O(n)；
add(E) 添加到末尾，复杂度O(1)；
add(index, E) 添加第几个元素后，须要先查找到第几个元素，直接指针指向利用，复杂度O(n)；
remove（）删除元素，直接指针指向利用，复杂度O(1)。

  （4）空间的消耗：ArrayList的空间浪费主要体现在在list列表的末端预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都须要消耗相当的空间。

总结

  ArrayList：
  优点：

随机访问服从高，适合查找和遍历利用。
内存一连，缓存命中率高，性能相对较好。

缺点：

插入和删除元素服从较低，特别是在中间插入或删除元素时。
动态扩容须要重新分配内存和复制元素，大概会影响性能。

  LinkedList：
  优点：

插入和删除元素服从高，特别是在中间插入或删除元素时。
不须要频繁扩容，没有数组扩容带来的性能损耗。

缺点：

随机访问服从低，须要从头或尾开始遍历。
每个节点须要额外的引用，占用更多内存空间。

二、ArrayList和Vector的区别：

（1）数据结构：ArrayList和Vector底层的数据结构都是数组。
（2）线程安全：Vector线程安全的，底层使用synchronize进行加锁，而ArrayList是线程不安全的。
（3）性能：由于Vector使用synchronize锁来确保线程的安全性，所以性能会稍逊于ArrayList。
（4）初始容量和扩容：ArrayList和Vector的默认初始容量都是10，但是扩容时，ArrayList容量会增长为原来的1.5倍，而Vector的容量会增长为原来的2倍。
（5）Vector实现的Enumeration接口，所以可以使用Enumeration进行遍历元素。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)