LinkedList 应该使用什么样的迭代?
我知道通过索引遍历 LinkedList 是不好的,因为 list.get(n) 是在线性时间 O(n) 内执行的。因此我不应该使用索引。我查看了由 iterator()
调用返回的 AbstactList.Itr
,它也使用 get(cursor)
。我很困惑。
正如@axtavt所指出的,LinkedList.iterator()
实际上调用了listIterator()
,它返回AbstactList.ListItr
,它扩展了AbstactList。 Itr
并且它只添加了 ListIterator
接口的实现。因此,获取下一个元素的机制仍然与 AbstactList.Itr
中的相同。 `AbstactList.Itr
的 next();
在指定列表上调用 get(n)
。
I know that traversing LinkedList
by indexing is bad, because list.get(n) is executed in linear time O(n). Thus i shouldn't use indexing. I looked at the AbstactList.Itr
that is returned by iterator()
call, it uses get(cursor)
too. I'm confused.
As pointed out by @axtavt , LinkedList.iterator()
actually calls listIterator()
which returns AbstactList.ListItr
which extends AbstactList.Itr
and it only adds implementations of ListIterator
interface. Thus the machinery for getting next element is still the same as in AbstactList.Itr
. `AbstactList.Itr
's next();
calls get(n)
on the specified list.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(6)
foreach 循环非常高效且简单:
The foreach loop is very efficient, and easy:
any
List
(实际上甚至anyIterable
)的最佳迭代是 对于每个循环:The best iteration over any
List
(actually even anyIterable
) is the for each loop:LinkedList 不仅继承自
AbstractList
,还继承自AbstractSequentialList
,后者又实现了iterator()
,如下所示:以及
ListIterator
LinkedList
返回的 code> 很聪明地使用顺序访问。因此,无论您使用 foreach、iterator() 还是 listIterator(),您始终处理相同的智能迭代器类型。
LinkedList inherits not only from
AbstractList
, but also fromAbstractSequentialList
which in turn implementsiterator()
like this:and the
ListIterator
returned byLinkedList
is smart about using sequential access.So whether you use foreach,
iterator()
orlistIterator()
, you are always dealing with the same smart iterator type.如果可以的话,您应该使用 foreach 循环 - 这是最有效的:
如果您需要修改循环内的列表,或者在一个循环中遍历多个集合,请使用迭代器:
如果您需要向后遍历,或者其他什么特定于链表,使用
listIterator
:You should use a foreach loop if you can - that's the most efficient:
If you need to modify the list inside the loop, or traverse through multiple collections in one loop, use an iterator:
And if you need to traverse backwards, or something else specific to linked lists, use
listIterator
:您可以使用迭代器,它由
iterator
方法返回。转到下一项不需要 O(n) 时间。它使用LinkedList
的ListIterator
实现,因此速度很快。You can use iterator, which returned by
iterator
method. It doesn't require O(n) time to go to next item. It usesListIterator
implementation fromLinkedList
so it's fast.您可以使用
Iterator
,它可以让您更快地访问。列表的示例代码:You can use the
Iterator
, it gives you a faster access. A sample code for a list: