Question on LinkedList.remove() vs Iterator.remove() , my university notes have me baffled!

This is what the lecture slides state:

LinkedList.remove must walk down the list each time, then remove, so in general it is O( n^2 )

Iterator.remove removes items without starting over at the beginning, so in general it is O( n )

However I am having trouble understanding this, surely if LinkedList.remove() steps down the list each time it is O( n ) because the list contains n elements and since Iterator.remove() doesn't step down the list it is O( 1 )?

Can someone please explain why the big-O values are n times what I expect them to be? I don't want to write anything in my notes I don't fully understand and I couldn't find anything helpful in the course textbook or on the web.

Many thanks!

Posted Feb 21, 2016, 9:35 PM UTC

310
Loading comments…