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

我在 main 方法中做错了什么？

如何在 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 类:

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.

为了实现它，我添加了用于链接/取消链接的 setter 。看评论:

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();

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