`
shift8
  • 浏览: 149704 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

3、说说ArrayList、LinkedList的区别

阅读更多

  笔试面试题目搜集整理【每日增加】

 

3、说说ArrayList、LinkedList的区别

【答案】

1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。

 

2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。

 

3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。

 

ArrayList 和LinkedList是两个集合类,用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String 或者Integer。那么ArrayList和LinkedList在性能上有什么差别呢?什么时候应该用ArrayList什么时候又该用 LinkedList呢?

一.时间复杂度

首先一点关键的是,ArrayList的内部实现是基于基础的对象数组的,因此,它使用get方法访问列表中的任意一个元素时(random access),它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查,直到另外一端。对 LinkedList而言,访问列表中的某个指定元素没有更快的方法了。

假设我们有一个很大的列表,它里面的元素已经排好序了,这个列表可能是ArrayList类型的也可能是LinkedList类型的,现在我们对这个列表来进行二分查找(binary search),比较列表是ArrayList和LinkedList时的查询速度,看下面的程序:

 

package com.mangocity.test; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.Random; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 
public class TestList ...{ 
     public static final int N=50000; 

     public static List values; 

     static...{ 
         Integer vals[]=new Integer[N]; 

         Random r=new Random(); 

         for(int i=0,currval=0;i<N;i++)...{ 
             vals=new Integer(currval); 
             currval+=r.nextInt(100)+1; 
         } 

         values=Arrays.asList(vals); 
     } 

     static long timeList(List lst)...{ 
         long start=System.currentTimeMillis(); 
         for(int i=0;i<N;i++)...{ 
             int index=Collections.binarySearch(lst, values.get(i)); 
             if(index!=i) 
                 System.out.println("***错误***"); 
         } 
         return System.currentTimeMillis()-start; 
     } 
     public static void main(String args[])...{ 
         System.out.println("ArrayList消耗时间:"+timeList(new ArrayList(values))); 
         System.out.println("LinkedList消耗时间:"+timeList(new LinkedList(values))); 
     } 
} 

 

 

我得到的输出是:

ArrayList消耗时间:15 

LinkedList消耗时间:2596 

 

这个结果不是固定的,但是基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(random access)策略,而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的,在ArrayList中进行随机访问所消耗的时间是固定的。

这是否表明ArrayList总是比LinkedList性能要好呢?这并不一定,在某些情况下LinkedList的表现要优于ArrayList,有些算法在LinkedList中实现时效率更高。比方说,利用Collections.reverse方法对列表进行反转时,其性能就要好些。

看这样一个例子,加入我们有一个列表,要对其进行大量的插入和删除操作,在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子,我们重复的在一个列表的开端插入一个元素:

package com.mangocity.test; 

import java.util.*; 
public class ListDemo { 
     static final int N=50000; 
     static long timeList(List list){ 
     long start=System.currentTimeMillis(); 
     Object o = new Object(); 
     for(int i=0;i<N;i++) 
         list.add(0, o); 
     return System.currentTimeMillis()-start; 
     } 
     public static void main(String[] args) { 
         System.out.println("ArrayList耗时:"+timeList(new ArrayList())); 
         System.out.println("LinkedList耗时:"+timeList(new LinkedList())); 
     } 
} 

 

这时我的输出结果是:

ArrayList耗时:2463 

LinkedList耗时:15 

 

这和前面一个例子的结果截然相反,当一个元素被加到ArrayList的最开端时,所有已经存在的元素都会后移,这就意味着数据移动和复制上的开销。相反的,将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录,然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的,而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。

二.空间复杂度

在LinkedList中有一个私有的内部类,定义如下:

private static class Entry { 
         Object element; 
         Entry next; 
         Entry previous; 
} 

 

 

每个Entry对象reference列表中的一个元素,同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的 LinkedList对象将有1000个链接在一起的Entry对象,每个对象都对应于列表中的一个元素。这样的话,在一个LinkedList结构中将有一个很大的空间开销,因为它要存储这1000个Entity对象的相关信息。

ArrayList 使用一个内置的数组来存储元素,这个数组的起始容量是10.当数组需要增长时,新的容量按如下公式获得:新容量=(旧容量*3)/2+1,也就是说每一次容量大概会增长50%。这就意味着,如果你有一个包含大量元素的ArrayList对象,那么最终将有很大的空间会被浪费掉,这个浪费是由 ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素,数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配,将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素,我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在 ArrayList分配完毕之后去掉浪费掉的空间。

三.总结

ArrayList和LinkedList在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下:

性能总结:

 

     -     add()操作     delete()操作      insert操作         index取值操作     iterator取值操作  
ArrayList/Vector/Stack      好            差                差                    极优            极优  
LinkedList      好            好                好                    差              极优    

1.对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象。

2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在LinkedList的中间插入或删除一个元素的开销是固定的。

3.LinkedList不支持高效的随机元素访问。

4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说:当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能;当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

 

分享到:
评论

相关推荐

    pandas-1.3.5-cp37-cp37m-macosx_10_9_x86_64.zip

    pandas whl安装包,对应各个python版本和系统(具体看资源名字),找准自己对应的下载即可! 下载后解压出来是已.whl为后缀的安装包,进入终端,直接pip install pandas-xxx.whl即可,非常方便。 再也不用担心pip联网下载网络超时,各种安装不成功的问题。

    基于java的大学生兼职信息系统答辩PPT.pptx

    基于java的大学生兼职信息系统答辩PPT.pptx

    基于java的乐校园二手书交易管理系统答辩PPT.pptx

    基于java的乐校园二手书交易管理系统答辩PPT.pptx

    tornado-6.4-cp38-abi3-musllinux_1_1_i686.whl

    tornado-6.4-cp38-abi3-musllinux_1_1_i686.whl

    Android Studio Ladybug(android-studio-2024.2.1.10-mac.zip.002)

    Android Studio Ladybug 2024.2.1(android-studio-2024.2.1.10-mac.dmg)适用于macOS Intel系统,文件使用360压缩软件分割成两个压缩包,必须一起下载使用: part1: https://download.csdn.net/download/weixin_43800734/89954174 part2: https://download.csdn.net/download/weixin_43800734/89954175

    基于ssm框架+mysql+jsp实现的监考安排与查询系统

    有学生和教师两种角色 登录和注册模块 考场信息模块 考试信息模块 点我收藏 功能 监考安排模块 考场类型模块 系统公告模块 个人中心模块: 1、修改个人信息,可以上传图片 2、我的收藏列表 账号管理模块 服务模块 eclipse或者idea 均可以运行 jdk1.8 apache-maven-3.6 mysql5.7及以上 tomcat 8.0及以上版本

    tornado-6.1b2-cp38-cp38-macosx_10_9_x86_64.whl

    tornado-6.1b2-cp38-cp38-macosx_10_9_x86_64.whl

    Android Studio Ladybug(android-studio-2024.2.1.10-mac.zip.001)

    Android Studio Ladybug 2024.2.1(android-studio-2024.2.1.10-mac.dmg)适用于macOS Intel系统,文件使用360压缩软件分割成两个压缩包,必须一起下载使用: part1: https://download.csdn.net/download/weixin_43800734/89954174 part2: https://download.csdn.net/download/weixin_43800734/89954175

    基于MATLAB车牌识别代码实现代码【含界面GUI】.zip

    matlab

    基于java的毕业生就业信息管理系统答辩PPT.pptx

    基于java的毕业生就业信息管理系统答辩PPT.pptx

    基于Web的毕业设计选题系统的设计与实现(springboot+vue+mysql+说明文档).zip

    随着高等教育的普及和毕业设计的日益重要,为了方便教师、学生和管理员进行毕业设计的选题和管理,我们开发了这款基于Web的毕业设计选题系统。 该系统主要包括教师管理、院系管理、学生管理等多个模块。在教师管理模块中,管理员可以新增、删除教师信息,并查看教师的详细资料,方便进行教师资源的分配和管理。院系管理模块则允许管理员对各个院系的信息进行管理和维护,确保信息的准确性和完整性。 学生管理模块是系统的核心之一,它提供了学生选题、任务书管理、开题报告管理、开题成绩管理等功能。学生可以在此模块中进行毕业设计的选题,并上传任务书和开题报告,管理员和教师则可以对学生的报告进行审阅和评分。 此外,系统还具备课题分类管理和课题信息管理功能,方便对毕业设计课题进行分类和归档,提高管理效率。在线留言功能则为学生、教师和管理员提供了一个交流互动的平台,可以就毕业设计相关问题进行讨论和解答。 整个系统设计简洁明了,操作便捷,大大提高了毕业设计的选题和管理效率,为高等教育的发展做出了积极贡献。

    机器学习(预测模型):2000年至2015年期间193个国家的预期寿命和相关健康因素的数据

    这个数据集来自世界卫生组织(WHO),包含了2000年至2015年期间193个国家的预期寿命和相关健康因素的数据。它提供了一个全面的视角,用于分析影响全球人口预期寿命的多种因素。数据集涵盖了从婴儿死亡率、GDP、BMI到免疫接种覆盖率等多个维度,为研究者提供了丰富的信息来探索和预测预期寿命。 该数据集的特点在于其跨国家的比较性,使得研究者能够识别出不同国家之间预期寿命的差异,并分析这些差异背后的原因。数据集包含22个特征列和2938行数据,涉及的变量被分为几个大类:免疫相关因素、死亡因素、经济因素和社会因素。这些数据不仅有助于了解全球健康趋势,还可以辅助制定公共卫生政策和社会福利计划。 数据集的处理包括对缺失值的处理、数据类型转换以及去重等步骤,以确保数据的准确性和可靠性。研究者可以使用这个数据集来探索如教育、健康习惯、生活方式等因素如何影响人们的寿命,以及不同国家的经济发展水平如何与预期寿命相关联。此外,数据集还可以用于预测模型的构建,通过回归分析等统计方法来预测预期寿命。 总的来说,这个数据集是研究全球健康和预期寿命变化的宝贵资源,它不仅提供了历史数据,还为未来的研究和政策制

    基于微信小程序的高校毕业论文管理系统小程序答辩PPT.pptx

    基于微信小程序的高校毕业论文管理系统小程序答辩PPT.pptx

    基于java的超市 Pos 收银管理系统答辩PPT.pptx

    基于java的超市 Pos 收银管理系统答辩PPT.pptx

    基于java的网上报名系统答辩PPT.pptx

    基于java的网上报名系统答辩PPT.pptx

    基于java的网上书城答辩PPT.pptx

    基于java的网上书城答辩PPT.pptx

    婚恋网站 SSM毕业设计 附带论文.zip

    婚恋网站 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B

    基于java的戒烟网站答辩PPT.pptx

    基于java的戒烟网站答辩PPT.pptx

    基于微信小程序的“健康早知道”微信小程序答辩PPT.pptx

    基于微信小程序的“健康早知道”微信小程序答辩PPT.pptx

    机器学习(预测模型):自行车共享使用情况的数据集

    Capital Bikeshare 数据集是一个包含从2020年5月到2024年8月的自行车共享使用情况的数据集。这个数据集记录了华盛顿特区Capital Bikeshare项目中自行车的租赁模式,包括了骑行的持续时间、开始和结束日期时间、起始和结束站点、使用的自行车编号、用户类型(注册会员或临时用户)等信息。这些数据可以帮助分析和预测自行车共享系统的需求模式,以及了解用户行为和偏好。 数据集的特点包括: 时间范围:覆盖了四年多的时间,提供了长期的数据观察。 细节丰富:包含了每次骑行的详细信息,如日期、时间、天气条件、季节等,有助于深入分析。 用户分类:数据中区分了注册用户和临时用户,可以分析不同用户群体的使用习惯。 天气和季节因素:包含了天气情况和季节信息,可以研究这些因素对骑行需求的影响。 通过分析这个数据集,可以得出关于自行车共享使用模式的多种见解,比如一天中不同时间段的使用高峰、不同天气条件下的使用差异、季节性变化对骑行需求的影响等。这些信息对于城市规划者、交通管理者以及自行车共享服务提供商来说都是非常宝贵的,可以帮助他们优化服务、提高效率和满足用户需求。同时,这个数据集也

Global site tag (gtag.js) - Google Analytics