Confirm Java LinkedList "foreach" loop

Question

Good Day,

Can someone confirm what was said at the bottom of this post java - iterating a linked list The post mentions that you can use the for(char c: linkedlistofchars) syntax and it will still be O(n). I would think accessing a list that looks like this...

a b c d e f

would actually run start at the beggining of the linked list during every iteration of the for loop, like this...

a ab abc abcde abcdef 

causing the access time not to be O(n).

How exactly does that work? It makes sense with an array and the array operators, but how does the java syntax know how to iterate through a linked list using the foreach loop in java?

I thought the LinkedList data structure was just an additional library and not part of the core language syntax. (I do realize that the LinkedList class is standard in java)

I hope I explained my concern clearly enough.... Thanks

Answer 1

First of all, any instance of class that implements Iterable can be used in a foreach loop. The reason is that after compilation, for (Suit suit : suits) actually becomes for (Iterator i = suits.iterator(); i.hasNext(); ). See this explanation for more detail.

And collections implement optimized iterators, specific to the data structure. Specifically to LinkedList, the iterator keeps a pointer to the last returned object to allow constant time next() and previous() operations. Therefore, iterating over a linkedlist using foreach-loop will yeild O(n) time complexity. You can look at the source code for more detail.