如何为 LinkedList 的浅/深副本做 Junit

Question

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

1.深拷贝法

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 :)
}

类列表节点

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 指向指向节点 0，该节点指向节点 1： 头 = 节点 0 => 节点 1

在深层副本中，创建两个新节点 7 和 8： 深度复制 = 节点 7 => 节点 6

在浅拷贝中，创建一个新节点 7 并将引用复制到原始节点： 浅拷贝 = 节点 7 => 节点 1

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;

}

如果更改了原始节点 1，则会影响原始副本和浅拷贝，不会影响深拷贝。

现在是术语。上面描述的是如何深度复制或浅拷贝节点。浅拷贝链表是没有意义的，因为你实际上只是浅层地复制单个节点。当然，您可以深层复制列表。

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

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

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

ListNode 等于 (( 和 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();
}