I am learning about linked lists, and trying to understand the time complexity behind insertion, deletion, reading and searching, and I am really confused with insertion. Why is it classified as O(1)? At first I understood this, I just took it as, you just move the node before where you want to insert pointer to the new node. But then I am reading a book, and it talked about having to traverse the entire list to get to the node before, then add in the new node, and the book classified it as O(N) but everywhere else says O(1).
Ive seen somewhere basically saying, you dont include the traversal in this insertion, but why, cause couldnt I just say this with searching, then say searching is O(1) cause by ignoring the traversal, the search would just be 1 step?
The site linked below lists the worse case as O(1), is that wrong then (or am i misunderstanding it) cause I thought then the worst case would then be O(N) would it not, since as you said adding somewhere that you need to search for is O(N)? https://www.bigocheatsheet.com/
It's O(N) if you add it at the head (or tail, if you keep track of the tail, too).
I assume that's a typo. It's O(1).
It's possible that different people are measuring different things.
Inserting at head: O(1)
Inserting when you know the previous node: O(1)
Inserting when you need to search for the previous node: O(n) operation followed by O(1) operation, therefore O(n)
Yes, the worst case is if you insert at the tail every time, starting from head and iterating to the tail to do so. This comes into play when you are keeping the list sorted, so you have to find the location and put it there by going one-by-one each insert.
but the above is, again, an assumption that you have an extra requirement. To just insert in a list with no other conditions is O(1). If you add the 'insert in order' criteria (or some other similar condition), it costs more.
As a side note, this is why lists excel as standard stacks and queues, which insert at the head or tail and read from the head or tail, all simple operations that ignore the middle of the list entirely. If you manage your memory on top of that you will have an extremely efficient tool
I'd say the only reasons to ever use a list are:
* As mbozzi said, if you need objects to never move around once allocated.
* If you need an intrusive list to avoid extra memory allocations.
* If you absolutely need insertion and can easily keep track of pointers to the middle of the structure.