Menu
Inserting into a linked list is O(1) because the list is not sorted. This means that every “insert” happens at the head of the list. Inserting at the head of the list is just the swap of a few pointers, considered O(1) as it takes the same amount of time no matter how big the list is.
A LinkedList consists of a chain of nodes; each node is separated allocated. And so while inserting, it's not necessary to traverse all the nodes. And that's why it has the complexity O(1) .
The task is to insert the given elements at the middle position in the linked list one after another. Each insert operation should take O(1) time complexity.
Worst time complexity for inserting into list is O(n-i) , where n is the length of the list and i is the index at which you are inserting. So in case if you are inserting at the last index, that makes it O(1) .
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).
The insertion itself is O(1). Node finding is O(n).
No, when you decide that you want to insert, it's assumed you are already in the middle of iterating through the list.
Operations on Linked Lists are often done in such a way that they aren't really treated as a generic "list", but as a collection of nodes--think of the node itself as the iterator for your main loop. So as you're poking through the list you notice as part of your business logic that a new node needs to be added (or an old one deleted) and you do so. You may add 50 nodes in a single iteration and each of those nodes is just O(1) the time to unlink two adjacent nodes and insert your new one.
For purposes of comparing with an array, which is what that chart shows, it's O(1) because you don't have to move all the items after the new node.
So yes, they are assuming that you already have the pointer to that node, or that getting the pointer is trivial. In other words, the problem is stated: "given node at X, what is the code to insert after this node?" You get to start at the insert point.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With