黑马程序员技术交流社区

标题: ArrayList和LinkedList的区别 [打印本页]

作者: homeless 时间: 2014-3-4 10:40
标题: ArrayList和LinkedList的区别
ArrayList：底层是数组结构，它的增加和删除相对麻烦，修改很快。LinkedList:底层是链表结构，增加和删除，修改都很容易，这两点我没啥疑问。

关键是查询？？？？？两者在效率上有多大区别呢？？？？？

打个比方，要在一堆人里找张三。用数组就好比，从里面抓一个出来问他“你是张三吗”，问完扔一边。
用链表就好比是从里面抓一个（周期），问他“你认识张三吗”，他说“我不认识，我认识王五，你问王五”
我这样想感觉查询效率都差不多，都要从头到尾一个一个判断的。

链表.png (3.8 KB, 下载次数: 27)

作者: 老貓钓鱼 时间: 2014-3-4 10:56
因为他们在内存中的存储方式不一样，数组结构的在内存中的存储方式是连续的，而链表结构的在内存中的存储方式是分散的

作者: xietansheng 时间: 2014-3-4 11:06
ArrayList是基于数组实现的，存储的对象引用在内存中是连续的；
Linkedlist是基于链表实现的，存储的对象引用在内存中是不连续的，
ArrayList搜索速度快，增删改查慢；
Linkedlist搜索速度慢，增删改查快

作者: 吴涛 时间: 2014-3-4 11:28
ArrayList:底层的数据结构使用的是数组结构。就是内存地址是连续的，可以通过数组的脚标直接进行访问数据，查询速度很快，但是删除稍慢，是因为在增删元素前要进行元素的移动，
LinkedList:底层使用的是链表数据结构。它的内存地址不一定是连续的，要对其进行访问数据，一般要从链表头到链表结束，一个一个查询，不像数组可以直接通过角标进行访问，所以查询稍慢，由于链表增删元素，不需要进行元素的移动，直接插入即可，所以，增删的速度很快

作者: 薛旻 时间: 2014-3-4 11:29
一方面是他们的数据结构决定了物理结构，所以数组结构存储位置连续的，链表就很随意了，这方面想的话，数组貌似效率高点，不过以现在的CPU速度如果数据不是很多的话，看不出来明显区别
另一方面，链表每个元素只知道自己后面的那个，所以你的查找不论怎样都得从头开始，但是如果从数组的话比如你查到了中间某个位置，做了标记，然后想查找标记之前的某一个元素，那么你就可以再倒回来，但是链表的话你又得从头开始找一遍了
两者相较，查找数组方便很多，效率自然高

作者: chenfc8578 时间: 2014-3-4 12:23
ArrayList：底层使用的数据结构是数组结构。特点：查询速度很快，但是增删稍慢。
LinkedList：底层使用的是链表数据结构。特点：增删速度很快，查询稍慢

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2