java - DoubleLinkedList 的 equals 方法

Question

我得到了这个任务来为双向链表创建一个 equals 方法。到目前为止，我得到了下面发布的代码。它通过了一些测试，但不是全部。失败的预期值确实与实际值相同，但我仍然收到一些断言错误。

我已经搞乱并试图改变事情很长一段时间了，但我似乎无法自己解决。我在互联网上也找不到任何好的例子。我尝试过使用 Eclipse 生成 equals 方法，但这也没有通过所有测试。

我知道您不会在这里给出免费答案，但是有人可以指出代码中的错误吗？

    /**
     * This method should return true iff the values of this list 
     * and that are identical and in the same order.
     * @param that list to compare this to.
     * @return true iff the values are identical and in the same order
     */
    public boolean equals(Object that) {
      if (that == null)
        return false;
      if (!(that instanceof DoublyLinkedList) )
    return false;

  DoublyLinkedList<E> other = (DoublyLinkedList<E>) that;
  if (header == null&&other.header != null)
            return false;
        if (trailer == null&&other.trailer != null)
            return false;           

  while (header.getNext() != trailer){
      if (!(header.equals(other.header))){
              return false;
      }
              header = header.getNext();
              other.header = other.header.getNext();
     }
        return true;
    }

根据请求编辑 DLL 类中失败的测试:

public static class DoublyLinkedList<E> {
    private Node<E> header;
    private Node<E> trailer;

    /** 
     * Constructor that creates an empty DLL
     */
    public DoublyLinkedList() {
        this.header = new Node<>(null, null, null);
        this.trailer = new Node<>(null, header, null);
        this.header.setNext(trailer);
    }

    /**
     * @return if the list is empty.
     */
    public boolean isEmpty() {
      return this.header.getNext() == this.trailer;
    }

    /**
     * @return the first element of the list.
     */
    public E getFirst() {
      if (isEmpty()) return null;
        return this.header.getNext().getElement();
    }

    /**
     * @return the last element of the list.
     */
    public E getLast() {
      if (isEmpty()) return null;
        return this.trailer.getPrevious().getElement();
    }


    /**
     * Adds a new Node to the beginning of the list, 
     * containing the specified value.
     * @param value for the new first node to hold.
     */
    public void addFirst(E element) {
        Node<E> newNode = new Node<>(element, header, header.getNext());
        header.getNext().setPrevious(newNode);
        header.setNext(newNode);
    }

    /**
     * This method should return true iff the values of this list 
     * and that are identical and in the same order.
     * @param that list to compare this to.
     * @return true iff the values are identical and in the same order
     */
    public boolean equals(Object that) {
      if (that == null)
        return false;
      if (!(that instanceof DoublyLinkedList) )
    return false;

  DoublyLinkedList<E> other = (DoublyLinkedList<E>) that;
  if (header == null&&other.header != null)
            return false;
        if (trailer == null&&other.trailer != null)
            return false;           

  while (header.getNext() != trailer){
      if (!(header.equals(other.header))){
              return false;
      }
              header = header.getNext();
              other.header = other.header.getNext();
     }
        return true;
    }


    /**
     * Simple toString for testing purposes. Please note that solutions that use the
     * .toString() to implement the .equals() method will be rejected.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("DoublyLinkedList<");

        Node<E> finger = header.getNext();
        while (finger != trailer) {
            sb.append(finger.toString());
            if (finger.getNext() != trailer) {
                sb.append("-");
            }
            finger = finger.getNext();
        }

        sb.append(">");
        return sb.toString();
    }
}

以及测试:

@Test
    public void testEqualsCopy() {
        Solution.DoublyLinkedList<Integer> dll1 = createDLL(2);
        Solution.DoublyLinkedList<Integer> dll2 = createDLL(2);
        assertEquals(dll1, dll2);
    }
        @Test
    // Both lists contain only the entry 42.
    public void testTwoEqualLists() {
        Solution.DoublyLinkedList<Integer> dll1 = new Solution.DoublyLinkedList<>();
        Solution.DoublyLinkedList<Integer> dll2 = new Solution.DoublyLinkedList<>();
        dll1.addFirst(42);
        dll2.addFirst(42);
        assertEquals(dll1, dll2);
    }

和错误:

testEqualsCopy(UTest) failed: 'java.lang.AssertionError: expected: Solution$DoublyLinkedList<DoublyLinkedList<1-0>> but was: Solution$DoublyLinkedList<DoublyLinkedList<1-0>>'
testTwoEqualLists(UTest) failed: 'java.lang.AssertionError: expected: Solution$DoublyLinkedList<DoublyLinkedList<42>> but was: Solution$DoublyLinkedList<DoublyLinkedList<42>>'

Answer 1

由于我认为双向链表的外观与您所拥有的之间存在很大差距，因此我想添加我的示例实现。它消除了虚拟的 header 和 trailer 节点，恕我直言，根本不需要这些节点。

public class DoublyLinkedList<E> {

    private Node<E> header;
    private Node<E> trailer;

    /**
     * @return if the list is empty.
     */
    public boolean isEmpty() {
      return header == null;
    }

    /**
     * @return the first element of the list.
     */
    public E getFirst() {
        return header != null ? header.getElement() : null;
    }

    /**
     * @return the last element of the list.
     */
    public E getLast() {
        return trailer != null ? trailer.getElement() : null;
    }

    /**
     * Adds a new Node to the beginning of the list, 
     * containing the specified value.
     * @param value for the new first node to hold.
     */
    public void addFirst(E element) {
        Node<E> newNode = new Node<E>(element, null, header);
        header = newNode;
        if (trailer == null) {
            trailer = newNode;
        }
    }

    /**
     * This method should return true if the values of this list and that are
     * identical and in the same order.
     * 
     * @param that
     *            list to compare this to.
     * @return true if the values are identical and in the same order
     */
    @SuppressWarnings("unchecked")
    public boolean equals(Object that) {
        if (!(that instanceof DoublyLinkedList))
            return false;

        DoublyLinkedList<E> other = (DoublyLinkedList<E>) that;

        // if lists are empty 
        if (header == null) {
            return other.header == null ? true : false;
        }

        if (!header.equals(other.header))
            return false;

        // Just one element
        if (header == trailer) {
            return true;
        }

        if (!trailer.equals(other.trailer))
            return false;

        Node<E> thisNode = header;
        Node<E> otherNode = other.header;

        while (thisNode.getNext() != trailer) {
            thisNode = thisNode.getNext();
            otherNode = otherNode.getNext();
            if (!(thisNode.equals(otherNode))) {
                return false;
            }
        }
        return true;
    }


    /**
     * Simple toString for testing purposes. Please note that solutions that use the
     * .toString() to implement the .equals() method will be rejected.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("DoublyLinkedList<");

        Node<E> finger = header;
        while (finger != null) {
            sb.append(finger.toString());
            if (finger.getNext() != null) {
                sb.append("-");
            }
            finger = finger.getNext();
        }

        sb.append(">");
        return sb.toString();
    }
}

这是我的 Node 类的样子。这里没有太多变化。

public class Node<E> {

    private E element;
    private Node<E> previous;
    private Node<E> next;

    public Node<E> getPrevious() {
        return previous;
    }

    public Node<E> getNext() {
        return next;
    }

    public E getElement() {
        return element;
    }

    public Node(E element, Node<E> previous, Node<E> next) {
        this.element = element;
        this.previous = previous;
        this.next = next;
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object that) {
        if (!(that instanceof Node)) {
            return false;
        }
        Node<E> other = (Node<E>) that;
        if (element == null) {
            return other.element == null ? true : false;
        }
        return element.equals(other.element);
    }

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

这是我用来测试我的实现的代码。

DoublyLinkedList<Integer> dll1 = new DoublyLinkedList<Integer>();
dll1.addFirst(100);
dll1.addFirst(200);

DoublyLinkedList<Integer> dll2 = new DoublyLinkedList<Integer>();
dll2.addFirst(100);
dll2.addFirst(200);

DoublyLinkedList<Integer> dll3 = new DoublyLinkedList<Integer>();
dll3.addFirst(42);

DoublyLinkedList<String> blankList1 = new DoublyLinkedList<String>();
DoublyLinkedList<String> blankList2 = new DoublyLinkedList<String>();

if (blankList1.equals(blankList2)) {
    System.out.println(blankList1 + " = " + blankList2);
}

if (!dll1.equals(dll3)) {
    System.out.println(dll1 + " != " + dll3);
}

if (dll1.equals(dll2)) {
    System.out.println(dll1 + " = " + dll2);
}

输出:

DoublyLinkedList<> = DoublyLinkedList<>
DoublyLinkedList<200-100> != DoublyLinkedList<42>
DoublyLinkedList<200-100> = DoublyLinkedList<200-100>