专注于 JetBrains IDEA 全家桶,永久激活,教程
持续更新 PyCharm,IDEA,WebStorm,PhpStorm,DataGrip,RubyMine,CLion,AppCode 永久激活教程

ArrayDeque(基于动态数组实现的循环队列 )和 LinkedList(双向链表的队列) 性能比较

package com.tc.javabase.collection;

package com.tc.javabase.collection;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Classname ArrayDequeCompareLinkedList
 * @Description 基于动态数组实现的循环队列 和 双向链表的队列  性能比较
 * ArrayDeque  compare with LinkedList
 * ArrayDeque 和  LinkedList 时间复杂度分析
 *                ArrayDeque    LinkedList
 * 入队操作:       O(1)          O(1)
 * 出队操作:       O(1)          O(1)
 * 查看队首元素:    O(1)          O(1)
 *
 *  猜测:  ArrayDeque 的底层是用动态数组来实现,会出现动态扩容和缩容的情况,虽然均摊到每次操作的
 *  时间复杂度仍然是O(1), 但性能比底层使用链表的队列性能低一点点
 *
 *  结果:
 *           n         ArrayDeque耗时   LinkedList耗时
 *           10w       0.0054            0.0067
 *           100w      0.0186            0.0271
 *           1000w     1.8155            4.3795
 *
 *  ArrayDeque的性能比LinkedList好 随着n的增加 耗时间隔越来越大
 *  原因:1.在每次新增元素的时候  链表都要创建一个node节点 分配内存时间大
 *
 *
 *
 * @Date 2020/7/21 19:48
 * @Created by zhangtianci
 */
public class ArrayDequeCompareLinkedList {
    private static Queue<Integer> linkedlistQueue = new LinkedList<Integer>();
    private static Queue<Integer> arrayQueue = new ArrayDeque<>();
    private static final int count = 1000000;   //测试1000w条数据的入队出队

    public static void main(String[] args) {
        double arrayQueueTime = arrayQueue();
        double linkedlistQueueTime = linkedlistQueue();

        System.out.println("linkedlistQueue 耗时:" + linkedlistQueueTime);
        System.out.println("arrayQueue 耗时:" + arrayQueueTime);
    }

    public static double linkedlistQueue(){
        long startTime = System.nanoTime();
        for (int i = 0;i < count;i++){
            linkedlistQueue.add(i);
        }
        for (int i = 0;i < linkedlistQueue.size();i++){
            linkedlistQueue.remove();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / Math.pow(10,9);
    }

    public static double arrayQueue(){
        long startTime = System.nanoTime();
        for (int i = 0;i < count;i++){
            arrayQueue.add(i);
        }
        for (int i = 0;i < arrayQueue.size();i++){
            arrayQueue.remove();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / Math.pow(10,9);
    }

}

文章永久链接:https://tech.souyunku.com/38379

未经允许不得转载:搜云库技术团队 » ArrayDeque(基于动态数组实现的循环队列 )和 LinkedList(双向链表的队列) 性能比较

JetBrains 全家桶,激活、破解、教程

提供 JetBrains 全家桶激活码、注册码、破解补丁下载及详细激活教程,支持 IntelliJ IDEA、PyCharm、WebStorm 等工具的永久激活。无论是破解教程,还是最新激活码,均可免费获得,帮助开发者解决常见激活问题,确保轻松破解并快速使用 JetBrains 软件。获取免费的破解补丁和激活码,快速解决激活难题,全面覆盖 2024/2025 版本!

联系我们联系我们