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.
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.
"I have never seen (...)"
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.
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.
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".
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.
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.
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.
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.
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.
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.
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.
Asymptotic complexity is of course only loosely correlated with speed. In real systems with real workload sizes, constant factors matter a lot.
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.
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.)
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.
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.
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.
> No it’s not, it’s about trying to quantify algorithmic complexity.
And what would you say is the goal of quantifying algorithmic complexity?
Thus, the answer to why we care about complexity is "it depends". But it is not always about speed.
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.
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.
I think you would have a hard time finding someone who knows me describe me that way. Maybe the way I related the anecdote here doesn't present me well. I am pretty meek and easily flustered. I don't think I was any more confident back then than I am now which is, alas, not very.
> The fact that you were unable to incorporate this into the conversation
In this case, it was an interview with three other engineers simultaneously (a truly cursed interview format), so it was hard to incorporate much of anything into the conversation. It felt much like I imagine a thesis examination where the three of them were in charge of pacing and questions. (Also, it was ten years ago, so I'm sure my memory has faded.
What I recall was them asking me how I'd do some sort of growable collection. I said I'd probably do a dynamic array. I mean, that is the way 99% of growable collections are done today—look at Java's ArrayList and C#'s List. This is a company that does strictly PC games and I was hiring for a tools position. Dynamic arrays are the right solution most of the time in that context.
They asked what the complexity was. I said something like "Constant time, across multiple appends." They didn't seem to get that and asked what the worst case was. I was some appends are O(n) but amortized across a series of them, it's constant. When I tried to clarify, they said they wanted to move on. I think in their minds I was hopelessly lost and they wanted to get to the next question so that I didn't embarrass myself further.
I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for. My impression was that they had never heard of amortized analysis at all, and thought I was confusing average case and worst case analysis (which I was not). From their perspective, I can see how I looked lost or wrong.
Overall, they had a superior tone that I found off-putting. (For comparison, I didn't get that impression from any of the interviews I had at Google the very next day. My Google interviewers were all kind, engaging, and really fun to talk to.)
> I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for.
This is the type of conversation I tend to enjoy during interview problem solving because IMO it most accurately reflects the type of conversation you'd actually have with teammates when building a system. I also might try to bait this topic by specifying O(1) worst case insertion up front and watch for how the candidate interprets the requirement, what type of questions are asked, etc. If you started implementing an array backed thing I might stop you early and prompt the insertion analysis specifically. However, in my experience people tend to discuss an overview of the solution before writing any code which is a great point to iron out any clear non-starters or missing requirements.
> Overall, they had a superior tone that I found off-putting.
Fair. It's a two way street after all. Even if they were entirely fine and it was all a comms misunderstanding, sometimes personalities just don't gel. Glad you found success the next day!
Yeah, that's fair. I'm not one to gloat usually but I never felt like I got closure from what was a pretty unpleasant interview experience so I couldn't resist the urge to get a dig in.
> This is the type of conversation I tend to enjoy during interview problem solving because IMO it most accurately reflects the type of conversation you'd actually have with teammates when building a system.
My Google interviews were so much better in this respect. The interviewers were really candid and fluid. They did a great job of letting me bring up points that I thought were relevant but not get too ratholed. Overall just a miles better experience.
> sometimes personalities just don't gel.
One way to look at it was that the interview was a success because it established that I likely wouldn't be happy working with those devs and that kind of culture.
This flippant remark followed by the egotistical follow up is the kind of art I read hacker news for, thank you.
If they were not dumb, they would definitely understand what he was saying and not sit clueless.
Working in for example Unity I need to not ever allocate anything per frame if I can help it (and then knowing other gotchas such as that foreach and/or getting the .Count on a list will also cause memory to be allocated).
Of the many scenarios where amortized complexity is not okay, code in a tight loop where predictable performance is key, e.g. code running game logic, jumps immediately to the top of the list. The fact that you were unable to incorporate this into the conversation makes me suspect you were more interested in putting on a show than a practical solution to the task at hand. The worst case performance for a dynamic array is O(n), but the amortized performance is constant. They aren't the same thing.
You may be a different, more mature, engineer nowadays. But, when I encounter the type of persona your story describes I tend to respond with strong no’s irrespective of whether you have since written a textbook.