Implementing clone on a LinkedList

Question

I am trying to implement a clone() method on a DoubleLinkedList. Now, the problem is that implementing it by "the convention" is a lot more troublesome than just creating a new DoubleLinkedList and filling it with all the elements of my current DoubleLinkedList.

Is there any inconvenient I am not seeing when doing that?

Here is my current approach:

@Override
public DoubleLinkedList<T> clone() {
    DoubleLinkedList<T> dll = new DoubleLinkedList<T>();

    for (T element : dll) {
        dll.add(element);
    }

    return dll;
}

Here is what it would be by the convention:

@Override
public DoubleLinkedList<T> clone() {
    try {
        DoubleLinkedList<T> dll = (DoubleLinkedList<T>)super.clone();
        //kinda complex code to copy elements
        return dll;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e.toString());
    }
}

Answer 1

If you do it by creating a new list and adding all the elements from the source, if you then do something like:

DoubleLinkedList<Foo> l1 = new DoubleLinkedList<Foo>();
l1.add (new Foo(params));
DoubleLinkedList<Foo> l2 = l1.clone();
Foo foo = l2.get(0);
foo.setProperty("new Value");

foo.property will be "new value" in both lists (the same the other way around; if you change it in l1, changes will appear in l2). The correct way would be to actually clone every element and the add the clone to ensure the lists are independent. Take note that this only happens if you change properties of the elements, not if you add, move, delete them from the list.

Edit: just realized that since it's a linked list, the next/previous elements are properties of the element, so even adding, deleting, will affect both list.

Answer 2

As you correctly point out, the convention is to always call super.clone() in the beginning of an implementation of clone(). From the API docs on Object#clone():

By convention, the returned object should be obtained by calling super.clone. If a class and all of its superclasses (except Object) obey this convention, it will be the case that x.clone().getClass() == x.getClass().

Your first attempt (without using super.clone()) has the following problem:

Suppose I have

class IntDoubleLinkedList extends DoubleLinkedList<Integer> implements Cloneable

(and that IntDoubleLinkedList does not bother to override clone()) and I run the following code:

IntDoubleLinkedList idll = new IntDoubleLinkedList();
IntDoubleLinkedList idll2 = (IntDoubleLinkedList) idll.clone();

What will happen? The clone method of your DoubleLinkedList will be executed, which, if it doesn't go through super.clone(), returns an instance of DoubleLinkedList which in turn can not be casted to an IntDoubleLinkedList. A ClassCastException will be thrown!

So how does super.clone() solve this issue? Well, if everybody stick to the convention of calling super.clone() in an overriden clone method, Object.clone() will eventually be called, and this implementation will create an instance of a proper type (IntDoubleLinkedList in this case)!

Answer 3

The reason the "convention" is to call super.clone() is to ensure the ultimate type of the cloned object matches the object that is being cloned. For example if you instantiate your own new DoubleLinkedList in the clone() method, well that's nice for now, but later if a subclass fails to override clone() it will end up returning a clone that is a DoubleLinkedList instead of its own class. (It'll also fail to clone its additional fields, if any, probably! so there are larger issues.)

In that sense, the conventional method is preferred, and it is indeed clunky.

Both implementations, however, have a similar problem: you're not deep-copying the data structures. The clone is only a shallow cop. This is probably not what the caller expects. You would need to go through and replace each value in the DoubleLinkedList with a clone of the value, and likewise for other non-primitive fields.

In that sense, the conventional method is going to give the wrong result here! You need a third way. Your first method probably just about works, except that you need to add element.clone() for example.

Answer 4

As others have explained, if you're going to override clone you should obey its contract.

If you like the way you currently have it, just make DoubleLinkedList not Cloneable and turn your implementation into a copy constructor or static factory method. A static factory method has the added benefit of providing a bit of type inferencing for generic type arguments, too.

P.S. LinkedList is a doubly-linked list.