Dance of the Edges
Dance of the Edges is a technique for the effective handling of lists in computer science . It makes it easy to remove or insert elements in lists.
For example, the element B of a list has the predecessor A and the successor C. Each element has a reference to its predecessor and its successor: In the case of B, A can be reached with B. on the left and C with B. on the right. A typical operation to remove B from the list is:
B.links.rechts := B.rechts; B.rechts.links := B.links;
That is, B. on the left, i.e. A, receives the element that was previously the successor of his successor, namely C. Correspondingly, B. receives on the right, i.e. C, as the predecessor A. Starting from A or C, B is no longer closed to reach. B has been removed from the list.
The idea behind the dance of the edges is that after the removal, B still has the information stored to undo the removal:
B.links.rechts := B; B.rechts.links := B;
Especially practical is this principle for backtracking - algorithms that achieve a certain status according to the principle of trial and error, and must make this reversed if it is not the solution of the problem.
This technique was first introduced in 1979 by Hirosi Hitotumatu and Kohei Noshita. It owes its name to Donald Knuth , whom the systematic change of references reminded of a dance. With their help one can solve the problem of the exact overlap with the dancing links algorithm .
literature
- Hirosi Hitotumatu, Kohei Noshita: A technique for implementing backtrack algorithms and its applications . In: Information Processing Letters . tape 8 , no. 4 , 1979, p. 174-175 .
- Donald E. Knuth: Dancing on the left . arxiv : cs / 0011047 (preprint).