3 ms·

Linked lists fare worse than arrays only for sequential iteration in tight loops. That includes many/most cases, but not all. As for O(1) insertion/deletion: It

by adwn 7y ago

Linked lists fare worse than arrays only for sequential iteration in tight loops. That includes many/most cases, but not all. As for O(1) insertion/deletion: It's not always about amortized cost, sometimes you actually do care about worst case execution time. Look, I'm not saying that linked lists can replace arrays. In fact, I almost always use arrays instead of linked lists. What I'm arguing against is the notion that arrays always trump linked lists, which is false, and repeating that meme shows a lack of deeper understanding.

Retric 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. Thus for random inserts arrays are actually faster. If you have a degenerate case and are never traversing nodes, you’re still likely better of with a rung buffer, array list, 2 different stacks, or various other options. And frankly you’re never going to endlessly just insert data without reading it.
- 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 ago
    Look 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.
overgard 7y ago
I don't think I've heard anyone seriously suggest never using a linked list -- the advice usually just ends up being "are you really sure?" which seems appropriate.
- adwn 7y ago
  Then let me quote the post I originally replied to: > The way modern memory works linked lists are practically a denial of service attack on system performance. and > IMO, like goto’s it’s better to just forget they exist. That's as close to "never use a linked list" as you can get without saying that literal sentence.

by adwn 7y ago

Retric 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. Thus for random inserts arrays are actually faster. If you have a degenerate case and are never traversing nodes, you’re still likely better of with a rung buffer, array list, 2 different stacks, or various other options. And frankly you’re never going to endlessly just insert data without reading it.

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 ago
  Look 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.

overgard 7y ago

I don't think I've heard anyone seriously suggest never using a linked list -- the advice usually just ends up being "are you really sure?" which seems appropriate.

adwn 7y ago
Then let me quote the post I originally replied to: > The way modern memory works linked lists are practically a denial of service attack on system performance. and > IMO, like goto’s it’s better to just forget they exist. That's as close to "never use a linked list" as you can get without saying that literal sentence.