Author: Mohammad J Iqbal

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

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.

Deep Copy

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:

Output shallow copy

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:

Output deep copy

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.

Follow Mohammad J Iqbal on LinkedIn