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