Deep Cloning of Custom Linked List

Question

I am trying to implement clone method for deep clonning of custom linked list(of Rectangle objects). I am able to get the correct value when there is no element or only a single element in the list but not when there are more than one element in the list. I think the problem is with my clone method in MyLinkNode Class. Can someone please help with me this?

Note: I have shortened my code for readability purposes

class Rectangle implements Cloneable {
    private double width;
    private double height;
    // setters and getters for these class variables

    public Object clone() {
        try {
            Object rectClone = super.clone();
            return (Rectangle) rectClone;
        } catch (CloneNotSupportedException c) {
            return null;
        }
    }
}


public class MyList implements Cloneable {
    private MyListNode head;

    public Object clone() {
        try {
            Object listClone = super.clone();
            if (head != null) {
                ((MyList) listClone).head = (MyListNode) head.clone();
            }
            return (MyList) listClone;
        } catch (CloneNotSupportedException c) {
            return null;
        }
    }
}


class MyListNode implements Cloneable {
    private Rectangle rectangle;
    private MyListNode next;
    // getter setter for class properties

    protected MyListNode clone() {
        try {
            Object NodeClone = super.clone();
            ((MyListNode) NodeClone).rectangle = (Rectangle) rectangle.clone();
            MyListNode temp = this.next;
            while (temp != null) {
                ((MyListNode) NodeClone).rectangle = (Rectangle) rectangle
                        .clone();
                temp = temp.getNext();
                //edited later, posted by mistake
                //clone();
            }
            return (MyListNode) NodeClone;
        } catch (CloneNotSupportedException c) {
            return null;
        }
    }
}

---My clone method using recursion(another try)--

protected MyListNode clone() {
    try {
        Object nodeClone = super.clone();
        MyListNode temp = this.next;

        if( temp == null){
        ((MyListNode) nodeClone).rectangle = (Rectangle)this.rectangle.clone();
        ((MyListNode) nodeClone).next = this.next.clone();
        temp = temp.getNext();
        }
        else{
            clone();
        }

        return  (MyListNode)nodeClone;      


    }catch (CloneNotSupportedException c) {
        return null;
    }


}

--this one seems to be working twice for the whole thing, although the result seems to be right(correction of previous method)--

protected MyListNode clone() {
    try {
        Object listNodeCopy = super.clone();
        MyListNode temp = this.next;

        if (temp == null) {
            ((MyListNode) nodeClone).rectangle = (Rectangle) this.rectangle.clone();
        } else {
            while (temp != null) {
                ((MyListNode) nodeClone).rectangle = (Rectangle) this.rectangle.clone();
                ((MyListNode) nodeClone).next = temp.clone();
                temp = temp.getNext();
            }
        }
    return (MyListNode) listNodeCopy;
    } catch (CloneNotSupportedException c) {
        return null;
    }
}

Any help with this is greatly appreciated! I am new to both cloning and custom linked list and have been trying to do this for a long time now :(

Answer 1

Your iterative approach is wrong. You have to clone every node so you have to do it in the list class. If you try to clone it on the first node when you try to clone the rest they will clone recursively the rest of the nodes. So first node will be cloned once, second twice, third three times, etc.

I'll try to fix your recursive approach.

    if( temp == null){ // <-- temp is null!! should be != null
        ((MyListNode) nodeClone).rectangle = (Employee)this.rectangle.clone(); <-- Employee ?!?!
        ((MyListNode) nodeClone).next = this.next.clone();
        temp = temp.getNext(); <-- This throws NPE as temp is null!! But it is useless anyway. Remove this line.
    }

This does work:

protected MyListNode clone() {
    try {
        Object nodeClone = super.clone();
        ((MyListNode) nodeClone).rectangle = (Rectangle) this.rectangle.clone();
        if (this.next != null) {
            ((MyListNode) nodeClone).next = this.next.clone();
        }
        return (MyListNode) nodeClone;
    } catch (CloneNotSupportedException c) {
        throw new RuntimeException(c); // <<- This is the best for impossible conditions so if they happen you notice
    }
}