How to deep copy a list?

After E0_copy = list(E0), I guess E0_copy is a deep copy of E0 since id(E0) is not equal to id(E0_copy). Then I modify E0_copy in the loop, but why is E0 not the same after?

E0 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for k in range(3):
    E0_copy = list(E0)
    E0_copy[k][k] = 0
    #print(E0_copy)
print E0  # -> [[0, 2, 3], [4, 0, 6], [7, 8, 0]]

E0_copy is not a deep copy. You don't make a deep copy using list(). (Both list(...) and testList[:] are shallow copies.)

You use copy.deepcopy(...) for deep copying a list.

deepcopy(x, memo=None, _nil=[])
    Deep copy operation on arbitrary Python objects.

See the following snippet -

>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = list(a)
>>> a
[[1, 2, 3], [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
>>> a[0][1] = 10
>>> a
[[1, 10, 3], [4, 5, 6]]
>>> b   # b changes too -> Not a deepcopy.
[[1, 10, 3], [4, 5, 6]]

Now see the deepcopy operation

>>> import copy
>>> b = copy.deepcopy(a)
>>> a
[[1, 10, 3], [4, 5, 6]]
>>> b
[[1, 10, 3], [4, 5, 6]]
>>> a[0][1] = 9
>>> a
[[1, 9, 3], [4, 5, 6]]
>>> b    # b doesn't change -> Deep Copy
[[1, 10, 3], [4, 5, 6]]

To explain, list(...) does not recursively make copies of the inner objects. It only makes a copy of the outermost list, while still referencing the same inner lists, hence, when you mutate the inner lists, the change is reflected in both the original list and the shallow copy. You can see that shallow copying references the inner lists by checking that id(a[0]) == id(b[0]) where b = list(a).

I believe a lot of programmers have run into an interview problem where they are asked to deep copy a linked list, however this problem is harder than it sounds!

In Python, there is a module called copy with two useful functions:

import copy
copy.copy()
copy.deepcopy()

copy() is a shallow copy function. If the given argument is a compound data structure, for instance a list, then Python will create another object of the same type (in this case, a new list) but for everything inside the old list, only their reference is copied. Think of it like:

newList = [elem for elem in oldlist]

Intuitively, we could assume that deepcopy() would follow the same paradigm, and the only difference is that for each elem we will recursively call deepcopy, (just like mbguy's answer)

but this is wrong!

deepcopy() actually preserves the graphical structure of the original compound data:

a = [1,2]
b = [a,a] # there's only 1 object a
c = deepcopy(b)

# check the result
c[0] is a # False, a new object a_1 is created
c[0] is c[1] # True, c is [a_1, a_1] not [a_1, a_2]

This is the tricky part: during the process of deepcopy(), a hashtable (dictionary in Python) is used to map each old object ref onto each new object ref, which prevents unnecessary duplicates and thus preserves the structure of the copied compound data.

Official docs

How to deep copy a list?

Related

Recent Posts