实验
在数据尾部插入数据
测试代码
- package com.lly.springtest1.collection;
- import lombok.extern.slf4j.Slf4j;
- import java.util.ArrayList;
- import java.util.LinkedList;
- /**
- * @ClassName ICollection
- * @Description TODO
- * @Author lly
- * @Date 2019/3/5 9:29 AM
- * @Version 1.0
- **/
- @Slf4j
- public class ICollection {
- public static void test() {
- LinkedList<String> links = new LinkedList<>();
- int len = 6553631;
- log.info(len + "");
- long btime = System.currentTimeMillis();
- for (int i = 0; i <len; i++) {
- links.add("sss");
- }
- long etime = System.currentTimeMillis();
- log.info("耗时:{}, 大小:{}", etime - btime, links.size());
- long btime1 = System.currentTimeMillis();
- ArrayList<String> arrays = new ArrayList<>();
- for (int i = 0; i <len; i++) {
- arrays.add("sss");
- }
- long etime1 = System.currentTimeMillis();
- log.info("耗时:{}, 大小:{}", etime1 - btime1, arrays.size());
- }
- public static void main(String[] args) {
- ICollection.test();
- }
- }
测试结果
此时我们的数量级别是百万级别, 我们惊讶的发现 ArrayList 插入效率要比 LinkedList 快接近 20 倍, 为什么? why? 我们明明记得在学习 java 集合的时候, 明确的知道是 ArrayList 查询快, 增删慢的, LinkedList 的特细则与之相反的, 可是现实测试却跟定义不一样呢, 那我们在多做点测试, 改变数量级别看看十万, 万, 千级别的测试结果, 我们改变插入集合的数据量大小测试.
首先降低到十万级别
发现测试的插入效率已经很接近了
万级别
这时候我们发现和十万级别的测试结果差不多, 还是 ArrayList 插入快一点
接着我们降低到千级别
此时两者的效率差不多, 还是没有体现出书中定义的 2 者关于插入效率的问题, 问题还是没有得到解决, 那么我们思考一下, 上面的实验我们都是默认插入的末尾的, 是否跟我么插入的顺序有关系吗, 我们下面测试一下将数据插入的头部
在数组头部插入数据
- package com.lly.springtest1.collection;
- import lombok.extern.slf4j.Slf4j;
- import java.util.ArrayList;
- import java.util.LinkedList;
- /**
- * @ClassName ICollection
- * @Description TODO
- * @Author lly
- * @Date 2019/3/5 9:29 AM
- * @Version 1.0
- **/
- @Slf4j
- public class ICollection {
- public static void test() {
- LinkedList<String> links = new LinkedList<>();
- int len = 100000;
- log.info(len + "");
- long btime = System.currentTimeMillis();
- for (int i = 0; i <len; i++) {
- links.addFirst("sss");
- }
- long etime = System.currentTimeMillis();
- log.info("耗时:{},LinkedList 大小:{}", etime - btime, links.size());
- long btime1 = System.currentTimeMillis();
- ArrayList<String> arrays = new ArrayList<>();
- for (int i = 0; i <len; i++) {
- arrays.add(0,"sss");
- }
- long etime1 = System.currentTimeMillis();
- log.info("耗时:{},ArrayList 大小:{}", etime1 - btime1, arrays.size());
- }
- public static void main(String[] args) {
- ICollection.test();
- }
- }
此时我们发现, 在万级别 LinkedList 的插入性能就看出来了
此时我们发现, 在十万级别 LinkedList 的插入性能是 ArrayList 的 100 + 倍, 那么我们下面再测试一下在数组中间部分插入数据
在数组中间插入数据
- package com.lly.springtest1.collection;
- import lombok.extern.slf4j.Slf4j;
- import java.util.ArrayList;
- import java.util.LinkedList;
- /**
- * @ClassName ICollection
- * @Description TODO
- * @Author lly
- * @Date 2019/3/5 9:29 AM
- * @Version 1.0
- **/
- @Slf4j
- public class ICollection {
- public static void test() {
- LinkedList<String> links = new LinkedList<>();
- int len = 10000;
- log.info(len + "");
- long btime = System.currentTimeMillis();
- for (int i = 0; i <len; i++) {
- links.add(links.size() / 2, "sss");
- }
- long etime = System.currentTimeMillis();
- log.info("耗时:{},LinkedList 大小:{}", etime - btime, links.size());
- long btime1 = System.currentTimeMillis();
- ArrayList<String> arrays = new ArrayList<>();
- for (int i = 0; i <len; i++) {
- arrays.add(arrays.size() / 2, "sss");
- }
- long etime1 = System.currentTimeMillis();
- log.info("耗时:{},ArrayList 大小:{}", etime1 - btime1, arrays.size());
- }
- public static void main(String[] args) {
- ICollection.test();
- }
- }
数据量万级别 Linkedlist 插入效率比 ArrayList 慢 20 倍
数据量十万级别 Linkedlist 插入效率比 ArrayList 慢 160 + 倍
源码分析
在指定位置插入
LinkedList 源码
- public void add(int index, E element) {
- checkPositionIndex(index);
- if (index == size)
- linkLast(element);
- else
- linkBefore(element, node(index));
- }
判断是否超过链表长度, 超过则抛错误
如果是插入最后的位置直接使用 linkLast 方法而不必去遍历查询对应位置
node 方法寻找 index 所指向的 Node, 首先判断 index 是否大于 size/2, 大于则从末尾往前找, 小于则从 0 开始往后找
找到之后就是 new 一个 node 对象, 设置指针的问题
LinkedList: 性能主要在于遍历链表查找 index
ArrayList 源码
- public void add(int index, E element) {
- rangeCheckForAdd(index);
- ensureCapacityInternal(size + 1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
rangeCheckForAdd 判断 index 是否合法
ensureCapacityInternal 判断是否需要扩容
arraycopy 数组复制, 从 index 开始把后面的数组元素全部复制到相对后一位的位置, 该方法是 native 方法而且是连续内存复制问题, 因此性能影响也没想象中的大
elementData 将 element 赋值给数组 index 元素
ArrayList: 影响 ArrayList 性能的主要因素是扩容和数组复制, 但是当 size 很大时数组扩容影响就会变小, 那么此时的效率就会提升, 此时如果在中间部分插入数据时候, 我们要插入的位置为 i, 数组长度是 n, 那么就要变动 i 之后的 n-i 的数据.
在头部部插入
LinkedList 源码
- public void addFirst(E e) {
- linkFirst(e);
- }
- private void linkFirst(E e) {
- final Node<E> f = first;
- final Node<E> newNode = new Node<>(null, e, f);
- first = newNode;
- if (f == null)
- last = newNode;
- else
- f.prev = newNode;
- size++;
- modCount++;
- }
可以看到 LinkedList 直接在头部时候不必遍历, 所以效率很高, 体现了 LinkedList 的插入效率高的特性
ArrayList 源码解释同 (指定位置插入)
在尾部插入
LinkedList 源码
- public boolean add(E e) {
- linkLast(e);
- return true;
- }
- void linkLast(E e) {
- final Node<E> l = last;
- final Node<E> newNode = new Node<>(l, e, null);
- last = newNode;
- if (l == null)
- first = newNode;
- else
- l.next = newNode;
- size++;
- modCount++;
- }
LinkedList: 用传入的值 new 一个 Node 对象, 然后尾指针指向该新的 Node
ArrayList 源码
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
ArrayList: 如果超出容量需要扩容, 不需扩容时直接数组元素赋值
结论: 当数据量越来越大时, ArrayList 比 LinkedList 快
原因: 当数据量大时, ArrayList 每次扩容都能得到很大的新空间, 解决了前期频繁扩容的劣势, 而 LinkedList 虽然有尾指针, 但是每次 add 都要将对象 new 成一个 Node(而 ArrayList 直接数组对应位置元素赋值)
结论
数据量 \ 插入位置 | 头部 | 中间 | 尾部 |
---|---|---|---|
万 | LinkedList 插入快 | ArrayList 插入快 | ArrayList 插入快 |
十万 | LinkedList 插入快 | ArrayList 插入快 | ArrayList 插入快 |
在尾部插入数据, 数据量较小时 LinkedList 比较快, 因为 ArrayList 要频繁扩容, 当数据量大时 ArrayList 比较快, 因为 ArrayList 扩容是当前容量 * 1.5, 大容量扩容一次就能提供很多空间, 当 ArrayList 不需扩容时效率明显比 LinkedList 高, 因为直接数组元素赋值不需 new Node
在首部插入数据, LinkedList 较快, 因为 LinkedList 遍历插入位置花费时间很小, 而 ArrayList 需要将原数组所有元素进行一次 System.arraycopy
插入位置越往中间, LinkedList 效率越低, 因为它遍历获取插入位置是从两头往中间搜, index 越往中间遍历越久, 因此 ArrayList 的插入效率可能会比 LinkedList 高
插入位置越往后, ArrayList 效率越高, 因为数组需要复制后移的数据少了, 那么 System.arraycopy 就快了, 因此在首部插入数据 LinkedList 效率比 ArrayList 高, 尾部插入数据 ArrayList 效率比 LinkedList 高
inkedList 可以实现队列, 栈等数据结构, 这是它的优势
来源: https://juejin.im/post/5c7dd5ece51d457cb60884d9