Making your Data Structure/Object Cloneable
Author: Mohammad J Iqbal
When we need cloning or copying object?
Mobile phone apps those deal with Maps and social networking might need clones of Graph objects. Social Networking server side applications might also need cloning Graph of Friend’s network or cloning Trees. If you want do parallel processing in multithreaded environment you might need a make a deep copy of your object and pass it to other object for parallel processing. Why I mentioned deep copy? You might not want states of your original object to be changed which can have negative impact. If you pass a shallow copy of object, making change on the cloned copy can alter your original object.
#Object Cloning: Object copying is the act of creating and initializing a new object based on an existing object’s state.
#Shallow copy involves creating a new, uninitialized object, B, and copying each field value from the original, Due to this procedure, this is also known as a field-by-field copy, field-for-field copy, or field copy. If the field value is a primitive type (such as int), the value is copied such that changes to the value in B do not affect the value in A. If the field value is a reference to an object (e.g., a memory address) the reference is copied, hence referring to the same object that A does. Changing the state of the inner object affects the emergent state of both A and B since the objects are shared. In a language without primitive types (where everything is an object), all fields of the copy reference the same objects as the fields of the original.
Shallow Copy code Example:
You can make a call to object’s super.clone() method to make a shallow copy of object.
// shallow copy
public Object clone() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return clone;
}
#Deep copy involves copying the state of all subordinate objects – recursively dereferencing object references at each level of the tree that is the state of the original object and creating new objects and copying fields. A modification of either the original or copied object, including their inner objects, does not affect the other since they share none of the content.
Note: Definitions of ‘Object Cloning’, ‘Shallow Copy’ ,’Deep Copy’ and the images are copied from en.wikipedia.org
Deep Copy code example:
In the below code, we first create an object of LinkedList class by calling super.clone();
Initialize the elements of Node with initial state or “virgin” state.
For deep copy since we won’t be using references to old objects, we need to create new objects and keep a track of old object -> new object, We are using a HashMap (For O(1) lookup) to store the mapping.
For all nodes in he list we are creating new node with the item and adding to HashMap.
Next, For all nodes we are updating prev and next by getting the corresponding new node from HashMap
#Time Complexity of cloning: O(n)
#Space Complexity of cloning O(n)
// deep copy
public Object clone() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
// Initialize clone with our elements (make a deep copy)
// Using a HashMap to keep track of old node and new node
Map<Node<E>, Node<E>> nodeMap = new HashMap<Node<E>, Node<E>>();
//For all nodes int he list create new node with the item and add to HashMap
Node<E> currentNode = first;
while (currentNode != null) {
Node<E> newNode = new Node<>(null, cloneItem(currentNode.item), null);
nodeMap.put(currentNode, newNode);
currentNode = currentNode.next;
}
//For all nodes update prev and next by getting the corresponding new node from HashMap
currentNode = first;
while (currentNode != null) {
Node<E> newNode = nodeMap.get(currentNode);
newNode.prev = nodeMap.get(currentNode.prev);
newNode.next = nodeMap.get(currentNode.next);
clone.addLast(newNode);
currentNode = currentNode.next;
}
return clone;
}
The CloneableLinkedList class implements java.lang.Cloneable interface which is a ‘Marker Interface’ that indicates the object should have clone() method inside and will be eligible to clone.
Finally our implementation class will look like below:
package com.spsoft.list;
import java.util.*;
public class CloneableLinkedList<E> extends SerializableLinkedList<E> implements Cloneable {
// shallow copy
public Object cloneShallow() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return clone;
}
// deep copy
public Object clone() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
// Initialize clone with our elements (make a deep copy)
// Using a HashMap to keep track of old node and new node
Map<Node<E>, Node<E>> nodeMap = new HashMap<Node<E>, Node<E>>();
//For all nodes int he list create new node with the item and add to HashMap
Node<E> currentNode = first;
while (currentNode != null) {
Node<E> newNode = new Node<>(null, cloneItem(currentNode.item), null);
nodeMap.put(currentNode, newNode);
currentNode = currentNode.next;
}
//For all nodes update prev and next by getting the corresponding new node from HashMap
currentNode = first;
while (currentNode != null) {
Node<E> newNode = nodeMap.get(currentNode);
newNode.prev = nodeMap.get(currentNode.prev);
newNode.next = nodeMap.get(currentNode.next);
clone.addLast(newNode);
currentNode = currentNode.next;
}
return clone;
}
private E cloneItem(E e){
//to be implemented
return e;
}
}
Let’s test shallow copy cloneShallow() method using below code:
package com.spsoft.list;
public class CloneableLinkedListTest {
public static void main(String args[]) {
// Creating an empty LinkedList
CloneableLinkedList<String> list = new CloneableLinkedList<>();
// Use add() method to add elements in the list
list.addLast("First");
list.addLast("Second");
list.addLast("Third");
// Displaying the list
System.out.println("Original List elements:");
for(Object s : list){
System.out.print((String)s+" ");
}
System.out.println();
// Creating another linked list and copying
CloneableLinkedList<String> clonedList = new CloneableLinkedList<>();
clonedList = (CloneableLinkedList<String>) list.cloneShallow();
// Displaying the cloned linked list
System.out.println("Cloned List:");
for(Object s : clonedList){
System.out.print((String)s+" ");
}
System.out.println();
System.out.println("Changing First Node in Original LinkedList to: 'Changed'");
Node<String> firstNode = list.first;
firstNode.item = "Changed";
System.out.println("Original LinkedList elements after first node modified :");
for(Object s : list){
System.out.print((String)s+" ");
}
System.out.println();
System.out.println("Cloned LinkedList elements:");
for(Object s : clonedList){
System.out.print((String)s+" ");
}
}
}
When we run the code, we get below output:
Looking at the above output we can see, changing node item of cloned list, modified the original list. (Expected for Shallow Clone)
To test deep clone, we will change below line in the above test class:
clonedList = (CloneableLinkedList<String>) list.clone();
For deep copy we get the below output:
From the output above, we can see changing original list did not impact the cloned list. This is true if we do opposite, changing cloned list will not impact original list for deep copy.