2 ms·
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
by gowld 6y ago
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.
- jpcooper 6y agoLinked 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?