发帖    主题    评论    推荐    标签    作者    订阅    查搜    注册   登陆   关注
 
面向对象 设计模式 领域驱动设计 企业架构 框架 开发教程 微服务 大数据 扩展性 并发编程 事件驱动 分布式 SOA

LinkedList到底什么时候用?

2009-04-29 23:21
赞助商链接

做了5年多项目,一直很少用LinkedList,一般都用ArrayList.有时碰到面试问起二者区别。于是仔细研究了一下。发现二者实现方式上相差很大。
ArrayList内部是通过一动态数据存储的。所以查找数据很快。根据INDEX,查数据效率高。数据存储在数组中。
LinkedList内数据根本没有固定的容器存储。而是通过对象关联引用,一层一层深入下去的。简单的说,就是保存在一个对象的无限引用中,引用链有多深取决数据量的大小。 具体数据结构如下:
Entry<E> {
E element;
Entry<E> previous;
Entry<E> next;
}

所以无论是查找还是插入,删除,都要从第一个元数据开始找。这样效率自然就很低。

有很多人说,LinkedList查找效率比ArrayList效率差。但批量添加或删除效率比ArrayList高。

前者很好理解。后者我测试了,LinkedList怎么都效率不高。批量添加或删除效率也不比ArrayList高。
大家有没有用过LinkedList,他究竟有什么好处。我看来除了数据结构设计的链表类,实际上很少用,不知道有什么用。 唯一发现有个用处,好象是在JDK里设计缓存策略时有用。

4
2009-04-30 09:33

做LRU缓存时用。

2009-04-30 09:53

还是有不同的,
ArrayList和LinkedList在作为List接口使用的时候,主要区别就是随机访问(按照index进行查找删除等等操作)效率,ArrayList的随机访问效率当然会高;如果你的程序很少应用随机访问,那使用LinkedList不会是比ArrayList更差的选择。ArrayList最没有效率的地方就是频繁的添加操作,这个操作可能会引起ArrayList的扩容,扩容的时候会copy数组浪费点时间,而LinkedList没有扩容时的问题。
还有一个地方不同:LinkedList实现了Deque接口,如果我们需要队列操作,那声明LinkedList的实现为Deque类型是非常方便的,ArrayList没有实现这个接口。

赞助商链接

赞助商链接

返回顶部

移动版 关于本站 使用帮助 联系管理员 最佳分辨率1366x768
OpenSource JIVEJDON Powered by JdonFramework Code © 2002-20 jdon.com