专栏首页程序员开发者社区对比Vector、 ArrayList、 LinkedList有何区别

对比Vector、 ArrayList、 LinkedList有何区别

对比Vector、 ArrayList、 LinkedList有何区别?

这三者都是实现集合框架中的List,也就是所谓的有序集合,因此具体功能也比较近似,比如都提供按照位置进行定位、添加或者删除的操作,都提倛迭代器以遍历其內容等。但因为具体的设计区别,在行为、性能、线程安全等方面,表现又有很大不同。

Vector 是 Java 早期提供的线程安全的动态数组,如果不需要线程安全,并不建议选择,同步有额外开销,Vector 内部是使用对象数组保存数据,也可以根据需要自动增加容量,当数组已满时,会创建新的数组,并拷贝原数组数据。

ArrayList 是应用更广泛的动态数组,本身不是线程安全的,与 Vector 相似, ArrayList 也是可以根据需要调整容量,不过两者间的调整有区别,Vector 在扩容时提高一倍, ArrayList 则是增加 50%。

LinkedList 是 Java 提供的双向链表,所有它不需要调整容量,它也不是线程安全的。

Vector、 ArrayList、 LinkedList均为线型的数据结构,但是从实现方式与应用场景中又存在差别,可以从下面几个方面总结。

底层实现方式

ArrayList内部用数组来实现;LinkedList内部采用双向链表实现;Vector内部用数组实现。

读写机制

ArrayList在执行插入元素是超过当前数组预定义的最大值时,数组需要扩容,扩容过程需要调用底层System.arraycopy()方法进行大量的数组复制操作;在删除元素时并不会减少数组的容量 (如果需要缩小数组容量,可以调用trimToSize()方法);在查找元素时要遍历数组,对于非null的元素采取equals的方式寻找。

LinkedList在插入元素时,须创建一个新的Entry对象,并更新相应元素的前后元素的引用;在查找元素时,需遍历链表;在删除元素时,要遍历链表,找到要删除的元素,然后从链表上将此元 素删除即可。

Vector与ArrayList仅在插入元素时容量扩充机制不一致。对于Vector,默认创建一个大小为10的Object数组,并将capacityIncrement设置为0;当插入元素数组大小不够时,如 果capacityIncrement大于0,则将Object数组的大小扩大为现有size+capacityIncrement;如果capacityIncrement<=0,则将Object数组的大小扩大为现有大小的2倍。

读写效率

ArrayList对元素的增加和删除都会引起数组的内存分配空间动态发生变化。因此,对其进行插入和删除速度较慢,但检索速度很快。

LinkedList由于基于链表方式存放数据,增加和删除元素的速度较快,但是检索速度较慢。

线程安全性

ArrayList、 LinkedList为非线程安全;

Vector是基于synchronized实现的线程安全的ArrayList。

单线程应尽量使用ArrayList, Vector因为同步会有性能损耗;即使在多线程环境下,我们可以利用Collections这个类中为我们提供的synchronizedList(List list)方法返回一个 线程安全的同步列表对象。

  • https://www.coursera.org/learn/algorithms-part1
  • http://hg.openjdk.java.net/jdk/jdk/file/bf9177eac58d/src/java.base/share/classes/java/util/TreeSet.java
  • http://mail.openjdk.java.net/pipermail/core-libs-dev/2018-January/051000.html

Java 集合框架

image

  • List,也就是我们前面介绍最多的有序集合,它提供了方便的访问、插入、删除等操作
  • set,set是不允许重复元素的,这是和L最明显的区别,也就是不存在两个对象 equals返回true。我们在日常开发中有很多需要保证元素唯一性的场合。
  • Queue/ Deque,则是Java提供的标准队列结构的实现,除了集合的基本功能,它还支持类似先入先出(FFO, First-in- First-Out)或者后入先岀(LIFO,Last-In- First out)等特定行为。这里不包括 BlockingQueue,因为通常是并发编程场合,所以被放置在并发包里。

Set 实现

  • TreeSet支持自然顺序访问,但是添加、删除、包含等操作要相对低效(log(n)时间)。
  • HashSet则是利用哈希算法,理想情况下,如果哈希散列正常,可以提供常数时间的添加、删除、包含等操作,但是它不保证有序。
  • LinkedHashSet,内部构建了一个记录插入顺序的双向链表,因此提供了按照插入顺序遍历的能力,与此同时,也保证了常数时间的添加、删除、包含等操作,这些操作性能略低于HashSet,因为需要维护链表的开销。
  • 在遍历元素时, HashSet性能受自身容量影响,所以初始化时,除非有必要,不然不要将其背后的HashMap容量设置过大。而对于LinkedHashSet,由于其内部链表提供的方便,遍历性能只和元素多少有关系

Collections 工具类

对于java.util.concurrent里面的线程安全容器,我在专栏后面会去介绍。但是,并不代表这些集合完全不能支持并发编程的场景,在Collections工具类中,提供了一系列的synchronized方法。

static <T> Lis<T> synchronizedLis(Lis<T> list)

线程安全集合

List list = Collections.synchronizedLis(new ArrayList());

本文分享自微信公众号 - 程序员开发者社区(gh_016ffe40d550),作者:猿星人

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 线程池原理

    一般开发者是利用 Executors 提供的统一线程创建方法,取创建不同配置的线程池,主要区别在于不同的 ExecutorService类型或者不同的初始参数。

    王小明_HIT
  • 一个线程调用两次 start()方法会出现什么情况?

    一个线程两次调用 start()方法会出现什么情况?谈谈线程的生命周期和状态转移。在第二次调用 start() 方法的时候,线程可能处于终止或者其他(非NEW)...

    王小明_HIT
  • RabbitMQ 集群数据迁移

    4. 停掉集群B ,将 集群A 的 n1 n2 n3 的文件,分别拷贝到 集群B 的 n1 n2 n3 文件mnesia 目录下。

    王小明_HIT
  • Java 基础(四)——集合源码解析 List

    前面我们学习了Iterator、Collection,为集合的学习打下了基础,现在我们来学习集合的第一大体系 List。

    蜻蜓队长
  • 面试江湖:一招破解 Java 集合类面试题

    Java集合类绝对是我们的老朋友了,Java技术江湖里,谁人不知,谁人不晓,它的使用率非常高,使用难度却也不大,这也导致了很多人对它不屑一顾,殊不知其中却暗藏玄...

    黄小斜
  • 数组

    数组是一种线性表的数据结构,它使用一组连续的内存空间,来存储一组具有相同类型的数据。

    幺鹿
  • Linux下的 Whoami 命令

    就像名字显示的那样,whoami命令打印出当前用户的用户名。换句话说,它显示当前登录用户的名字。

    雪梦科技
  • 春节充电系列:李宏毅2017机器学习课程学习笔记03之梯度下降

    【导读】我们在上一节的内容中已经为大家介绍了台大李宏毅老师的机器学习课程的regression问题,其中简要提及了梯度下降(gradient descent),...

    WZEARW
  • JavaScript强化教程——数组的基本处理函数

    本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScript强化教程 —— 数组的基本处理函数

    IMWeb前端团队
  • MyBatis(1)——快速入门

    MyBatis 简介 MyBatis 本是apache的一个开源项目iBatis, 2010年这个项目由apache software foundation 迁...

    我没有三颗心脏

扫码关注云+社区

领取腾讯云代金券