## Iterating through LinkedList in O(n)

Question

I think I have this understanding right, but wanted to double check.

Say we are iterating through a LinkedList like this:

```
for(int i = 0 ; i < lst.size() ; i++) {
System.out.println(lst.get(i));
}
```

`lst.get()`

runs in O(n) time, and we're calling it n times. So, would this code have O(n^2) time?

Sorry if this is a dumb question - just want to make sure I'm getting this correctly. I'm assuming it would be better to use Iterator, where we could iterate through the list in O(n) time?

Show source

## Answers ( 1 )

On a

`LinkedList`

as defined by the JDK...So yes,

`get(n)`

is O(n). Of course, an implementation could try to optimize (keeping track of the last node returned by`get`

, for instance, and potentially navigating from there). Oracle's version doesn't.`get`

calls an internal`node`

method that finds the node:...and

`node`

works as defined above: It starts at the beginning or end, without reference to any previous access:Yes, absolutely. Because the iterator remembers what the next node is rather than re-

`get`

ting it.