Why LinkedList clone method implementation needs to store the copyied list into virgin state?

user_13756311 0
Viewed 47
    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;
    }

This is the source code of LinkedList. The clone already has the elements in the original list, what is the purpose of making it empty and assigning the elements again?

java
2 Answers

The purpose of the clone method is returning a copy of the instance object. They correct meaning of copy is delegated to the implementor class, but main requirement is when object.clone() != x, it returns true.

In the case of the Java LinkedList, it returns a shallow copy of the elements, but not a copy of the elements theirslef. In this case the list.clone() != list, it's still true, but when you check their elements is going to return false (example list.get(0) != list.clone().get(0)).

The purpose of the copied list is to be not linked to the original one, so you could add/insert/delete elements without modify the original list.

Example (pseudo-code):

original.add(1);
original.add(2);
original.size(); // 2

clonedList = original.clone();

clonedList.size(); // 2

clonedList.add(3);
clonedList.size(); //3
originalList.size(); //2
user_108692840

The way that a java.util.LinkedList is implemented, is that it uses Node<E> objects to link elements together. And a LinkedList object has a reference to the first and last Node<E> in the list.

If you scroll around a bit you'll find this declaration:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Visually, a LinkedList with 4 elements can be thought of like this:

enter image description here

When cloning a linked list, what we would expect to happen is that the entire chain of Nodes is copied. Like this:

enter image description here

However, superClone just calls super.clone, which does not make copies of these Node objects. It only copies the LinkedList object. Therefore, it would be incorrect to implement LinkedList.clone by just calling super.clone, because then the cloned list would use the same chain of Nodes as the original:

enter image description here

This would mean that adding something in the middle of the chain would add that thing to both the cloned list, and the original list!

By resetting the cloned list to its initial state, and then re-adding all the elements from the original list, we create a new chain of Node objects for the cloned list. This is because add creates new Node objects:

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
user_51335850
Related