热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

arraylist和linkedlist内部的实现大致是怎样的

1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList优于LinkedList,因为Ar

1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 
2.对于随机访问get和set,ArrayList优于LinkedList,因为ArrayList可以随机定位,而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时的查询速度,看下面的程序:

123456789101112131415161718192021222324252627282930313233package 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

我得到的输出是:ArrayList消耗时间:15

                 LinkedList消耗时间:2596

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

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

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

12345678910111213141516package 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
这时我的输出结果是:ArrayList耗时:2463

                           LinkedList耗时:15

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

二.空间复杂度

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

12345private 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在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下:

性能总结:

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

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

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

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

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


LinkedList类
     LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。
    注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:
List list = Collections.synchronizedList(new LinkedList(...));

ArrayList类
ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。
size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
和LinkedList一样,ArrayList也是非同步的(unsynchronized)。

总结
  如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。
      尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。

 

arraylist和linkedlist内部的实现大致是怎样的


推荐阅读
  • 在Android 4.4系统中,通过使用 `Intent` 对象并设置动作 `ACTION_GET_CONTENT` 或 `ACTION_OPEN_DOCUMENT`,可以从相册中选择图片并获取其路径。具体实现时,需要为 `Intent` 添加相应的类别,并处理返回的 Uri 以提取图片的文件路径。此方法适用于需要从用户相册中选择图片的应用场景,能够确保兼容性和用户体验。 ... [详细]
  • 捕获并处理用户输入数字时的异常,提供详细的错误提示与指导
    在用户输入数字时,程序能够有效捕获并处理各种异常情况,如非法字符或格式错误,并提供详尽的错误提示和操作指导,确保用户能够准确输入有效的数字数据。通过这种方式,不仅提高了程序的健壮性和用户体验,还减少了因输入错误导致的系统故障。具体实现中,使用了Java的异常处理机制,结合Scanner类进行输入读取和验证,确保了输入的合法性和准确性。 ... [详细]
  • C++入门必备:首个博客知识点汇总
    本文总结了C++初学者需要掌握的关键知识点,特别强调了成员类型的区分。其中,protected成员与private成员在本类中的作用相同,但protected成员允许派生类的成员函数访问,而private成员则不允许。此外,文章还介绍了其他重要的C++基础概念,如类的构造函数、析构函数以及继承机制,为初学者提供了一个全面的学习指南。 ... [详细]
  • 在Ubuntu系统中配置Python环境变量是确保项目顺利运行的关键步骤。本文介绍了如何将Windows上的Django项目迁移到Ubuntu,并解决因虚拟环境导致的模块缺失问题。通过详细的操作指南,帮助读者正确配置虚拟环境,确保所有第三方库都能被正确识别和使用。此外,还提供了一些实用的技巧,如如何检查环境变量配置是否正确,以及如何在多个虚拟环境之间切换。 ... [详细]
  • 本文详细介绍了在 Vue.js 前端框架中集成 vue-i18n 插件以实现多语言支持的方法。通过具体的配置步骤和示例代码,帮助开发者快速掌握如何在项目中实现国际化功能,提升用户体验。同时,文章还探讨了常见的多语言切换问题及解决方案,为开发人员提供了实用的参考。 ... [详细]
  • 并发编程入门:初探多任务处理技术
    并发编程入门:探索多任务处理技术并发编程是指在单个处理器上高效地管理多个任务的执行过程。其核心在于通过合理分配和协调任务,提高系统的整体性能。主要应用场景包括:1) 将复杂任务分解为多个子任务,并分配给不同的线程,实现并行处理;2) 通过同步机制确保线程间协调一致,避免资源竞争和数据不一致问题。此外,理解并发编程还涉及锁机制、线程池和异步编程等关键技术。 ... [详细]
  • Jeecg开源社区正式启动第12届架构技术培训班,现已开放报名。本次培训采用师徒制模式,深入探讨Java架构技术。类似于大学导师指导研究生的方式,特别适合在职人员。导师将为学员布置课题,提供丰富的视频资料,并进行一对一指导,帮助学员高效学习和完成任务。我们的教学方法注重实践与理论结合,旨在培养学员的综合技术能力。 ... [详细]
  • VC维在机器学习中的应用与解析
    VC维在机器学习中的应用与解析VC维是指在机器学习中,一个假设空间能够正确分类的最大样本数量。具体而言,如果一个假设空间能够将N个样本以所有可能的 \(2^N\) 种方式完全分开,则称该假设空间具有N的VC维。VC维是衡量模型复杂度的重要指标,对于理解模型的泛化能力和过拟合风险具有重要意义。本文详细探讨了VC维的定义、计算方法及其在机器学习中的应用,并通过实例分析展示了其在模型选择和评估中的关键作用。 ... [详细]
  • 在使用Block时,正确的声明方法和确保线程安全是至关重要的。为了保证Block在堆中分配,应使用`copy`修饰符进行声明,因为栈中的Block与栈的生命周期绑定,容易导致内存问题。此外,还需注意Block捕获外部变量的行为,以避免潜在的循环引用和数据不一致问题。建议深入研究相关文档,以掌握更多高级技巧和最佳实践。 ... [详细]
  • 利用树莓派畅享落网电台音乐体验
    最近重新拾起了闲置已久的树莓派,这台小巧的开发板已经沉寂了半年多。上个月闲暇时间较多,我决定将其重新启用。恰逢落网电台进行了改版,回忆起之前在树莓派论坛上看到有人用它来播放豆瓣音乐,便萌生了同样的想法。通过一番调试,终于实现了在树莓派上流畅播放落网电台音乐的功能,带来了全新的音乐享受体验。 ... [详细]
  • 二叉树的直径是指树中任意两个叶节点之间最长路径上的节点数量。本文深入解析了计算二叉树直径的算法,并提出了一种优化方法,以提高计算效率和准确性。通过详细的案例分析和性能对比,展示了该优化算法在实际应用中的优势。 ... [详细]
  • 使用for循环构建标准等腰三角形
    通过使用 `for` 循环,可以构建一个标准的等腰三角形。具体来说,每层的星号数量为 `2*i-1`,而空格的数量则为 `(n-i)*2`,其中 `n` 是总层数,`i` 是当前层的索引。通过合理地控制星号和空格的数量,可以确保生成的三角形在视觉上是标准且对称的。例如,对于一个 4 层的等腰三角形,第一层有 1 个星号和 6 个空格,第二层有 3 个星号和 4 个空格,依此类推。这种算法不仅简单高效,而且易于实现。 ... [详细]
  • 在IIS上运行的WebApi应用程序在开发环境中能够正常进行文件的读写操作。然而,在尝试通过FTP访问实时服务器上的文件列表时,遇到了无法显示的问题,尽管服务器配置与开发环境相同。这可能涉及权限设置、FTP服务配置或网络连接等方面的问题。 ... [详细]
  • Netty框架中运用Protobuf实现高效通信协议
    在Netty框架中,通过引入Protobuf来实现高效的通信协议。为了使用Protobuf,需要先准备好环境,包括下载并安装Protobuf的代码生成器`protoc`以及相应的源码包。具体资源可从官方下载页面获取,确保版本兼容性以充分发挥其性能优势。此外,配置好开发环境后,可以通过定义`.proto`文件来自动生成Java类,从而简化数据序列化和反序列化的操作,提高通信效率。 ... [详细]
  • SQLite数据库CRUD操作实例分析与应用
    本文通过分析和实例演示了SQLite数据库中的CRUD(创建、读取、更新和删除)操作,详细介绍了如何在Java环境中使用Person实体类进行数据库操作。文章首先阐述了SQLite数据库的基本概念及其在移动应用开发中的重要性,然后通过具体的代码示例,逐步展示了如何实现对Person实体类的增删改查功能。此外,还讨论了常见错误及其解决方法,为开发者提供了实用的参考和指导。 ... [详细]
author-avatar
农夫三拳
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有