确认Java LinkedList"foreach"循环

Question

美好的一天,

有人可以确认在这篇文章的底部说了什么java - 迭代一个链表 该帖子提到你可以使用for(char c:linkedlistofchars)语法,它仍然是O(n).我想要访问一个看起来像这样的列表......

a b c d e f

实际上在for循环的每次迭代期间都会在链表的开始处运行,就像这样......

a ab abc abcde abcdef 

导致访问时间不是O(n).

这究竟是如何工作的？它对数组和数组运算符有意义,但java语法如何知道如何使用java中的foreach循环遍历链表？

我认为LinkedList数据结构只是一个额外的库,而不是核心语言语法的一部分.(我确实知道LinkedList类在java中是标准的)

我希望我能够清楚地解释我的担忧....谢谢

Answer 1

首先,任何实现的类的实例Iterable都可以在foreach循环中使用.原因是编译后,for (Suit suit : suits)实际上变成了for (Iterator i = suits.iterator(); i.hasNext(); ).有关详细信息,请参阅此说明.

集合实现了特定于数据结构的优化迭代器.具体来说LinkedList,迭代器保持指向最后返回的对象的指针,以允许恒定的时间next()和previous()操作.因此,使用foreach-loop迭代链表将导致O(n)时间复杂度.您可以查看源代码以获取更多详细信息.