I came across the Tortoise and Hare algorithm by Robert W. Floyd, which can find a loop in a linked list, but I can't understand why that would be necessary if the linked list is implemented correctly.
To my understanding, it's to do with when an item is removed from the list, but I can't see how you could have a loop.
Item 1
Item 2
Item 3
Item 4
Let's say we want to remove item 3 from the list. We make the next item in the list, item 4 point back at whatever item 3 was pointing back to (in this case, item 2) and make item 2 point forward to whatever item 3 was pointing at, which is item 4.
Obviously, I'm missing something but I don't know what. I've Googled this and all I can find are people asking how to detect such loops and no explanation as to why it's necessary.
EDIT 1: Not sure why this has been marked as a duplicate. I searched for my answer and could not find it. If whoever marked it as duplicate could link to said post, it would be much appreciated.
EDIT 2: Perhaps I'm not asking the right question. I was watching a video on Java by Tim Buchalka and he said that Java LinkedList iterators don't point to the item in the list, but instead they point between the items in the list (as illustrated here https://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html). He then said it was for a very good reason too, and showed an illustration of how, when an item was removed from the linked list, it caused an infinite loop. However, it made absolutely no sense to me why that would happen.
He went on to mention the Tortoise and Hare Algorithm. Perhaps he has the wrong end of the stick and I can safely ignore him on that?
EDIT 3: Some extra information is that this all came about when he demonstrated that callingnext() on a LinkedList iterator works as expected, but using previous() did not. It returned the same item that next() returned on the previous call.
