Deep Copy Constructor for Linked List in Java

Question

I have a HW assignment and only one small part of it is to make a copy constructor which makes a Deep Copy of the linked list which you have entered in its parameters.

I understand that this means, that the List you have entered remains unchanged, and that the new linked list is isolated from the "old" one. My code gives me a new list which is exactly the same as the old one (the one you enter as a parameter) and this is what I want, but the old one is changed.

Here is the constructor:

public SortedLinkedSet(SortedLinkedSet<T> copy) {
    if (copy == null) {
        this.firstNode = null;
    } else{
        SortedLinkedSetNode firstNode1 = new SortedLinkedSetNode(copy.getFirstNode().value);
        this.firstNode = firstNode1;
       // so basically I am chaining elements from "copy" to firstNode1 and then making "this" = to firstNode1. 
        while (copy.firstNode.next !=null) {  
            firstNode1.add(copy.getFirstNode().next.value);
            this.firstNode = firstNode1;
            copy.firstNode = copy.firstNode.next;
       // at the end of this loop I have a successful new linkedList with the same value, but "copy" has been changed
        }
    }      
}

If for example I enter a linked list which has the values (1,2,3) -- with this constructor i get back a new linked list with values 1,2,3 but the old one just has 1.. If someone can help me with why this is going wrong it would be great. Thanks

UPDATE : As Ireeder pointed out, and with a test I did, I am almost sure that the problem is in the statement : copy.firstNode = copy.firstNode.next; i deleted the current code, and did the following test:

SortedLinkedSetNode firstNode = new SortedLinkedSetNode(copy.getFirstNode().value);
this.firstNode=firstNode;

firstNode.add(copy.getFirstNode().next.value);
this.firstNode = firstNode;

firstNode.add(copy.getFirstNode().next.next.value);
this.firstNode = firstNode;

and this Works perfectly(but I knew in advance i'm testing with only 3 element list).How would i do it with a while loop without using such a statement as : copy.firstNode = copy.firstNode.next; I have to somehow move along the "copy" list ?

Answer 1

First the original to copy from, is called copy, like in do copy this one?

You did have some mix-up with the correct nodes and the code was not kept simple enough.

A recursive solution to simplify things seems appropriate:

public SortedLinkedSet(SortedLinkedSet<T> original) {
    Objects.requireNotNull(original);
    this.firstNode = copyNodes(orignal.firstNode);
}

private SortedLinkedSetNode copy(SortedLinkedSetNode originalNode) {
    if (originalNode == null) {
        return null;
    }
    SortedLinkedSetNode node = new SortedLinkedSetNode(originalNode.value);
    node.next = copy(originalNode.next);
    return node;
}

If the node's value would need deep copying too, that could be done at one place.

A loop would still be simple. One way:

private SortedLinkedSetNode copy(SortedLinkedSetNode originalNode) {
    SortedLinkedSetNode firstNode = null;
    SortedLinkedSetNode previousNode = null;
    while (originalNode != null) {
        SortedLinkedSetNode node = new SortedLinkedSetNode(originalNode.value);
        if (firstNode == null) {
            firstNode = node;
        } else {
            previousNode.next = node;
        }
        previousNode = node;
        originalNode = originalNode.next;
    }
    return firstNode;
}

Answer 2

It's hard to say what the problem is without seeing the source for SortedLinkedSetNode, but you seem to be modifying your original with this statement:

copy.firstNode= copy.firstNode.next;

This probably advances firstNode to the end of your original linkedset, resulting in the original having one element. Also, confusingly the original is called "copy". You may want to rename it so you can understand your code better.

When creating a deep copy, you shouldn't modify the structure you want to copy.

In this case, you can just use a temporary variable to store the reference to the current node you are on, without modifying your original data structure. Try this:

this.firstNode = firstNode1;
// so basically I am chaining elements from "copy" to firstNode1 and then making "this" = to firstNode1. 

SortedLinkedSetNode currentNode = copy.firstNode;

while (currentNode.next !=null) {  
    firstNode1.add(currentNode.next.value);
    this.firstNode = firstNode1;
    currentNode = currentNode.next;
 }