4 ms·
> Linked lists require you to be on the node in order to do an insertion so it’s generally not O(1) it’s O(n) with sky high constants. Re-read my original post
by adwn 7y ago
> Linked lists require you to be on the node in order to do an insertion so it’s generally not O(1) it’s O(n) with sky high constants.
Re-read my original post: "[...] especially if you have callbacks which store a pointer to a list element [...]"
This happens all the time in kernel code or bare-metal programming.
What else can I say? Open the Linux source code [1] and see for yourself.
[1] https://elixir.bootlin.com/linux/latest/source https://elixir.bootlin.com/linux/latest/source
- Retric 7y agoLook we can all agree if you’re writing ASM your going to use goto’s. Further if linked lists are tiny or rarely used, it’s not a problem. If you can ensure the data stays in L2 cache it’s far less of an issue. If any number of things they don’t create problems, but frankly the general case encountered by most programmers are not that. PS: If you don’t feel like pointing to a concrete example, I am going to counter with 99% of the stuff you can find here: www.google.com.