谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1375|回复: 15
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
CSTeen 发表于 2015-10-20 01:50:01 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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 总结很精辟
candy_shmily + 10 谢谢你的介绍!
victorsterling + 20
whdawn + 20

查看全部评分


上一篇:4sum, 这样写算是O(N^2)么?
下一篇:这Hard题 Scramble String的DP解法有点烦人啊!
我的人缘0
peizhongxu 发表于 2015-10-20 05:51:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
上周刚刚学完数据结构线性表这里!转专业路漫漫~
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
dongyu2015 发表于 2015-10-20 06:00:04 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (2) 【我投】
给楼主大赞
回复 支持 反对

使用道具 举报

我的人缘0
plich 发表于 2015-10-20 09:46:34 | 显示全部楼层
  此人我要顶:
 
35% (7) 【我投】
  此人我要踩:
 
65% (13) 【我投】
对应c++里面的vector和deque么?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| CSTeen 发表于 2015-10-20 10:07:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
plich 发表于 2015-10-20 09:46
对应c++里面的vector和deque么?

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

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| CSTeen 发表于 2015-10-20 11:53:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
peizhongxu 发表于 2015-10-20 05:51
上周刚刚学完数据结构线性表这里!转专业路漫漫~

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

使用道具 举报

我的人缘0
 楼主| CSTeen 发表于 2015-10-20 12:09:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
666666fl 发表于 2015-10-20 10:24
还有一点面试的时候被问到了。vector在内存上是连续的,所以cache读取时根据spatial locality可能会把一大 ...

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| CSTeen 发表于 2015-10-21 01:58:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
坐看云起 发表于 2015-10-20 12:25
有个疑问:
对于尾部增加数据,ArrayList和LinkedList哪个更有?
个人认为应该是ArrayList吧,因为不需要 ...

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

使用道具 举报

我的人缘0
 楼主| CSTeen 发表于 2015-10-21 02:01:37 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
whuwangyi 发表于 2015-10-20 12:17
java里面也有deque,两个deque是对应的。

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

使用道具 举报

我的人缘0
hdy0616 发表于 2015-10-21 04:06:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
非常受用,总结得很好
回复 支持 反对

使用道具 举报

我的人缘0
666666fl 发表于 2015-10-22 04:51:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
坐看云起 发表于 2015-10-20 12:25
有个疑问:
对于尾部增加数据,ArrayList和LinkedList哪个更有?
个人认为应该是ArrayList吧,因为不需要 ...

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

使用道具 举报

我的人缘0
坐看云起 发表于 2015-10-22 05:59:46 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
666666fl 发表于 2015-10-22 04:51
这个问题我面试的时候被问到了。如果说你push element这个动作的分布不是很均匀的话,最好用List。因为ar ...

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

使用道具 举报

我的人缘0
AndrewFish 发表于 2015-10-22 06:11:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
不是说面试的数据结构都要自己实现吗
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html






手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-25 18:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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