linked list insertion time complexity?
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?
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?
It's O(1) if you add it at the head (or tail, if you keep track of the tail, too).
But if you insert it in order, then you need to search for the insertion point first, which is O(N).
But if you insert it in order, then you need to search for the insertion point first, which is O(N).
Last edited on
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/
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). |
It's possible that different people are measuring different things.
Inserting at head: O(1)
Searching: O(n)
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)
Traversal to find the insertion point requires linear time. Once the insertion point is given, actually inserting a node requires constant time.
Some sources give results assuming (incorrectly, IMO) that a search operation (a traversal) is required as part of insertion.
Some sources give results assuming (incorrectly, IMO) that a search operation (a traversal) is required as part of insertion.
Last edited on
| I assume that's a typo. It's O(1). |
Right. I meant to type O(1) there. :-( I'll edit it.
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
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
Last edited on
| As a side note, this is why lists excel as standard stacks and queues |
Disagree. IMO the main reason to use a list, is that almost nothing you do to it invalidates pointers or references to the elements.
Both std::queue and std::stack are implemented by default in terms of the double-ended queue container std::deque, which can be thought of as a vector of pointers to arrays.
Last edited on
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.
* 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.
Another important consideration for preferring the standard library list is that it is the container that provides a strong exception guarantee for almost all operations.
Topic archived. No new replies allowed.