6

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

Community
  • 1
  • 1
Matthew
  • 3,886
  • 7
  • 47
  • 84
  • 1
    foreach loop uses the Iterator provided by the underlying class. So it would actually be O(n). See [this](http://stackoverflow.com/q/85190/845279) post. – user845279 Jun 15 '12 at 01:29
  • Oh okay, cool, thanks for the confirmation. I can sleep easier now :) – Matthew Jun 15 '12 at 01:31
  • Check http://stackoverflow.com/questions/85190/how-does-the-java-for-each-loop-work for further details. – Butaca Jun 15 '12 at 01:32

2 Answers2

11

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.

user845279
  • 2,794
  • 1
  • 20
  • 38
2

The code example at this link demonstrates the difference. The OP at that link is wrong: calling list.get(i) will start at the beginning of the list each time and then count until i is reached, while a iterator.next() will save your place in the list, so each time it is called it only needs to read the next value, not all of the values between 0 and n.

kaz
  • 675
  • 2
  • 5
  • 13