Confirm "foreach" loop for Java LinkedList

Question

Good afternoon,

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

abcdef 

actually starts at the beginning of the linked list at each iteration of the for loop, like this ...

 a ab abc abcde abcdef 

forcing access time not to be O (n).

How exactly does it work? This makes sense with an array and array operators, but how does java syntax know how to iterate over a linked list using a foreach loop in java?

I thought the LinkedList data structure was just an extra library, not part of the main language syntax. (I really understand that the LinkedList class is standard in java)

I hope I have explained my concern in sufficient detail .... Thank you

Answer 1

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

And collections implement optimized iterators specific to the data structure. In particular, for LinkedList , the iterator stores a pointer to the last returned object to allow constant time operations next() and previous() . Thus, iterating over a linked list using foreach-loop will be complex in O (n) time. See Source Code for more details.

Answer 2

The sample code on this link shows the difference . The OP on this link is incorrect: the call to list.get(i) will be launched at the beginning of the list each time, and then it will be counted until i is reached, and iterator.next() save your place in the list, so every time, when he should read only the next value, and not all values ​​between 0 and n.