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 ?

This may help you to understand the concept: http://stackoverflow.com/questions/6182565/java-deep-copy-shallow-copy-clone — , Mar 02 '14 at 16:02

lreeder · Answer 1 · 2014-03-03T19:09:59.760

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;
 }

You are right, I just did a test where I removed this statement and the while loop, and just added 3 more "adding" statements where i first call copy.getfirstNode.value, and in the next one copy.getFirstNode.next.value, and finally copy.getFirstNode.next.next.value and it WORKS (but i knew im testing with only a 3 element list). When i try doing it in a loop ("while" since i dont know the length) I cant see how NOT to use such a statement. Thanks for pointing it out! — user3371034, Mar 02 '14 at 16:17
Use a temp variable to store a reference to the current node in the list, and update that variable instead of your original. See my updated answer. — lreeder, Mar 03 '14 at 19:10

score 0 · Answer 2 · answered Feb 07 '22 at 16:22

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;
}

Deep Copy Constructor for Linked List in Java

2 Answers2