美好的一天,
有人可以确认在这篇文章的底部说了什么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中是标准的)
我希望我能够清楚地解释我的担忧....谢谢
我有一个通用的实践，可以使用O（）表示法确定一小段代码的复杂性。
代码是：
for (int i = 0; i < list.size(); i++)
System.out.println(list.get(i));
有问题的列表是链接列表。对于我们的实践，我们给了现成的LinkedList类，尽管我们必须编写自己的size()和get()方法。
使我困惑的是在最终计算中该算什么。问题问：
如果列表中有100个元素，它将进行多少次查找？基于此，使用O（）表示法计算程序的复杂度。
如果我只是在计算get()方法，它将平均进行n / 2次查找，从而导致O（n）的O表示法很大。但是，for循环的每次迭代都需要重新计算size（），这涉及到查找（以确定链接列表中有多少个节点）。
在计算此代码的复杂度时，是否应考虑到这一点？还是计算大小不算作查找？