📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3835| 回复: 15
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
CSTeen | 只看该作者 |倒序浏览
全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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大米 +105 收起 理由
beer + 5 感谢分享!
南方的狼 + 10 感谢分享!
凌曦 + 21 谢谢你的介绍!
vivaroma + 19 总结很精辟
夏虫不知雪花 + 10 谢谢你的介绍!

查看全部评分


上一篇:4sum, 这样写算是O(N^2)么?
下一篇:这Hard题 Scramble String的DP解法有点烦人啊!
推荐
 楼主| 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需要重新配置数组大小的时候扩充的时间也不小,这样估计平均下来考虑在尾部增加数据的情况应该差不多吧。不过我也不太懂,也是在一边学一遍总结,一起讨论研究哈
回复

使用道具 举报

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

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

使用道具 举报

推荐
 楼主| CSTeen 2015-10-21 02:01:37 | 只看该作者
全局:
whuwangyi 发表于 2015-10-20 12:17
java里面也有deque,两个deque是对应的。

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

使用道具 举报

🔗
peizhongxu 2015-10-20 05:51:56 | 只看该作者
全局:
上周刚刚学完数据结构线性表这里!转专业路漫漫~
回复

使用道具 举报

🔗
然陌语 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的,所以内存上也是连续的
回复

使用道具 举报

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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