百科狗-知识改变命运!
--

ArrayList、linklist、list的区别

百变鹏仔1年前 (2023-12-17)阅读数 7#综合百科
文章标签数组元素

1、ist是一个接口,ArrayList和LinkedList是两个实现类.

2、他们实现的方式不一样,其实LinkedList才是真正的链表(如果不清楚什么是链表,需要了解一下相关数据结构的知识,这不是一两句话能说清楚的)

3、而ArrayList是用数组实现的,它不是真正的链表,在初始化的时候它先对数组设置一个初始容量,当数组空间不够的时候,它会重新构建一个容量更大的数组,然后把先前的元素拷贝进去。

4、ArrayList和LinkedList本质上的区别就是数组和列表这两种数据结构的区别。课参阅相关数据结构的知识。

5、ArrayList:缺点:内存使用量要大一些,添加删除元素效率较低。元素随机访问的效率较高。

LinkedList:相反

扩展资料

1、ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了ICollection和IList接口,灵活的设置数组的大小等好处。

2、List?接口的大小可变数组的实现,位于API文档的java.util.ArrayList。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。

3、每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。

4、随着向 ArrayList 中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。

5、注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。

参考资料:

百度百科-arraylist

数组和List有什么区别

List:是一个有序的集合,可以包含重复的元素。提供了按索引访问的方式。它继承 Collection。

List有两个重要的实现类:ArrayList 和 LinkedList

ArrayList:我们可以将其看作是能够自动增长容量的数组。

利用ArrayList的toArray()返回一个数组。

Arrays.asList()返回一个列表。

1.ArrayList底层采用数组实现,当使用不带参数的构造方法生成ArrayList对象时,实际上会在底层生成一个长度为10的Object类型数组

2.如果增加的元素个数超过了10个,那么ArrayList底层会新生成一个数组,长度为原数组的1.5倍+1,然后将原数组的内容复制到新数组当中,并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时,重复该过程。

3.对于ArrayList元素的删除操作,需要将被删除元素的后续元素向前移动,代价比较高。

4.集合当中只能放置对象的引用,无法放置原生数据类型,我们需要使用原生数据类型的包装类才能加入到集合当中。

5.集合当中放置的都是Object类型,因此取出来的也是Object类型,那么必须要使用强制类型转换将其转换为真正的类型(放置进去的类型)

Array和List都属于顺序表。

Array是一段连续的存储结构

int[] i=new int[3]

i其实记录的是数组的首地址,而i[1]其实相当于在i的地址的基础上加上1个整数的地址偏移,然后再取这块地址中的值。

List则是不连续的存储结构,List的每个节点都有着一个Next属性,这个属性则记录着他的下一个节点的地址。

也就是说当我们想找第100个节点的时候,他还是需要从第一个节点,然后做99次Next操作,才能找到list[99]节点。

在查找一个元素时时分别生成以下IL码

Array:

IL_0020:  ldloc.0

IL_0021:  ldc.i4.3

IL_0022:  ldelem.i4

IL_0023:  stloc.2

List:

IL_0022:  ldloc.0

IL_0023:  ldc.i4.3

IL_0024:  callvirt   instance !0 class [mscorlib]System.Collections.Generic.List`1::get_Item(int32)

IL_0029:  stloc.2

通过这两段IL,我只是希望证明List和Array对索引元素的方式是不同的。当然,我们无从知道Microsoft对List方法get_Item的实现。但是我们不难想象:

因为List是一个链表,所以我需要从第一个元素开始逐个Next到所需索引的元素。这是一个耗时的过程。

 1. 从空间扩展角度上来说:

数组必须要在初始化时分配固定的大小,比如说int[] a=new int[3];如果我们仅仅写int[] a=new int[];编译器就会无情地给我们报错。但是List由于空间不必连续,所以无须指定初始大小。

总结1: 当不确定大小时,最好使用List代替Array。

2. 从操作角度上来看:

关于索引这个就不赘述了。

总结2:当需要大量的查找操作时,最好使用Array。

对于插入(删除)操作,很多人是从插入(删除)的时间上分析,说List优于Array,我觉得是不合理的。

更合理的解释应该是从两个角度分析(以插入为例):

指定位置插入指定元素:

对于Array讲,有两套解决方案:

A. 使用一个新数组,N+1个元素重新赋值的过程。一个for循环,时间复杂度O(n)。

B. 在原数组上操作,那么首先需要为该数组预留空间,这是个很难办的事情。而且其后续元素的移动耗费时间复杂度仍未O(n)。

对于List来讲,很多人说复杂度就是O(1)。这其实是不合理的,因为List插入元素固然容易,但是在指定位置的插入,需要一个时间复杂度为O(n)的查找过程。

但是只考虑时间复杂度是不够的,我们要考虑总体的情况。如果使用新数组,不仅浪费了新的空间,而且需要反复的赋值过程,是N+1次。如果不使用新数组,预留空间实在太麻烦,因此综上所述,还是List好。

给出前一个节点,然后在后面插入元素。这个我的意思就是不仅仅给出了PreviousNode的Value,还给出了他的Next。这个情况我就不废话了,List的优势太大了。可是在实际情况中,这种情况的可能性几乎为零。

因此,总结3:当需要进行频繁的插入,删除操作时,最好使用List代替Array。

另外,给出个不太重要的补充,由于List需要存储他下一个节点的地址,所以List比Array相对起来浪费了更多的空间。

也就是说虽然使用list强类型范性,能够节约装箱拆箱时间,但查询速度会有很多问题。

在实际使用中,对变化不大,查询次数频繁的,我们应该考虑list外的情况

ArrayList、linklist、list的区别

当然,就查询某个值的速度而言,还是 Hashtable 或 Dictionary 最快,当然这两者和我们在讨论的东西,结构完全不相同,没有可比性。毕竟数组,是节约空间,而hash表是散列的,牺牲空间来换取速度

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com

免责声明:我们致力于保护作者版权,注重分享,当前被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理!邮箱:344225443@qq.com)

图片声明:本站部分配图来自网络。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

内容声明:本文中引用的各种信息及资料(包括但不限于文字、数据、图表及超链接等)均来源于该信息及资料的相关主体(包括但不限于公司、媒体、协会等机构)的官方网站或公开发表的信息。部分内容参考包括:(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供参考使用,不准确地方联系删除处理!本站为非盈利性质站点,本着为中国教育事业出一份力,发布内容不收取任何费用也不接任何广告!)