Hello,
ever since I started getting into low level programming I pretty much only used ArrayList because of its nice properties.
Whenever I considered using a linked list I found that I can emulate e.g. the pointers staying the same as indices that I track in a second arraylist.
I honestly dont know whats more performant and thats why im asking how you guys reason about the two structures.
To more precisely ask my question: Whats the point where you say “Time for a linked list”
When I know I’m not going to be searching the list often or at all, but I know I’m going to be inserting into it/deleting from it often (specifically inserting/deleting at arbitrary points, as opposed to appending/popping from the end).
Relevant link:
Relevant Zig PR where a linked list was not the right data structure due to a lot of searching:
(note also that the changes in that PR have been obsoleted after that allocator was rewritten to avoid the need to search for buckets entirely)
Linked lists are nice for freelists (although I prefer to use indizies in freelists too) or with intrusive data structures where you can have an item be part of multiple different collections, so basically in scenarios where there is no search necessary, just either adding the item or removing/processing them.
But I think it is always good to think about and measure what the linked list actually gives you and consider whether you could get better performance by avoiding it.
Linked lists can be pretty terrible, so be careful when using them and convince yourself that you aren’t trashing your cache etc.
But overall I would say it really depends on algorithmic details and then it is more a question of what is the right data-structure from a whole bunch of different data-structures.
If you have real-time constraints, a linked list may be appropriate if you would like to be able to grow / shrink / insert the list in deterministic constant time (like microseconds), or avoid syscalls when growing the list (by using some pre-allocated memory pool).
Real-time pop / append can be accomplished with fixed memory pool and array list, but not insert. Linked list also provide ability for O(1) insert.
Applications with real-time constraints are things like audio / video capture, industrial controls / networking.
Probably the most interesting property of a linked list is that splits and joins are both O(1), and neither of them allocates. There are times when this property is useful.
They’re also good when the data shape is mostly a list, but not entirely. Consider something like an undo/redo buffer: just a bunch of commands, they can be undone, and anything undone can be redone using the same struct. You can store this in an array, but if you do, you’re stuck: once the user does something new after an undo, all of the redo capability is lost, because you have to start overwriting it.
With a linked list, you can just split, turn it “sideways”, and make the alternate history a node in the main-line list. Of course, at that point, strictly speaking, you have a tree. But not really a tree, because your alternate history sticking off the side is data, you don’t reach it with the usual list traversal. That kind of flexibility can come in handy.
This also has the nice property that your place in the tree is an object, rather than the combination of an aggregate and an index. For this kind of complex system, that can be a lifesaver.
Linked lists are nice when the data is only a list sometimes. Let’s say you have macros. Just a list of commands (this is an array for our purposes), you send them off to whatever executes the commands, things happen, it finishes the macro.
Ok, but, what if the macro calls a macro?
Again, you can have a stack of macros here, implemented as an ArrayList or whatever we’re calling it, but now you’re always dealing with a stack, working off the top of it, when what you wanted to be doing is playing back a macro. Really you want the macro itself to be an ?*Macro, so that you only execute it when there is one. This is less elegant with an array, although I’ll admit that checking if the array is empty does accomplish the same thing. The point is that macro-calls-macro is this inconvenient corner case which you don’t want to be constantly handling, the normal case is just one.
So you can add a prev field to the macro struct. If your macro calls a macro, the current macro gets put in that prev field of the new macro, and life goes on. Each time the command loop returns to the macro executor, it’s just executing a macro, and your code only has to deal with it as a stack when it has to.
Whenever you reach the end of a macro, you just check if there’s a stack, and pop it back in place if so. Since your prev field is a ?*Macro, and your execution is storing macros as a ?*Macro, you just assign prev and the next round of execution does whatever it needs to do.
Oh, and by the way, you might want to check that stack when an incoming macro arrives, just in case you’re executing a copy of it already. Vim doesn’t ^_^.
Linked lists are good for that kind of semi-principled ad-hoccery.
I genuinely found all your answers really interesting and helpful, so instead of marking one as a solution ill just mark this message, indirectly referring to all of your answers here.
The idea of needing something not super-fast most of the time but just always somewhat fast but consistently faster than some time constraint makes a lot of sense to me!
I’ll definitely read some of the links you provided, I appreciate the help!
I think in most cases you can either just use an ArrayList, if you are fine with reusing items in LIFO order, or you can use a resizable circular buffer queue if you want FIFO.
I guess the one nice thing about linked lists, for a free list, is that you can place the nodes directly into the free memory block instead of having an external list. Additionally it is also easier to use lockfree algorithms with linked lists, but most of the time a mutex should be fast enough anyways.