4 ms·
> A particularly beautiful outcome is that the implementation has consistent semantics for the edge cases Not sure if this is actually a benefit or not. Edge c
by dvt 6y ago
> A particularly beautiful outcome is that the implementation has consistent semantics for the edge cases
Not sure if this is actually a benefit or not. Edge cases are notoriously hard to debug, so it's sometimes actually nice to have a branch that specifically handles edge cases. Conceptually, it's also much more difficult to wrap one's head around. I would be interested to see how much of the cs101 solution is compiled away and if there are any tangible benefits of being clever here.
PS: If the linked list is stored in contiguous memory (if you're using a slab allocator, for example), you can actually be even more clever (I'll leave that as an exercise to the reader).
- cjaybo 6y ago> PS: If the linked list is stored in contiguous memory (if you're using a slab allocator, for example), you can actually be even more clever (I'll leave that as an exercise to the reader). This might be a dumb question, but if list elements are stored contiguously, is there any advantage to using a linked list instead of a data structure that is designed for contiguous storage (something like C++'s std::vector)?
- matvore 6y ago> if list elements are stored contiguously, is there any advantage to using a linked list Storing them contiguously probably implies that you consider "freed" space in the middle to also be part of the contiguous area. Otherwise you can't remove in O(1) time. It is straightforward to maintain a list of freed nodes which you can add back later. If you don't mind not being able to remove in O(1) time, you still have the advantage of passing the handi-capped (contiguous) linked list to interfaces that expect a linked list, but still get the cache locality of a plain vector.