News for hackers. Stuff that matters.
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @05:29PM (#27887464)
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.

Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @05:50PM (#27887648)
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.

Re:I had to give a wrong answer to get the job (2017) by whatshisface on Monday July 19, 2021 @09:49PM (#27889309)
I have never ever seen a linked list in a game, anywhere, serving any purpose.
Re:I had to give a wrong answer to get the job (2017) by areyousure on Tuesday July 20, 2021 @12:52PM (#27896146)
Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Wednesday July 21, 2021 @03:18AM (#27903297)
He is still probably technically right.

"I have never seen (...)"

Re:I had to give a wrong answer to get the job (2017) by dcow on Wednesday July 21, 2021 @09:57AM (#27906337)
Nobody responding asserted anything to the contrary. Rather, examples were provided rhetorically and for anybody interested in exploring more.
Re:I had to give a wrong answer to get the job (2017) by dcow on Tuesday July 20, 2021 @12:21AM (#27890033)
Re:I had to give a wrong answer to get the job (2017) by rytill on Monday July 19, 2021 @05:56PM (#27887707)
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.

Re:I had to give a wrong answer to get the job (2017) by emerged on Monday July 19, 2021 @08:23PM (#27888820)
Sorry but your analogy makes no sense because Kiwis are better.
Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @08:50PM (#27888995)
Worth the DVs (;
Re:I had to give a wrong answer to get the job (2017) by thayne on Monday July 19, 2021 @09:00PM (#27889045)
> 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.

Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @06:03PM (#27887777)
> 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".

Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @06:08PM (#27887844)
> 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.

Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @06:29PM (#27888029)
> Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert?

You usually have a pointer to the node where you want to insert.

I don't think many people would suggest using linked lists in cases where you actually do need to seek for the insertion point.

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @05:58PM (#27887731)
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.

Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @05:59PM (#27887744)
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.

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @06:10PM (#27887868)
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.
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @06:13PM (#27887897)
> 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.

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @06:51PM (#27888196)
If I ask for something to be done in O(1) I'm not asking for it to be fast, I'm asking for it to take the exact same amount of time every time no matter what. That might end up being slower, but so what, maybe that's what I need.

If I ask for an O(1) algorithm and you build something that is as fast as possible, faster in every case, but sometimes it's really fast and sometimes it's a little less fast but still fast -- well, then it's not O(1) and not what I asked for. It may be fast, but if it's sometimes faster than at other times it's not O(1).

Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest.

Re:I had to give a wrong answer to get the job (2017) by CRConrad on Monday July 26, 2021 @03:03PM (#27963790)
> Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest.

Maybe not synonymous in the sense of technically exactly equal, but certainly a pretty good approximation -- and absolutely synonymous in the sense that the whole purpose of big-O notation is to be able to reason about speed in more general terms, comparing algorithms in pseudo code in stead of having to actually write the program so you can run it through a benchmark.

So, no: If "the best possible big-O, O(1), does not necessarily mean the fastest," then it isn't actually the best.

Re:I had to give a wrong answer to get the job (2017) by sagarm on Wednesday July 21, 2021 @10:48AM (#27907043)
A hash table has E[O(1)] inserts and lookups. Most people ignore the expected part and just say those operations are O(1).

Asymptotic complexity is of course only loosely correlated with speed. In real systems with real workload sizes, constant factors matter a lot.

Re:I had to give a wrong answer to get the job (2017) by indeed30 on Monday July 19, 2021 @07:20PM (#27888393)
I'm confused - that isn't what I understand O(1) to mean. To me, O(1) means only that there exists some constant that bounds the runtime, while individual invocations can absolutely be sometimes faster.
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @07:33PM (#27888487)
Well, not exactly.

What it really means is that the execution time does not depend on the size of input (n).

What it does not say is how much time it takes to execute, whether it is exactly same amount of time every time or whether there exists some kind of upper bound on execution time.

For example, an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.

Re:I had to give a wrong answer to get the job (2017) by peferron on Monday July 19, 2021 @10:30PM (#27889511)
> an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.

According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) <= M * 1. But according to your own words there's no upper limit to 1/(randFloat()), therefore there's no such constant M, therefore it's not O(1).

(In practice on most systems there would be an upper limit since a float can't be infinitely close to zero, but let's act as if that wasn't the case.)

Re:I had to give a wrong answer to get the job (2017) by randomswede on Wednesday July 21, 2021 @02:56AM (#27903124)
More a case of "f(n) = 1/randFloat() does not have a well-defined limit as n goes to infinity", so it would be hard to say that it fits in ANY complexity class.

What is, however, clear is that its run-time does not depend on the size of the input. And technically, that means we can find a constant (infinity) that always... But, that is pretty unsatisfying.

Re:I had to give a wrong answer to get the job (2017) by dcow on Wednesday July 21, 2021 @10:02AM (#27906418)
Re:I had to give a wrong answer to get the job (2017) by munchbunny on Monday July 19, 2021 @10:22PM (#27889475)
> The whole point of big-O analysis is to be able to reason about how fast a program will be given input size.

It's an important technicality that matters when you are doing performance tuning of code on modern CPU's. Big-O is asymptotic but omits the constant multiplier, so if you're comparing, for example, deletion from a naive binary search tree vs. an unsorted array, it's not necessarily obvious that a tree search on a naive pointer based tree (O(log n)) is faster than a find, swap, and delete (O(n)) until n is sufficiently large.

Another example is iterating through the pixels of a very large bitmap on the order of 10m+ pixels. While iterating through all pixels should be linear to the number of pixels (O(width * height)), assuming it's a row-oriented bitmap, which most are, scanning row by row can be substantially faster than scanning column by column because of caching behaviors.

Point being, big-O and actual performance are not always the same thing because the constant factor can sometimes dominate depending on what you're trying to do.

Re:I had to give a wrong answer to get the job (2017) by dentemple on Monday July 19, 2021 @06:48PM (#27888170)
"Performance" depends on a number of factors beyond the code itself.

To take a real world example, immutable operations in Javascript are often more performant than mutable operations--thanks to the fact that the Chrome Engine "cheats" with its hot path functionality.

However, in Big O, constantly generating new data structures, even within loops, would clearly trash the algorithm's space complexity. On compilers that don't optimize for immutability, the Big O algorithm is more performant; on the ones that do, the immutable approach is more performant.

It's because of example like these that you want to disconnect the concept of "performance" from Big O. Because context matters for the former, while the latter relates only to the algorithm itself.

Re:I had to give a wrong answer to get the job (2017) by DangitBobby on Monday July 19, 2021 @06:51PM (#27888199)
Replying here because I can't to the relevant comment:

> No it’s not, it’s about trying to quantify algorithmic complexity.

And what would you say is the goal of quantifying algorithmic complexity?

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @07:00PM (#27888270)
In cryptography the goal might be to ensure the algorithm always takes the exact same amount of time, or the exact same number of CPU instructions, even if it is slower than alternatives. This is a case where we are interested in complexity without regard to speed.

Thus, the answer to why we care about complexity is "it depends". But it is not always about speed.

Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @07:10PM (#27888324)
BTW I've found that in cases where the reply and/or edit button(s) disappear, refreshing the page usually causes them to appear.
Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @07:49PM (#27888597)
There's a delay before the reply button appears to encourage more thought as discussions get deeper. A HN thing.
Re:I had to give a wrong answer to get the job (2017) by rhizome on Monday July 19, 2021 @08:10PM (#27888738)
In those cases, if you click on the "X minutes ago" timestamp you'll get a single comment view with a reply box. Yours didn't have a reply link in-thread, so just like I did here.
Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @08:10PM (#27888736)
Wow I thought this was some rendering bug for the longest time. Is there any (un)official list of HN quirks, out of curiosity?
Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @06:45PM (#27888150)
No it’s not, it’s about trying to quantify algorithmic complexity.
Re:I had to give a wrong answer to get the job (2017) by benibela on Monday July 19, 2021 @07:23PM (#27888414)
Linked lists are better for immutable/persistent structures
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @07:27PM (#27888442)
If your data structure is immutable, then an array is always faster than a linked list.
Re:I had to give a wrong answer to get the job (2017) by jacoblambda on Monday July 19, 2021 @08:53PM (#27889008)
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.

Re:I had to give a wrong answer to get the job (2017) by sagarm on Wednesday July 21, 2021 @10:53AM (#27907105)
The term you are looking for is pointer stability. It can be a useful property, but you can also get it storing pointers in a vector. That would often be faster in practice than a linked list.
Re:I had to give a wrong answer to get the job (2017) by chakkepolja on Tuesday July 20, 2021 @08:49AM (#27893072)
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..
Re:I had to give a wrong answer to get the job (2017) by jacoblambda on Tuesday July 20, 2021 @01:15PM (#27896465)
Well yes but I've always seen immutable DS as synonymous for persistent DS. What OP refers to I've found to be referred to as fixed, const, const static, or compile-time static data structures.

Of course naming in CS and Math is terrible and we love reusing terminology so that everything is confusing but that's just where we are.

I wasn't trying to be negative towards OP or anything. I just saw that since their comment was downvoted so heavily (which it really shouldn't have been), it might be beneficial to reply with an explanation to clear up any misconceptions and smooth out the conversation.