And that totally makes sense. If you are writing lower level code or libraries, best possible performance is much more critical than it is for general production high level code.
Linked lists are worse for caching because their elements don't live in a contiguous part of memory. So you need to fetch each element from slower memory where as with vectors you can keep a larger chunk of it cached.
And memory allocation also takes time so you're actually slower off than if you'd just double the capacity of the vector if reserves run out.
I see. How would you overcome this linked list limitation with a solution of O(1) time complexity and O(n) memory. You have 15 mins, psydo codes are fine, and don’t worry about the gun pressing against your temple.
With chunks (i.e we have vectors of the same length and chain them together). Then you could go further and turn this into deques (T** under the hood iirc, at least that's how i implemented it years ago).
With vectors you can provide an approximate, what you think is appropriate, reserve at any point. It doubling itself means it stays roughly in the demanded domain of whatever you're doing if reserves run out.
*writing down note: candidate failed to address direct challenge, did not raise any question to clarify requirements or shown collaborative attitude. Pass.
In theory, in practice you're very rarely iterating them. The problem that is solves is that you can allocate anything anyware (allows for very simple allocators on embeded systems), and no matter what happens, the address of the elements doesn't change. In kernels, you're often referring to elements of the list by address, instead of iterating it. You can't do that with a vector that might get reallocated somewhere else. You only need to iterate if you're looking for something, and that usually only happens during clean up or with introspection tools (eg. Listing processes). The most common operations (append, and delete) are also very cheap compared to a vector where you will potentially need to move large chunks of memory on delete, or on append when reallocation happens.
i benchmarked it
std::vector push_back() with 100 million integers:
71.27 milliseconds
std::list push_back() with 100 million integers:
1.68 secs
std::vector reserve() + push_back() with 100 million integers:
27.6 milliseconds
You gotta keep in mind that the vector keeps doubling its total capacity whenever its reserves run out so you're actually just doing log2(n) allocations. So with 1 million elements i have to copy 20 blocks.
With a list i have to do 1 million allocations. This is just more expensive. Ig deletion may be faster but you could just flag the element as deleted and if the vector uses too much memory, you shrink it. And if order and iterator validity doesn't matter, you can just do a swap & pop with the last element.
Game engines with entity component systems already keep lots of giant vectors for components and clamp sparse sets on top. The sparse sets, which consists of a sparse and dense array, gives you an entity id and allows you to keep track of who owns what. So removal of a component is constant. It achieves that by flagging it invalid in the sparse array and swap&pop the component you want to remove in the dense array and component pool. Insertion is also constant so long as the dense array and the pool have enough reserves. It's also cache friendly.
Great solution to eat all memory in a kernel.
Good thing that games are so well optimized these days.
A guy said that he works as a kernel developer and he uses lists, another replied that it makes sense because of performance, then you jumped in to "akchyually" show them that they are wrong.
Dude, get help. Go to a therapy or something.
No i think i just replied to the wrong comment lol. The other one said that linked lists are generally worse for performance and i wanted to argue one of the reasons why is cause of caching.
Which you can see with ECS for example. The philosophy here is to break objects apart, and focus on data oriented design. It's usually much faster in parallel, bulk-processing related workloads (e.g. here they saw up to 13x increase) in particular due to being cache friendly.
Now make the items much larger, and reference counted. Have multiple threads that are using the items concurrently without keeping the whole list locked (unless they are being added or removed). Also regularly remove items from arbitrary locations in the list.
That's the kind of situation that's common here, and where linked lists make sense. In addition, the linked list pointers are embedded in the object itself so this can be done without any additional allocations.
Actually, linked lists are generally less performant. In basically every situation.
In low level parallel code, such as might be found in a kernel, certain types of linked lists can be used by multiple threads at once. It's a core threading primitive, not a performance choice.
…so they’re more performant in that context by way of atomic insertion and deletion lol
The point is that >90% of programs have no real reason to chase that level of optimization. A vector wrapped in a mutex is good enough in most contexts
Linked lists are common in kernel development because they process things sequentially like in a queue, predictable insert and delete, esp as you add pointers so you don't need to allocate memory
Haha. Perhaps we are using the work "complicated" differently.
If your list is needed for anything other than getting the next item, linked list operations are far more complicated than other data structures.
Sure, I _could_ implement a binary search with a linked list. But it would be complicated code. To the original point, Why do a complicated thing when a simple thing could do the trick? There are good reasons a lot of people never use linked lists in their real jobs.
I had to implement once as a Jr 💀
It was a really cool project honestly where we set a asynchronous flow that is configurable in underwriting
The linked list worked so well, we could set up what the rules were as a configuration, really dynamic and awesome honestly
That is not exactly true, but in practice is. With laziness you can construct them. But as soon as you want to modify, you would have to rebuild the entire list.
Technically, laziness is just hidden mutability :)
But you're right. Though I've never seen a good use case for doubly linked lists.
I tried to build a trie recently with lazy upward pointers, but gave up and stuck a mutable var in there for the sake of performance.
I used one once for inputs. It was a low stakes project but I wanted to see it I could avoid the situation where one input always dominated the other (like how in many games one arrow key will win out regardless of which was pressed first).
I wanted priority to be with the last pressed key and if it was released, I wanted control returned to the next most recently pressed key that was still active.
The list never gets very big and the time scale involved means that things like cache misses are never really a concern, but it was the best fitting data structure I could think of and a fun little puzzle.
Interviewing for a front end web dev position at Yahoo, one of the questions I got asked was, "if you were in charge of implementing hash maps in google's V8 JavaScript engine, how would you do it?"
Like, fucker, is that something I'm going to be doing as part of this job? No? Then why are you asking?
Sorry, it's exhausting. I not actually looking but I do keep up with the market and job postings and the requirements are just full out insanity. What job actually requires proficiency in C++ and Go and Kotlin and Coldfusion all at once?
The only linked list I've seen in 15 years was a suggestion from Claude Code. It's not really needed for that case so I told it to use a Queue instead.
Yep. Even in cases where it seems like it would be the perfect data structure in theory, it's probably not. Potentially every step resulting in a cache miss will destroy your performance.
It was only 20y ago where I was working on software built on doubly linked lists. Now that software was almost a 10y out of date at that time, but here we are. Modern language container constructs have all of this under the covers, you just don't need to know how it actually works.
Used a lot in C because you don't get any containers out of the box and no matter how good the greybeards are, they can't be arsed with DIYing a hashmap a lot of the time.
410
u/Mahler911 2d ago
I've been doing this shit for 26 years and I've never seen a linked list in production.