Geek asks and answers

Whip Key Link Algorithm Data Structure

I apologize if my question sounds silly because understanding the data structure is not very good.

I read about the Knuth Dancing Links algorithm and pretty much understand how it works in principle. He mentioned that the visualization of the data structure of the dance link looks like a table with columns and rows, with each cell associated with their higher, lower, left and right cells. I also read that this algorithm uses a cyclically double linked list.

What I want to know is how can I make a double list of links in such a table with columns and rows?

As I know, most double linked lists have only 2 pointers (up and down), does this mean that I have to create my own custom linked list that has 4 pointers (up, down, left and right)? Or are there other ways?

Thanks in advance.

+5
source share
1 answer

The algorithm uses a doubly linked list for each row and column, and not just for one list.

This article on using dance links to solve sudoku has a nice image.

At least in the code of this article, the rows are really represented as pointers left and right, and the columns are pointers up and down at the same nodes, more or less, as you described, so the lists are interconnected.

+4

More articles:


All Articles