Yes, I wanted to change as little as possible to illustrate why you almost always want to close your lists into a ring when using a linked list ;)
It simplifies a lot of algorithms to be able to guarantee no null pointers. It's a very old trick. You trade a lot of conditionals and a risk of null pointers dereference for a smaller risk of non-termination (failure to check for a null pointer is always bad; failure to check for the end is only a problem if the end of the list is actually your termination condition).
You could do a ring with an array and modulus too, but then you end up copying the whole thing to open up slots to insert to maintain the property of your insertion point being separate from the hand.
That may or may not do worse, but likely to depend on cache size and implementation language.
What you'd almost certainly want in a production implementation anyway would in any case be to do away with constantly allocating nodes and just move them to a free list and reuse to avoid dynamic allocation overhead and garbage collection.
I added a second, singly-linked ring version to the gist I linked above. It doesn't save much, as to be able to unlink the hand you need to keep a pointer to the node adjacent to the hand (I changed "direction" in the naming because it feels weird to have a singly linked list with just "prev" pointers, but that doesn't matter), but it does mean a pointer less for each Node and from experience a lot of people struggle to get the pointer updates right for doubly linked lists, and that is a lot harder to get wrong when singly linked...
vidarh|2 years ago
It simplifies a lot of algorithms to be able to guarantee no null pointers. It's a very old trick. You trade a lot of conditionals and a risk of null pointers dereference for a smaller risk of non-termination (failure to check for a null pointer is always bad; failure to check for the end is only a problem if the end of the list is actually your termination condition).
You could do a ring with an array and modulus too, but then you end up copying the whole thing to open up slots to insert to maintain the property of your insertion point being separate from the hand.
That may or may not do worse, but likely to depend on cache size and implementation language.
What you'd almost certainly want in a production implementation anyway would in any case be to do away with constantly allocating nodes and just move them to a free list and reuse to avoid dynamic allocation overhead and garbage collection.
vidarh|2 years ago
1a1a11a|2 years ago