Dancing Links

Here is a demonstration of the Dancing Links idea (Wikipedia definition).

The idea is this: if you remove an item from a doubly-linked list, you can put it right back in O(1) as long as you hold on to it. And, if you remove items A B C, you can put them right back as long as you reverse the order exactly, C B A.

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:

One thought on “Dancing Links

  1. Pingback: Exact Cover Problem and Knuth’s Algorithm X | Derek Illchuk - Computations

Leave a Reply