List 是 Java 中比较常用的集合类, 关于 List 接口有很多实现类, 本文就来简单介绍下其中几个重点的实现 ArrayList,LinkedList 和 Vector 之间的关系和区别.
List
List 是一个接口, 它继承于 Collection 的接口. 它代表着有序的队列. 当我们讨论 List 的时候, 一般都和 Set 作比较.
List 中元素可以重复, 并且是有序的(这里的有序指的是按照放入的顺序进行存储. 如按照顺序把 1,2,3 存入 List, 那么, 从 List 中遍历出来的顺序也是 1,2,3).
Set 中的元素不可以重复, 并且是无序的(从 set 中遍历出来的数据和放入顺序没有关系).
下面是 Java 中的集合类的关系图. 从中可以大致了解集合类之间的关系
ArrayList, LinkedList 和 Vector 之间的区别
从上图可以看出, ArrayList, LinkedList 和 Vector 都实现了 List 接口, 是 List 的三种实现, 所以在用法上非常相似. 他们之间的主要区别体现在不同操作的性能上. 后面会详细分析.
ArrayList
ArrayList 底层是用数组实现的, 可以认为 ArrayList 是一个可改变大小的数组. 随着越来越多的元素被添加到 ArrayList 中, 其规模是动态增加的.
LinkedList
LinkedList 底层是通过双向链表实现的. 所以, LinkedList 和 ArrayList 之前的区别主要就是数组和链表的区别.
数组中查询和赋值比较快, 因为可以直接通过数组下标访问指定位置.
链表中删除和增加比较快, 因为可以直接通过修改链表的指针 (Java 中并无指针, 这里可以简单理解为指针. 其实是通过 Node 节点中的变量指定) 进行元素的增删.
所以, LinkedList 和 ArrayList 相比, 增删的速度较快. 但是查询和修改值的速度较慢. 同时, LinkedList 还实现了 Queue 接口, 所以他还提供了 offer(), peek(), poll()等方法.
Vector
Vector 和 ArrayList 一样, 都是通过数组实现的, 但是 Vector 是线程安全的. 和 ArrayList 相比, 其中的很多方法都通过同步 (synchronized) 处理来保证线程安全.
如果你的程序不涉及到线程安全问题, 那么使用 ArrayList 是更好的选择(因为 Vector 使用 synchronized, 必然会影响效率).
二者之间还有一个区别, 就是扩容策略不一样. 在 List 被第一次创建的时候, 会有一个初始大小, 随着不断向 List 中增加元素, 当 List 认为容量不够的时候就会进行扩容. Vector 缺省情况下自动增长原来一倍的数组长度, ArrayList 增长原来的 50%.
ArrayList 和 LinkedList 的性能对比
使用以下代码对 ArrayList 和 LinkedList 中的几种主要操作所用时间进行对比:
- ArrayList arrayList = new ArrayList();
- LinkedList linkedList = new LinkedList();
- // ArrayList add
- long startTime = System.nanoTime();
- for (int i = 0; i < 100000; i++) {
- arrayList.add(i);
- }
- long endTime = System.nanoTime();
- long duration = endTime - startTime;
- System.out.println("ArrayList add:" + duration);
- // LinkedList add
- startTime = System.nanoTime();
- for (int i = 0; i < 100000; i++) {
- linkedList.add(i);
- }
- endTime = System.nanoTime();
- duration = endTime - startTime;
- System.out.println("LinkedList add:" + duration);
- // ArrayList get
- startTime = System.nanoTime();
- for (int i = 0; i < 10000; i++) {
- arrayList.get(i);
- }
- endTime = System.nanoTime();
- duration = endTime - startTime;
- System.out.println("ArrayList get:" + duration);
- // LinkedList get
- startTime = System.nanoTime();
- for (int i = 0; i < 10000; i++) {
- linkedList.get(i);
- }
- endTime = System.nanoTime();
- duration = endTime - startTime;
- System.out.println("LinkedList get:" + duration);
- // ArrayList remove
- startTime = System.nanoTime();
- for (int i = 9999; i >=0; i--) {
- arrayList.remove(i);
- }
- endTime = System.nanoTime();
- duration = endTime - startTime;
- System.out.println("ArrayList remove:" + duration);
- // LinkedList remove
- startTime = System.nanoTime();
- for (int i = 9999; i >=0; i--) {
- linkedList.remove(i);
- }
- endTime = System.nanoTime();
- duration = endTime - startTime;
- System.out.println("LinkedList remove:" + duration);
结果:
- ArrayList add: 13265642
- LinkedList add: 9550057
- ArrayList get: 1543352
- LinkedList get: 85085551
- ArrayList remove: 199961301
- LinkedList remove: 85768810
他们的表现的差异是显而易见的. 在添加和删除操作上 LinkedList 更快, 但在查询速度较慢.
如何选择
如果涉及到多线程, 那么就选择 Vector(当然, 你也可以使用 ArrayList 并自己实现同步).
如果不涉及到多线程就从 LinkedList,ArrayList 中选. LinkedList 更适合从中间插入或者删除(链表的特性). ArrayList 更适合检索和在末尾插入或删除(数组的特性).
来源: http://zhuanlan.51cto.com/art/201809/584377.htm