一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 843|回复: 15
收起左侧

[学Java/C#] ArrayList vs. LinkedList对比总结【JAVA】

[复制链接] |试试Instant~ |关注本帖
CSTeen 发表于 2015-10-20 01:50:01 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 CSTeen 于 2015-10-20 11:55 编辑

无论是ArrayList 还是LinkedList都是刷题中常用的数据结构,为此我先总结对比了一下它们俩之间的区别。

首先,显而易见的是,A是基于动态数组的,而L是基于链表哈。

其次,由于L的访问都是需要指针移动的,所以对于random access的情况来说, 明显A在时间复杂度上拥有巨大的优势。为此,遇到相应情况是应选用ArrayList。
但L的好处也存在,就是头尾处数据的提取,甚至,如果数据量较大时,可以说头尾部的数据提取时,如时间复杂有需求优化的话,应选用LinkedList。

最后,再稍微提一下空间复杂度。由于LinkedList的每个点都包含了下一节点的位置(双向LinkedList的话则上下节点位置),所以固定空间开销相对会比较大。
而对于A来说,当数组需要增大时,会根据公式 (N * 3) / 2 + 1的原则扩大(N代表数组原大小,大概是50%的增长量吧),这样当数组原数据量较大时,一次的扩展会增加很多的空间,这样可能会造成大量的空间浪费。为了解决这个问题,我们可以利用ArrayList里的方法trimToSize()来解决。

————————————————————————分界线—————————————————————————

这里总结一些我自己比较常用的方法吧。


ArrayList                                                                                   

.add()           --->  add the element to the end of the A;
.contains()    --->  boolean;
.get()           ---> retrieve the element at specific position;
.remove()     ---> remove the ........;
.removeRange(fI, tI)    ---> remove elements from fI to tI, exclude tI;
.set(i, E)       ---> replace element with E in pos i;
.size()           
.toArray()     ---> return an array with elements from A;
.trimToSize() ---> cut the wasted space;

******************************************************************
LinkedList

.add()  .addFirst()    .addLast()   .offer()  ---> add, offer and addLast are equivalent
.contains();
.element()   .peek()  ---> both return the first element without remove it, diff is when the list is empty, element() returns a NoSuchElementException while peek() returns a null;
.poll()   .remove()    ---> both remove the first element and return it , diff is when the list is empty, remove() returns NoSuchElementException while poll() returns null;
.size();
set(i, E);
pop() push();   ---> pop() is equivalent to removeFirst() ,   push() is equivalent to addFirst();

————————————————————————————————————————————————————

评分

7

查看全部评分

peizhongxu 发表于 2015-10-20 05:51:56 | 显示全部楼层
上周刚刚学完数据结构线性表这里!转专业路漫漫~
回复 支持 反对

使用道具 举报

dongyu2015 发表于 2015-10-20 06:00:04 | 显示全部楼层
给楼主大赞
回复 支持 反对

使用道具 举报

plich 发表于 2015-10-20 09:46:34 | 显示全部楼层
对应c++里面的vector和deque么?
回复 支持 反对

使用道具 举报

 楼主| CSTeen 发表于 2015-10-20 10:07:08 | 显示全部楼层
plich 发表于 2015-10-20 09:46
对应c++里面的vector和deque么?

我不太懂c++啊,但我看c++也有list,应该是比较靠近vector跟list的区别吧,你可以自己研究一下
回复 支持 反对

使用道具 举报

666666fl 发表于 2015-10-20 10:24:53 | 显示全部楼层
还有一点面试的时候被问到了。vector在内存上是连续的,所以cache读取时根据spatial locality可能会把一大部分vector都读取进来,所以vector的iteration会比list更快,尽管看起来都是linear的
回复 支持 反对

使用道具 举报

 楼主| CSTeen 发表于 2015-10-20 11:53:22 | 显示全部楼层
peizhongxu 发表于 2015-10-20 05:51
上周刚刚学完数据结构线性表这里!转专业路漫漫~

哈哈,加油,多总结就好
回复 支持 反对

使用道具 举报

 楼主| CSTeen 发表于 2015-10-20 12:09:26 | 显示全部楼层
666666fl 发表于 2015-10-20 10:24
还有一点面试的时候被问到了。vector在内存上是连续的,所以cache读取时根据spatial locality可能会把一大 ...

赞!arraylist应该跟vector是一样的, 因为它是基于array的,所以内存上也是连续的
回复 支持 反对

使用道具 举报

头像被屏蔽
whuwangyi 发表于 2015-10-20 12:17:34 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-20 12:25:38 | 显示全部楼层
有个疑问:
对于尾部增加数据,ArrayList和LinkedList哪个更有?
个人认为应该是ArrayList吧,因为不需要每次增加数据都trap in kernel,所以效率较高?
回复 支持 反对

使用道具 举报

 楼主| CSTeen 发表于 2015-10-21 01:58:00 | 显示全部楼层
坐看云起 发表于 2015-10-20 12:25
有个疑问:
对于尾部增加数据,ArrayList和LinkedList哪个更有?
个人认为应该是ArrayList吧,因为不需要 ...

trap in kernel是什么意思?我觉的就算有区别可能也不会太大吧,感觉在考虑效率的时候一般情况只考虑较大影响的就行,比如arraylist你在中间某处插入数据是,需要改变数组的大小,在数组装满的时候要将所有的数据重新装入一个新的数组,这样可能需要O(n)的时间,相对应的linkedlist数据插入只需要O(1)。而且每次arraylis容器满了,t需要重新配置数组大小的时候扩充的时间也不小,这样估计平均下来考虑在尾部增加数据的情况应该差不多吧。不过我也不太懂,也是在一边学一遍总结,一起讨论研究哈
回复 支持 反对

使用道具 举报

 楼主| CSTeen 发表于 2015-10-21 02:01:37 | 显示全部楼层
whuwangyi 发表于 2015-10-20 12:17
java里面也有deque,两个deque是对应的。

嗯,我也查了查,java也是有deque的,linkedlist就是基于deque的实现,谢谢补充啦。能不能再帮忙介绍一下一般deque在什么时候会用到?我现在刷题暂时还没接触到
回复 支持 反对

使用道具 举报

hdy0616 发表于 2015-10-21 04:06:06 | 显示全部楼层
非常受用,总结得很好
回复 支持 反对

使用道具 举报

666666fl 发表于 2015-10-22 04:51:27 | 显示全部楼层
坐看云起 发表于 2015-10-20 12:25
有个疑问:
对于尾部增加数据,ArrayList和LinkedList哪个更有?
个人认为应该是ArrayList吧,因为不需要 ...

这个问题我面试的时候被问到了。如果说你push element这个动作的分布不是很均匀的话,最好用List。因为arrayList会变的unpredictable,你不知道他会resize多少次
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-22 05:59:46 | 显示全部楼层
666666fl 发表于 2015-10-22 04:51
这个问题我面试的时候被问到了。如果说你push element这个动作的分布不是很均匀的话,最好用List。因为ar ...

有道理,非常感谢!我当时只想到了kernel mode 和 user mode 转换的问题。。。。
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2015-10-22 06:11:29 | 显示全部楼层
不是说面试的数据结构都要自己实现吗
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 19:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表