removal from linkedlist

[knasim]

"This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration." - Not correct for removal. Deleting a node from a linked list is not efficient as you have to traverse the list (in case it is very large list then it will not be optimal) The option is to use Vector.

[trekhleb]

@knasim thank you for your comment.

You're right in case if we're talking about "delete by value" and not about "delete by node reference" functionality. In the case we will need to traverse whole linked list to find the node and then we'll do O(1) deletion.

But the context of the phrase "This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration" is different. It means that deletion of the node from linked list will cost you O(1) in case if you have a pointer to the node. Or for example if you're deleting the head or the tail (pretty common linked list operations). In these case the deletion will indeed be done in O(1) time. Consider following implementation for doubly linked list:

const node1 = linkedList.append('value #1');
const node2 = linkedList.append('value #2');
const node3 = linkedList.append('value #3');

linkedList.delete(node2);

What you will need to do in the last code line is just make node2.previous to be a new parent for node2.next node. It is done in O(1), no search needed.

Another question here is that in current repository the doubly linked list is not implemented. And in current implementation in this repo the deletion operation will indeed be done in O(n) time. But this fact doesn't mean that phrase "This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration" isn't correct.

Does it make sense?