美好的一天,
有人可以确认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中是标准的)
我希望我能够清楚地解释我的担忧….谢谢
解决方法
首先,任何实现Iterable的类的实例都可以在foreach循环中使用.原因是在编译之后,for(套装：套装)实际上变成了(Iterator i = suit.iterator(); i.hasNext();).有关详细信息,请参见
this explanation.
集合实现了特定于数据结构的优化迭代器.具体到LinkedList,迭代器保持指向最后返回对象的指针,以允许常量时间next()和prevIoUs()操作.因此,使用foreach-loop迭代链表将导致O(n)时间复杂度.您可以查看源代码以获取更多详细信息.
