黑马程序员技术交流社区

标题: 关于ArrayList和LinkedList [打印本页]

作者: 今生无憾 时间: 2014-3-4 20:57
标题: 关于ArrayList和LinkedList
本帖最后由今生无憾于 2014-3-5 12:43 编辑

我们都知道 ArrayList 的特性是查询效率快，增删效率低，LinkedList特性是增删效率高，查询效率低。有知道为什么是这样的么？求教~~~

作者: 天凌蓝 时间: 2014-3-4 21:36
因为ArrayList 是有索引的，查询可以通过索引查找，所以比较快，而当增加或者删除某一个元素的时候，需要将在被操作的元素后面的所有每一个元素的位置索引都依次加1或者减1，所以效率会稍低。
LinkedList是前面的元素会记录后一个元素的索引，当查询时，需要通过查找到先前一个元素后才能知道后面的元素，所以查找效率较低，而当增删时，只需要将要被操作元素的位置的后一个的索引交给前一个元素存放就可以了，所以增删速度较快。

作者: 何清林 时间: 2014-3-4 21:36
这是由他们的数据结构不同决定的，ArrayList 的底层结构是数组，数组都有所以，要查询一个元素，直接顺着找哪个索引就行了，就好比，你在班级是22号，老师要找你不用一个个去找，直接找22号就ok了。但是，你想想，一旦你要插入一个数到中间，是不是所有元素都要改变索引（往后挪一位）？这样就慢了。再说LinkedList是链表结构，就好比班里的人手拉手，老师不知道你们的索引，只有你们知道，1知道2,2知道3,3知道4，这样，要找一个元素就要一个个查过去，慢。但是有一个好处，增删，你看我要我要在3,4之间增加一个，后面的数据都不用改变索引，只需要3记住后面的不再是4了，是新的，4记住前面不再是3了，是新的，就ok了，只需要改变2个数，增删块！

作者: Amorvos 时间: 2014-3-4 21:59
ArrayList是线性表的顺序存储，LinkList是线性表的链式存储。
线性表是一种用于存储有序元素，元素可以重复的存储结构。
这是一种常见的数据结构，楼主可以看下介绍
http://blog.csdn.net/kougq819/article/details/5801919

作者: 今生无憾 时间: 2014-3-4 22:49

天凌蓝发表于 2014-3-4 21:36
因为ArrayList 是有索引的，查询可以通过索引查找，所以比较快，而当增加或者删除某一个元素的时候，需要将 ...

感谢~~~感谢~~~感谢~~~感谢~~~

作者: 天凌蓝 时间: 2014-3-4 22:53

今生无憾发表于 2014-3-4 22:49
感谢~~~感谢~~~感谢~~~感谢~~~

不用客气，应该的

作者: 赵卓辉 时间: 2014-3-4 23:15
ArrayList的底层是数组的数据结构，数组的特性是可以通过脚标直接访问，但是要增删的话就要移动此数据后面的数据，因而效率低。LinkedList底层是链表的数据结构，链表的特性是增删十分方便，但是要访问某个数据则必须从头结点依次顺序访问，不具备随机访问的特性，因此查询效率低。

作者: 山治0712 时间: 2014-3-4 23:20
数据结构有关系，毕老师的视频讲的很清楚啊

作者: 行如止水 时间: 2014-3-4 23:51
一个正常的框架都必须对各种数据结构都有很好的支持以应对不同的需求，JAVA设计的这两个集合是很正常的，也是应该的，可能你只用其中一个，但总有人有需求。
你如果学习了数据结构，就明白了这两者的差别以及为什么几乎所有体系化的高级语言都有这两个数据结构的实现方式，例如STL。

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

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