The idea is this: if you remove an item from a doubly-linked list, you can put it right back in as long as you hold on to it. And, if you remove items , you can put them right back as long as you reverse the order exactly, .
This is done as follows:
// Remove: `curr` is forgotten by neighbors curr->prev->next = curr->next; curr->next->prev = curr->prev; // Reinsert: 'curr' knows where to go, and steps right back in! curr->next->prev = curr; curr->prev->next = curr; // Works over and over, as long as it's done in stack order: // remove=push, reinsert=pop. dancing_link_remove(A); dancing_link_remove(B); dancing_link_reinsert(B) dancing_link_remove(C); dancing_link_reinsert(C) dancing_link_reinsert(A)
This works well where you’re drilling in to search but need to backtrack too — you can do so without the need to work with multiple copies.
And finally, this is demonstrated in git and as follows: