美文网首页
ArrayList、LinkedList、Vector

ArrayList、LinkedList、Vector

作者: Ray昱成 | 来源:发表于2019-01-26 13:48 被阅读0次

从行为、结构、性能、安全等来分析。

行为

  • 都实现了List接口,都是有序集合
  • 都提供了根据位置索引进行查找、增加、删除
  • 都提供迭代器进行遍历元素
  • vector和ArrayList支持随机访问,而LinkedList需要遍历所有元素。
  • sort内部实际都是调用Arrays.sort
  • LinkedList同时实现了Deque,拥有队列的行为。

结构

  • vector是线程安全的动态数组、ArrayList是常态动态数组
  • LinkedList是双向链表

性能

  • vector和ArrayList中数组默认长度都是10,元素数量超出需要扩容。而LinkedList新增元素与元素数据无关。
  • vector中数组扩容提高一倍,而ArrayList是50%
  • 由于数组在中间插入和删除元素需要重新移动元素,所以理论上在中间增删数据没有LikedList高效。

安全

Vector内部对所有方法都加上了锁,所以是线程安全的。其余两个线程不安全

关于Arrays.sort

  • 对于原始数据类型,目前使用的是所谓双轴快速排序(Dual-Pivot QuickSort),是一种改进的快速排序算法
  • 对于对象数据类型,目前则是使用TimSort,思想上也是一种归并和二分插入排序(binarySort)结合的优化排序算法。它的思路是查找数据集中已经排好序的分区,然后合并这些分区来达到排序的目的
  • Java 8 引入了并行排序算法(直接使用 parallelSort 方法),适合处理大数据集。不过当数据集小于1 << 13时,其实还是调用的TimeSort。

相关文章

网友评论

      本文标题:ArrayList、LinkedList、Vector

      本文链接:https://www.haomeiwen.com/subject/lmlijqtx.html