7 ms·

Unfortunately, you are wrong. Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is

Unfortunately, you are wrong. Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). Linked lists have a lot of huge downsides that are not easily captured in their naive big-O characterization. Big-O does not tell anything about how efficient things are. Two algorithms can have same big-O complexity yet hugely different costs. For example, you can easily parallelize operations on array lists but you can't do that on linked list where to get to next node you need to dereference a pointer. Even without this, you get bonus from prefetching data to cache when searching through array list or when doing things like moving data. Speculative dereferencing pointers is nowhere close to just regular prefetch. Array lists are denser in memory than linked lists (because of additional pointers). This means that a lot of things works just more efficiently -- cache, memory transfers, prefetching, less need to resolve TLBs, etc. Inserting into array list at the end is as fast as into linked list (after taking account for amortized cost), but what not many people appreciate is that finding an insertion place and inserting within array list is also the same cost or even better than in linked list. That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot. Actually, it costs more than copying the same size of array list.

deleted 5y ago
[deleted]
dcow 5y ago
I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case performance. Context is everything. Also some things to note: a) game logic tends not to parallelize very well for various reasons, but even so it depends on the domain of the problem whether or not you can run a parallel algorithm on a linked list, b) if you already have a reference to the insertion point you can avoid the walk, c) cache coherence is only important of you are actually iterating over the list, etc.
- whatshisface 5y ago
  I have never ever seen a linked list in a game, anywhere, serving any purpose.
  - dcow 5y ago
    Here’s one: https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20cb4902f2dc53a0c20a96/source/enet/include/enet/list.h https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20c...
  - areyousure 5y ago
    Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb10315479fc00086f08e25d968b4b43c49/q3map/qbsp.h#L92 https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...
    - lmilcin 5y ago
      He is still probably technically right. "I have never seen (...)"
      - dcow 5y ago
        Nobody responding asserted anything to the contrary. Rather, examples were provided rhetorically and for anybody interested in exploring more.
rytill 5y ago
GP basically created a hypothetical situation wherein they were right, and then here you are saying they're wrong. The only case in which you would be right in saying the GP is unequivocally wrong is if dynamic arrays were Pareto-optimal compared to linked lists. Alice: Can you think of any situation where apples are better than oranges? Bob: Well, if someone had a craving for apples, then they would be better. Charlie: Unfortunately, you are wrong. Even in that situation, oranges are juicier, have more tang, and contain more vitamin C.
- emerged 5y ago
  Sorry but your analogy makes no sense because Kiwis are better.
  - dcow 5y ago
    Worth the DVs (;
Buttons840 5y ago
They were talking about big-O analysis (or whatever you want to call it), then you jump in talking about speed and performance. That's not the same thing, and as you say, may not even be closely related. I think your right, but again, it's not applicable to the point of contention the above comments were discussing. Also, in an interview, it should be fine to talk about all this. It could lead to some good technical discussion where you can show your knowledge. If such a conversation does arise though, remember you have to make these people like you and ramming your point down their throats and forcing them to acknowledge that you're right and they're wrong probably doesn't do that. Also, don't forget you may, indeed, be wrong.
- lmilcin 5y ago
  What is not applicable? If one person says a linked list is faster than an array list but the opposite is true, then why do you claim it is not applicable? Isn't it exactly the point of the article, that sometime you need to say what the interviewer wants to hear rather than what is the actual truth? It is an unfortunate truth that a lot of interviewers will ask about linked lists vs array lists and at the same time will not understand that linked lists will be slower for insertions or deletions in most cases. That is because you first need to find the insertion/deletion place, and any benefit of faster insertion/deletion for linked list will be offset by much slower search.
  - Buttons840 5y ago
    None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed.
    - lmilcin 5y ago
      > None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed. I am sorry, do you want to say "performance" and "big-O" have nothing to with trying to make the program go faster? I think you have lost your way and need to backtrack a little bit. The whole point of big-O analysis is to be able to reason about how fast a program will be given input size.
munificent 5y ago
> Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). I think you're overcorrecting here. There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Today, in many cases, arrays are faster. And that awareness of caching effects is becoming greater. But I think there's a tendency to over-apply new knowledge that seems counter-intuitive. The reality is somewhere in the middle. Arrays can be surprisingly fast, even when you need to shift stuff around to insert or copy to grow. But there are still plenty of cases where linked lists are better if you are doing a lot of inserting or rearranging. I don't think the guidance is so much "linked lists bad!" as it is "arrays maybe not bad".
- lmilcin 5y ago
  > There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Nothing to do with caches or conventional wisdom no longer being true. Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert? Unless you have some kind of index to the list (in which case it no longer is a linked list, it is some other data structure), you have three options: a) at the beginning of the list b) at the end of the list c) in the middle of the list, in which case you need to run linear search to find the place. If you want to do this at the end of the list, then array list has the same amortized cost as linked list. If you need to do this at the beginning of the list, then array list can be reversed. Unless you have the very special case of having to add at both beginning and end of the list. So most likely you need to insert somewhere within the list to see the improvement over an array list. But then you need to do the linear search and the search is so much slower with linked list that it completely offsets the cost of copying of all that data.
  - munificent 5y ago
benibela 5y ago
Linked lists are better for immutable/persistent structures
- lmilcin 5y ago
  If your data structure is immutable, then an array is always faster than a linked list.
  - jacoblambda 5y ago
    Immutable doesn't necessarily mean unchanging in the context of data structures. An immutable data structure can support adding, removing, and/or changing the data but the way it does it is in such a way that once data is created it isn't modified until it is completely unused and unreferenced. So an immutable data structure has the benefit that data stays the same and stays the same in memory so it can be shared where duplication exists. You can copy said data-structure but it won't actually modify the underlying data and will just allocate a new tag/head that holds some reference to the underlying data. Now this new copy can be modified and it will instead just allocate a new block of memory for the changed portion and stitch it in to the head/tag structure as if it was just some diff/delta. Here immutable means that the underlying data is unchanging and can be reused/shared by multiple instances, not that it is unchanging at all from an external point of view. Now in the case of your comment, an array is extraordinarily bad in most cases for an immutable data structure as it is extremely difficult to sub-divide and let go of unused/old parts without breaking that immutability for the in-use data. Linked lists have their own issues as well but can be a valid trade-off for certain types of immutable data structures. Generally though trees will be the primary underlying structure for these immutable data structures as they are easy to use for this purpose, have reasonably good lookup times, have reasonable worst time complexity, and most importantly decent average/amortised time complexity.
    - chakkepolja 5y ago
      Isn't that a persistent DS and I thought OP mistook it for immutable-at-memory-level data structure.. like an array you create once but read many times from..
thayne 5y ago
> That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot. That isn't always true. If you already have a pointer to the position in the list, and the list has an API that supports it (which a good implementation would), then with a linked list you wouldn't need to traverse the list again. That said, in most cases that probably isn't worth the downsides of a linked list, especially if the size of the list is small.

deleted 5y ago

[deleted]

dcow 5y ago

I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case performance. Context is everything. Also some things to note: a) game logic tends not to parallelize very well for various reasons, but even so it depends on the domain of the problem whether or not you can run a parallel algorithm on a linked list, b) if you already have a reference to the insertion point you can avoid the walk, c) cache coherence is only important of you are actually iterating over the list, etc.

whatshisface 5y ago
I have never ever seen a linked list in a game, anywhere, serving any purpose.
- dcow 5y ago
  Here’s one: https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20cb4902f2dc53a0c20a96/source/enet/include/enet/list.h https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20c...
- areyousure 5y ago
  Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb10315479fc00086f08e25d968b4b43c49/q3map/qbsp.h#L92 https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...
  - lmilcin 5y ago
    He is still probably technically right. "I have never seen (...)"
    - dcow 5y ago
      Nobody responding asserted anything to the contrary. Rather, examples were provided rhetorically and for anybody interested in exploring more.

rytill 5y ago

GP basically created a hypothetical situation wherein they were right, and then here you are saying they're wrong. The only case in which you would be right in saying the GP is unequivocally wrong is if dynamic arrays were Pareto-optimal compared to linked lists. Alice: Can you think of any situation where apples are better than oranges? Bob: Well, if someone had a craving for apples, then they would be better. Charlie: Unfortunately, you are wrong. Even in that situation, oranges are juicier, have more tang, and contain more vitamin C.

emerged 5y ago
Sorry but your analogy makes no sense because Kiwis are better.
- dcow 5y ago
  Worth the DVs (;

Buttons840 5y ago

They were talking about big-O analysis (or whatever you want to call it), then you jump in talking about speed and performance. That's not the same thing, and as you say, may not even be closely related. I think your right, but again, it's not applicable to the point of contention the above comments were discussing. Also, in an interview, it should be fine to talk about all this. It could lead to some good technical discussion where you can show your knowledge. If such a conversation does arise though, remember you have to make these people like you and ramming your point down their throats and forcing them to acknowledge that you're right and they're wrong probably doesn't do that. Also, don't forget you may, indeed, be wrong.

lmilcin 5y ago
What is not applicable? If one person says a linked list is faster than an array list but the opposite is true, then why do you claim it is not applicable? Isn't it exactly the point of the article, that sometime you need to say what the interviewer wants to hear rather than what is the actual truth? It is an unfortunate truth that a lot of interviewers will ask about linked lists vs array lists and at the same time will not understand that linked lists will be slower for insertions or deletions in most cases. That is because you first need to find the insertion/deletion place, and any benefit of faster insertion/deletion for linked list will be offset by much slower search.
- Buttons840 5y ago
  None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed.
  - lmilcin 5y ago
    > None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed. I am sorry, do you want to say "performance" and "big-O" have nothing to with trying to make the program go faster? I think you have lost your way and need to backtrack a little bit. The whole point of big-O analysis is to be able to reason about how fast a program will be given input size.

munificent 5y ago

> Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). I think you're overcorrecting here. There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Today, in many cases, arrays are faster. And that awareness of caching effects is becoming greater. But I think there's a tendency to over-apply new knowledge that seems counter-intuitive. The reality is somewhere in the middle. Arrays can be surprisingly fast, even when you need to shift stuff around to insert or copy to grow. But there are still plenty of cases where linked lists are better if you are doing a lot of inserting or rearranging. I don't think the guidance is so much "linked lists bad!" as it is "arrays maybe not bad".

lmilcin 5y ago
> There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Nothing to do with caches or conventional wisdom no longer being true. Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert? Unless you have some kind of index to the list (in which case it no longer is a linked list, it is some other data structure), you have three options: a) at the beginning of the list b) at the end of the list c) in the middle of the list, in which case you need to run linear search to find the place. If you want to do this at the end of the list, then array list has the same amortized cost as linked list. If you need to do this at the beginning of the list, then array list can be reversed. Unless you have the very special case of having to add at both beginning and end of the list. So most likely you need to insert somewhere within the list to see the improvement over an array list. But then you need to do the linear search and the search is so much slower with linked list that it completely offsets the cost of copying of all that data.
- munificent 5y ago

benibela 5y ago

Linked lists are better for immutable/persistent structures

lmilcin 5y ago
If your data structure is immutable, then an array is always faster than a linked list.
- jacoblambda 5y ago
  Immutable doesn't necessarily mean unchanging in the context of data structures. An immutable data structure can support adding, removing, and/or changing the data but the way it does it is in such a way that once data is created it isn't modified until it is completely unused and unreferenced. So an immutable data structure has the benefit that data stays the same and stays the same in memory so it can be shared where duplication exists. You can copy said data-structure but it won't actually modify the underlying data and will just allocate a new tag/head that holds some reference to the underlying data. Now this new copy can be modified and it will instead just allocate a new block of memory for the changed portion and stitch it in to the head/tag structure as if it was just some diff/delta. Here immutable means that the underlying data is unchanging and can be reused/shared by multiple instances, not that it is unchanging at all from an external point of view. Now in the case of your comment, an array is extraordinarily bad in most cases for an immutable data structure as it is extremely difficult to sub-divide and let go of unused/old parts without breaking that immutability for the in-use data. Linked lists have their own issues as well but can be a valid trade-off for certain types of immutable data structures. Generally though trees will be the primary underlying structure for these immutable data structures as they are easy to use for this purpose, have reasonably good lookup times, have reasonable worst time complexity, and most importantly decent average/amortised time complexity.
  - chakkepolja 5y ago
    Isn't that a persistent DS and I thought OP mistook it for immutable-at-memory-level data structure.. like an array you create once but read many times from..

thayne 5y ago

> That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot. That isn't always true. If you already have a pointer to the position in the list, and the list has an API that supports it (which a good implementation would), then with a linked list you wouldn't need to traverse the list again. That said, in most cases that probably isn't worth the downsides of a linked list, especially if the size of the list is small.