This is because the article that you are reading considered “getting to that index” as a separate operation. The article assumes that you are already at the index you wish to perform add(int, E). To conclude: Insert or Remove operation = O(1) Finding node at nth index = O(n)
You can detect it by simply running two pointers through the list, this process is known as the tortoise and hare algorithm after the fable of the same name: First off, check if the list is empty (head is null). If so, no cycle exists, so stop now. Otherwise, start the first pointer tortoise on … Read more
You are correct, the article considers “Indexing” as a separate operation. So insertion is itself O(1), but getting to that middle node is O(n).