Java: 如何实现 Dancing Links 算法（使用 DoublyLinkedLists）？

Question

我正在尝试在 Java 中实现 Knuth 的 Dancing Links 算法。

根据 Knuth 的说法，如果 x 是一个节点，我可以在 C:

中通过以下操作完全取消链接一个节点

L[R[x]]<-L[x]
R[L[x]]<-R[x]

并通过以下方式恢复取消链接：

L[R[x]]<-x
R[L[x]]<-x

我的主要方法做错了什么？

如何在 Java 中实现取消链接和恢复？

这是我的主要方法：

      ///////////////

      DoublyLinkedList newList = new DoublyLinkedList();

      for (int i = 0; i < 81; i++) {
        HashSet<Integer> set = new HashSet<Integer>();
        set.add(i);
        newList.addFirst(set);
      }

      newList.displayList();

      // start at 69
      newList.getAt(12).displayNode();

      //HOW TO IMPLEMENT UNLINK?
      //newList.getAt(12).previous() = newList.getAt(12).next().previous().previous();
      //newList.getAt(12).next() = newList.getAt(12).previous().next().next();

      newList.displayList();

      //HOW TO IMPLEMENT REVERT UNLINK?
      //newList.getAt(12) = newList.getAt(12).next().previous();
      //newList.getAt(12) = newList.getAt(12).previous().next();

      System.out.println();

      ///////////////

这是 DoublyLinkedList class:

public class DoublyLinkedList<T> {

  public Node<T> first = null;
  public Node<T> last = null;

  static class Node<T> {
    private T data;
    private Node<T> next;
    private Node<T> prev;

    public Node(T data) {
      this.data = data;
    }

    public Node<T> get() {
      return this;
    }

    public Node<T> set(Node<T> node) {
      return node;
    }

    public Node<T> next() {
      return next;
    }

    public Node<T> previous() {
      return prev;
    }

    public void displayNode() {
      System.out.print(data + " ");
    }

    @Override
    public String toString() {
      return data.toString();
    }
  }

  public void addFirst(T data) {
    Node<T> newNode = new Node<T>(data);

    if (isEmpty()) {
      newNode.next = null;
      newNode.prev = null;
      first = newNode;
      last = newNode;

    } else {
      first.prev = newNode;
      newNode.next = first;
      newNode.prev = null;
      first = newNode;
    }
  }

  public Node<T> getAt(int index) {
    Node<T> current = first;
    int i = 1;
    while (i < index) {
      current = current.next;
      i++;
    }
    return current;
  }

  public boolean isEmpty() {
    return (first == null);
  }

  public void displayList() {
    Node<T> current = first;
    while (current != null) {
      current.displayNode();
      current = current.next;
    }
    System.out.println();
  }

  public void removeFirst() {
    if (!isEmpty()) {
      Node<T> temp = first;

      if (first.next == null) {
        first = null;
        last = null;
      } else {
        first = first.next;
        first.prev = null;
      }
      System.out.println(temp.toString() + " is popped from the list");
    }
  }

  public void removeLast() {
    Node<T> temp = last;

    if (!isEmpty()) {

      if (first.next == null) {
        first = null;
        last = null;
      } else {
        last = last.prev;
        last.next = null;
      }
    }
    System.out.println(temp.toString() + " is popped from the list");
  }
}

Answer 1

我不熟悉 Knuth 的 Dancing Links 算法，但发现 this article 这让它变得很清楚。特别是我发现这非常有帮助：

Knuth takes advantage of a basic principle of doubly-linked lists. When removing an object from a list, only two operations are needed:

x.getRight().setLeft( x.getLeft() )
x.getLeft().setRight(> x.getRight() )

However, when putting the object back in the list, all is needed is to do the reverse of the operation.

x.getRight().setLeft( x )
x.getLeft().setRight( x )

All that is needed to put the object back is the object itself, because the object still points to elements within the list. Unless x’s pointers are changed, this operation is very simple.

为了实现它，我添加了用于链接/取消链接的设置器。看评论：

import java.util.HashSet;

public class DoublyLinkedList<T> {

      public Node<T> first = null;
      public Node<T> last = null;

      static class Node<T> {
        private T data;
        private Node<T> next;
        private Node<T> prev;

        public Node(T data) {
          this.data = data;
        }

        public Node<T> get() {
          return this;
        }

        public Node<T> set(Node<T> node) {
          return node;
        }

        public Node<T> next() {
          return next;
        }

        //add a setter
        public  void setNext(Node<T> node) {
              next = node;
        }
        public Node<T> previous() {
          return prev;
        }

        //add a setter
        public  void setPrevious(Node<T> node) {
              prev = node;
        }

        public void displayNode() {
          System.out.print(data + " ");
        }

        @Override
        public String toString() {
          return data.toString();
        }
      }

      public void addFirst(T data) {
        Node<T> newNode = new Node<T>(data);

        if (isEmpty()) {
          newNode.next = null;
          newNode.prev = null;
          first = newNode;
          last = newNode;

        } else {
          first.prev = newNode;
          newNode.next = first;
          newNode.prev = null;
          first = newNode;
        }
      }

      public Node<T> getAt(int index) {
        Node<T> current = first;
        int i = 1;
        while (i < index) {
          current = current.next;
          i++;
        }
        return current;
      }

      public boolean isEmpty() {
        return (first == null);
      }

      public void displayList() {
        Node<T> current = first;
        while (current != null) {
          current.displayNode();
          current = current.next;
        }
        System.out.println();
      }

      public void removeFirst() {
        if (!isEmpty()) {
          Node<T> temp = first;

          if (first.next == null) {
            first = null;
            last = null;
          } else {
            first = first.next;
            first.prev = null;
          }
          System.out.println(temp.toString() + " is popped from the list");
        }
      }

      public void removeLast() {
        Node<T> temp = last;

        if (!isEmpty()) {

          if (first.next == null) {
            first = null;
            last = null;
          } else {
            last = last.prev;
            last.next = null;
          }
        }
        System.out.println(temp.toString() + " is popped from the list");
      }

      public static void main(String[] args) {

          ///////////////

          DoublyLinkedList newList = new DoublyLinkedList();

          for (int i = 0; i < 81; i++) {

              HashSet<Integer> set = new HashSet<Integer>();
              set.add(i);
              newList.addFirst(set);
          }

          newList.displayList();

          // start at 69
          Node node = newList.getAt(12);
          node.displayNode(); System.out.println();

          //HOW TO IMPLEMENT UNLINK?
          node.previous().setNext(node.next);
          node.next().setPrevious(node.previous());

          //The 2 statements above are equivalent to
          //Node p = node.previous();
          //Node n = node.next();
          //p.setNext(n);
          //n.setPrevious(p);

          newList.displayList();

          //HOW TO IMPLEMENT REVERT UNLINK?
          node.previous().setNext(node);
          node.next().setPrevious(node);

          newList.displayList(); System.out.println();

          ///////////////
      }
    }

Java: 如何实现 Dancing Links 算法（使用 DoublyLinkedLists）？

Java: How to implement Dancing Links algorithm (with DoublyLinkedLists)?

java

linked-list

nodes

doubly-linked-list

knuth