Re:Don’t Think, Just Defunctionalize
by gowld on Wednesday December 23, 2020 @12:04PM
(#25519622)
Remember that a linked list is not necessary worse than a stack if you use it like a stack. Linked lists are essentially the same as stacks (for a sufficiently smart compiler/runtime) if you never mutate at the middle/end and you can garbage-collect the head immediately when it's popped, letting you store the list in a contiguous structure.
[ Parent
| on HN ]
Linked lists are generally implemented using pointers to other linked list nodes which reside in memory not necessarily adjacent to the original node. If the nodes are in adjacent memory, then you still have the indirection of using pointers, and the extra memory used by storing the pointers for each node. In that case, why not use a stack defined over contiguous memory in the first place?