munificent
Doubly linked list not necessarily required for O(1) deletion
Hi! Thanks for the great read.
In the Observer chapter you mention:
If we use a doubly linked list, where each observer has a pointer to both the observer after it and before it, we can remove an observer in constant time. If this were real code, I’d do that.
In many cases you can get away with a singly linked list and still get O(1) deletion by just deleting the next node and fixing the data pointers. Meaning - since you have a reference to the current node and the next node you can move the data from the next node onto the current node (essentially making the current node the "next" node) and then delete what was the next node.
This has some side effects - like any outside references to the next node are invalidated. Also deleting the last node in the list is tricky but you can handle that by using an end-of-list node.
Possibly too much of a diversion for the book but maybe worth a sidebar note. Thanks again.
Ah, that's a really cool trick! I'd have to think that through to see if it works for the observer pattern, but that's a neat idea.
