In example below, in "main" when after cloning LinkedList l1 to l2, when I add element to l2, I do not get 300 in l1.
However, in the the method "addTwoLists" when I use custom implementation, adding any element to "rohit" adds it to "first" as well.
package hackerrank;
import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;
class Node1 implements Cloneable{
int data;
Node1 next;
Node1(int x){
this.data=x;
this.next=null;
}
Node1 (){
}
protected Node1 clone() throws CloneNotSupportedException {
return (Node1) super.clone();
}
}
public class MS_linkedlist_copy {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<AtomicInteger> l1 = new LinkedList<>();
l1.add(new AtomicInteger(100));
l1.add(new AtomicInteger(200));
LinkedList<AtomicInteger> l2 = (LinkedList) l1.clone();
l2.add(new AtomicInteger(300));
System.out.println(l1);
System.out.println(l2);
// change element on first list
l1.get(0).incrementAndGet();
System.out.println();
System.out.println("After change internal state of first element");
System.out.println(l1);
System.out.println(l2);
Node1 first = new Node1(1);
Node1 second = new Node1(2);
first.next= second;
Node1 third = new Node1(3);
Node1 fourth = new Node1(4);
third.next=fourth;
addTwoLists(first, third);
}
static Node1 reverse(Node1 head){
Node1 prev =null;
while(head!=null){
Node1 next_node = head.next;
head.next = prev;
prev=head;
head=next_node;
}
return prev;
}
//
static Node1 addTwoLists(Node1 first, Node1 second){
System.out.println(first.data);
Node1 rohit = null;
try {
rohit = (Node1)first.clone();
} catch (CloneNotSupportedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
rohit.data=1000;
rohit.next.data=1000;
System.out.println(first.data);
System.out.println(rohit.data);
Node1 rohit2= rohit;
while(rohit.next!=null) {
rohit= rohit.next;
}
Node1 rohit_add = new Node1(2000);
rohit.next = rohit_add;
System.out.println(first.data);
System.out.println(rohit2.data);
// rohit = first;
// rohit= reverse(rohit);
// reverse(second);
// System.out.println(first.data);
// System.out.println(rohit.data);
return null;
}
}
I tried to add elements to a shallow copy in custom, which got added to main list successfully. However, after trying to add elements to shallow copy of built-in LinkedList, the elements are not added to original list. I am trying to understand what is going on in the built-in LinkedList.
The difference is that LinkedList.clone also copies all the nodes in the entire linked list, whereas your Node1.clone only copies that one node, and not any of the nodes linked to it.
You can find an implementation of LinkedList.clone here,
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
Notice that it calls add on the cloned list (called clone here) in the loop. Each call to add creates a new linked list node.
Note that this is still a shallow copy, in the sense that the data in the nodes are not cloned. For example, if the lists stores String objects, no new strings are created.
So after cloning, you actually get two "chains" with the builtin LinkedList:
O-O-O
O-O-O
whereas with your Node1, since only one node is cloned, you get something like this:
first -> O
\
-O-O
/
rohit2 -> O
The two "heads" of the lists share the same "end", so adding an element to the end of the list adds it to both lists.
You can rewrite your clone so that it copies all the nodes. One simple way is to do it recursively:
protected Node1 clone() throws CloneNotSupportedException {
Node1 newNode = new Node1(this.data);
if (next != null) {
newNode.next = next.clone();
}
return newNode;
}