如何为 LinkedList 的 shallow/deep 副本做 Junit

Question

你好，我做了深拷贝，浅拷贝是由用户 AndyMan 建议的，现在我做了 JUnit，我在进行这些测试时遇到了一些小问题：

1.deep复制方法

   public ListNode<E> deep_clone() {
           first = deep_clone(first);
           ListNode<E> copy = new ListNode<>(first);
     return copy;
    } 

    private static Node deep_clone(Node head) {
        if (head == null) {
            return null;
        }

        Node temp = new Node(head.getData());
        temp.setNext(deep_clone(head.getNext()));

        return temp;
    }

编辑

非常感谢 AndyMan 建议这种浅拷贝方法:

private static Node shallow_clone(Node head) {
   if (head == null)
      return null;

   Node temp = new Node(head.getData());
   temp.setNext(head.getNext());  // Just copy the reference

return temp;
}

但有一个问题是如何 Junit 深拷贝和浅拷贝方法？

我做了以下操作，但 Junit 测试失败了：

@Test
public void test_shallow_clone(){
    ListNode<Integer> list =new ListNode<>();
    for (int i = 0; i < 10; i++)
        list.insert(i);

    ListNode<Integer>cloned =list.shallow_clone();
    //assertSame(cloned,list); //failed i dont know why
    //assertEquals(cloned, list);//Even though its shallow copy i get that they are  not equal!
    assertSame(list.getFirst(), cloned.getFirst());
    assertTrue(cloned.equals(list));
}

以及深拷贝测试：

@Test
public void test_depp_clone(){
    ListNode<Integer> list =new ListNode<>();
    for (int i = 0; i < 10; i++)
        list.insert(i);

    ListNode<Integer>cloned =list.depp_clone();

    assertSame(cloned.getFirst(),list.getFirst());//check for same val..
    //assertEquals(cloned, list);//this make the test fail..
    assertFalse(cloned.equals(list));//okay the are not equal lists this means its deep copy...no implemented equal method :)
}

class 列表节点

public class ListNode<E> implements Iterable<E>{

private Node<E> first;
//private Node<E> last;

public ListNode() {
    first = null;
    //last = null;
}

public ListNode(Node head) {
    this.first = head;
    //this.last = this.first;
}

public ListNode(E data) {
    Node head = new Node(data);
    this.first = head;
    //this.last = this.first;
}

@Override
public Iterator<E> iterator() {
    return new LL_Iterator<>(first);
}

private static class Node<E> {

    private E data;
    private Node next;

    public Node() {
        this.data = null;
        this.next = null;
    }

    public Node(E data) {
        this.data = data;
        next = null;
    }

    public Node(E data, Node next) {
        this.data = data;
        this.next = null;
    }

    public E getData() {
        return data;
    }

    public void setData(E val) {
        this.data = val;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" + "data=" + data + ", next=" + next + '}';
    }

}

private static class LL_Iterator<E> implements Iterator<E> {

    private Node<E> curr;//we have to specify the E here because if we dont we have to cast the curr.getData()

    public LL_Iterator(Node head) {
        curr = head;
    }

    @Override
    public boolean hasNext() {
        return curr != null;
    }

    @Override
    public E next() {
        if (hasNext()) {
            E data = curr.getData();
            curr = curr.getNext();
            return data;
        }
        return null;
    }

}

public E getFirst(){
    if(first==null)
        return null;

    return first.getData();
}

public boolean addFirst (E data) {
    if(data==null)
        return false;

    Node t= new Node (data);
    t.setNext(first);
    first=t;
    return true;
}

public E getLast() {
    if (first==null)
        return null;
    return getLast(first).getData();
}

private static<E> Node<E> getLast(Node<E> head) {
    if (head == null) {
        return null;
    }

    Node temp = head;
    if (temp.getNext() != null) {
        temp = getLast(temp.getNext());
    }

    return temp;
}

//insertion....Wie setLast
public boolean insert(E data) {
    if(data==null)
        return false;

    first = insert(first, data);
    //last = getLast();
    return true;
}

private static <E> Node insert(Node head, E data) {
    if (head == null) {
        return new Node(data);
    } else {
        head.setNext(insert(head.getNext(), data));
    }
    return head;
}

public void printList(){
    LL_Iterator it= new LL_Iterator(first);
    printUsingIterator(it,it.next());

}

private static<E> void printUsingIterator (LL_Iterator it, E data){

    //VERDAMMT MAL RHEINFOLGE DER ANWEISUNGEN MACHT UNTERSCHIED
    System.out.print(data+"->");

    if (!it.hasNext()) {
        System.out.print(it.next()+"\n");//THIS WILL PRINT NULL!!!
        return;
    }
    printUsingIterator(it,it.next());
}

public int size() {
    return size(first);
}

private static int size(Node head) {
    if (head == null) {
        return 0;
    } else {
        return 1 + size(head.getNext());
    }
}

public boolean contains(E data) {
    return contains(first, data);
}

public static <E> boolean contains(Node head, E data) {
    if (head == null || data == null) {
        return false;
    }
    if (head.getData().equals(data)) {
        return true;
    }
    return contains(head.getNext(), data);
}

public int countIf(E t) {
    return countIf(first, t);
}

private static <E> int countIf(Node head, E t) {
    if (head == null ||t ==null) {
        return 0;
    }
    if (head.getData().equals(t)) {
        return 1 + countIf(head.getNext(), t);
    }

    return countIf(head.getNext(), t);
}


//TODO: WHY IM GETTING HERE AN OVERRIDE REQUEST FROM THE COMPILER??
//answer because im overriding the damn clone() of the list class which is shallow clone
public ListNode<E> depp_clone() {
    first = depp_clone(first);
    ListNode<E> copy = new ListNode<>(first);
    return copy;
}

private static Node depp_clone(Node head) {
    if (head == null) {
        return null;
    }

    Node temp = new Node(head.getData());
    temp.setNext(depp_clone(head.getNext()));

    return temp;
}

public ListNode shallow_clone (){
    ListNode<E> cloned=new ListNode<>(shallow_clone(first));
    return cloned;
}
private static Node shallow_clone(Node head) {
    if (head == null)
        return null;

    Node temp = new Node(head.getData());
    temp.setNext(head.getNext());  // Just copy the reference

    return temp;
}

Answer 1

假设 head 指向 node0，node0 指向 node1： head = node0 => node1

在深拷贝中，新建两个节点7和8： deepCopy = node7 => node6

在浅拷贝中，创建一个新的节点7并复制对原始节点的引用： shallowCopy = node7 => node1

private static Node shallow_clone(Node head) {
if (head == null) {
    return null;
}

Node temp = new Node(head.getData());
temp.setNext(head.getNext());  // Just copy the reference

return temp;

}

如果改变了原来的node1，会同时影响到原始和浅拷贝。不会影响深拷贝。

现在介绍术语。上面描述的是如何对节点进行深拷贝或浅拷贝。 浅拷贝一个链表没有意义，因为你实际上只是在浅拷贝一个节点。当然你也可以深拷贝列表。

如果是数组，而不是链表，那么你可以浅拷贝或深拷贝。

要测试这些，请覆盖 equals() 和 hashCode()。如果两个列表具有相同的值，我会认为它们相等。为了使两个节点相等，它们应该具有相同的值，并且列表的其余部分应该相等。如果不覆盖 equals()，则使用 Object 中的实现。对象使用需要相同引用的按位比较。你可能想查一下。

此外，当覆盖 equals() 时，hashCode() 也需要被覆盖。这与问题没有直接关系，因此您可能需要查看它。

ListNode equals() 和 hashCode():

@Override
public boolean equals(Object otherObject) {
    // Objects are equal if they have the same value, and next has the same value
    if (otherObject instanceof ListNode) {
        ListNode other = (ListNode)otherObject;
        return first.equals(other.first);
    }
    else {
        return false;
    }
}
@Override
public int hashCode() {
    return first.hashCode();
}

Node equals() 和 hashCode():

@Override
    public boolean equals(Object otherObject) {
        // Objects are equal if they have the same value, && next has the same value
        if (otherObject instanceof Node) {
            Node other = (Node)otherObject;
            return data.equals(other.data) && ((next == null && ((Node) otherObject).getNext() == null) || next.equals(((Node) otherObject).next));
        }
        else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return data.hashCode();
    }

如何为 LinkedList 的 shallow/deep 副本做 Junit

how to do Junit for shallow/deep copy of LinkedList

java

recursion

implementation

linked-list