java - 确认 Java LinkedList "foreach"循环

Question

美好的一天，

谁能证实这篇文章底部所说的内容java - iterating a linked list该帖子提到您可以使用 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(); )。参见 this explanation了解更多详情。

集合实现优化的迭代器，特定于数据结构。特别是 LinkedList，迭代器保留指向最后返回对象的指针，以允许常数时间 next() 和 previous() 操作。因此，使用 foreach 循环遍历链表将产生 O(n) 时间复杂度。您可以查看源代码以获取更多详细信息。