[python] How to deep copy a list?

I have some problem with a List copy:

So After I got E0 from 'get_edge', I make a copy of E0 by calling 'E0_copy = list(E0)'. Here I guess E0_copy is a deep copy of E0, and I pass E0_copy into 'karger(E)'. But in the main function.
Why does the result of 'print E0[1:10]' before the for loop is not the same with that after the for loop?

Below is my code:

def get_graph():
    f=open('kargerMinCut.txt')
    G={}
    for line in f:
        ints = [int(x) for x in line.split()]
        G[ints[0]]=ints[1:len(ints)]
    return G

def get_edge(G):
    E=[]
    for i in range(1,201):
        for v in G[i]:
            if v>i:
                E.append([i,v])
    print id(E)
    return E

def karger(E):
    import random
    count=200 
    while 1:
        if count == 2:
            break
        edge = random.randint(0,len(E)-1)
        v0=E[edge][0]
        v1=E[edge][1]                   
        E.pop(edge)
        if v0 != v1:
            count -= 1
            i=0
            while 1:
                if i == len(E):
                    break
                if E[i][0] == v1:
                    E[i][0] = v0
                if E[i][1] == v1:
                    E[i][1] = v0
                if E[i][0] == E[i][1]:
                    E.pop(i)
                    i-=1
                i+=1

    mincut=len(E)
    return mincut


if __name__=="__main__":
    import copy
    G = get_graph()
    results=[]
    E0 = get_edge(G)
    print E0[1:10]               ## this result is not equal to print2
    for k in range(1,5):
        E0_copy=list(E0)         ## I guess here E0_coypy is a deep copy of E0
        results.append(karger(E0_copy))
       #print "the result is %d" %min(results)
    print E0[1:10]               ## this is print2

This question is related to python list copy deep-copy

The answer is


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]]

If your list elements are immutable objects then you can use this, otherwise you have to use deepcopy from copy module.

you can also use shortest way for deep copy a list like this.

a = [0,1,2,3,4,5,6,7,8,9,10]
b = a[:] #deep copying the list a and assigning it to b
print id(a)
20983280
print id(b)
12967208

a[2] = 20
print a
[0, 1, 20, 3, 4, 5, 6, 7, 8, 9,10]
print b
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10]

just a recursive deep copy function.

def deepcopy(A):
    rt = []
    for elem in A:
        if isinstance(elem,list):
            rt.append(deepcopy(elem))
        else:
            rt.append(elem)
    return rt

Edit: As Cfreak mentioned, this is already implemented in copy module.


Here's an example of how to deep copy a 2D list:

  b = [x[:] for x in a]

If the contents of the list are primitive data types, you can use a comprehension

new_list = [i for i in old_list]

You can nest it for multidimensional lists like:

new_grid = [[i for i in row] for row in grid]

I believe a lot of programmers have run into one or two interview problems 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 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 the answer of mbcoder)

but this is wrong!

deepcopy() actually preserve 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 # return False, a new object a' is created
c[0] is c[1] # return True, c is [a',a'] not [a',a'']

this is the tricky part, during the process of deepcopy() a hashtable(dictionary in python) is used to map: "old_object ref onto new_object ref", this prevent unnecessary duplicates and thus preserve the structure of the copied compound data

official doc


If you are not allowed to directly import modules you can define your own deepcopy function as -

def copyList(L):
if type(L[0]) != list:
    return [i for i in L]
else:
    return [copyList(L[i]) for i in range(len(L))]

It's working can be seen easily as -

>>> x = [[1,2,3],[3,4]]
>>> z = copyList(x)
>>> x
[[1, 2, 3], [3, 4]]
>>> z
[[1, 2, 3], [3, 4]]
>>> id(x)
2095053718720
>>> id(z)
2095053718528
>>> id(x[0])
2095058990144
>>> id(z[0])
2095058992192
>>>

Regarding the list as a tree, the deep_copy in python can be most compactly written as

def deep_copy(x):
    if not isinstance(x, list): return x
    else: return map(deep_copy, x)

@Sukrit Kalra

No.1: list(), [:], copy.copy() are all shallow copy. If an object is compound, they are all not suitable. You need to use copy.deepcopy().

No.2: b = a directly, a and b have the same reference, changing a is even as changing b.

$ python
Python 3.9.0 (tags/v3.9.0:9cf6752, Oct  5 2020, 15:34:40) [MSC v.1927 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> 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
>>> a
[1, [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
>>> exit()

$ python
Python 3.9.0 (tags/v3.9.0:9cf6752, Oct  5 2020, 15:34:40) [MSC v.1927 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = a
>>> a
[[1, 2, 3], [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
>>> a[0] = 1
>>> a
[1, [4, 5, 6]]
>>> b
[1, [4, 5, 6]]
>>> exit()

This is more pythonic

my_list = [0, 1, 2, 3, 4, 5]  # some list
my_list_copy = list(my_list)  # my_list_copy and my_list does not share reference now.

NOTE: This is not safe with a list of referenced objects


Examples related to python

programming a servo thru a barometer Is there a way to view two blocks of code from the same file simultaneously in Sublime Text? python variable NameError Why my regexp for hyphenated words doesn't work? Comparing a variable with a string python not working when redirecting from bash script is it possible to add colors to python output? Get Public URL for File - Google Cloud Storage - App Engine (Python) Real time face detection OpenCV, Python xlrd.biffh.XLRDError: Excel xlsx file; not supported Could not load dynamic library 'cudart64_101.dll' on tensorflow CPU-only installation

Examples related to list

Convert List to Pandas Dataframe Column Python find elements in one list that are not in the other Sorting a list with stream.sorted() in Java Python Loop: List Index Out of Range How to combine two lists in R How do I multiply each element in a list by a number? Save a list to a .txt file The most efficient way to remove first N elements in a list? TypeError: list indices must be integers or slices, not str Parse JSON String into List<string>

Examples related to copy

Copying files to a container with Docker Compose Copy filtered data to another sheet using VBA Copy output of a JavaScript variable to the clipboard Dockerfile copy keep subdirectory structure Using a batch to copy from network drive to C: or D: drive Copying HTML code in Google Chrome's inspect element What is the difference between `sorted(list)` vs `list.sort()`? How to export all data from table to an insertable sql format? scp copy directory to another server with private key auth How to properly -filter multiple strings in a PowerShell copy script

Examples related to deep-copy

Why and when to use angular.copy? (Deep Copy) How to deep copy a list? Copying an array of objects into another array in javascript How create a new deep copy (clone) of a List<T>? How to make a deep copy of Java ArrayList How do I copy a hash in Ruby? How do I clone a range of array elements to a new array? How to clone ArrayList and also clone its contents? What is the difference between a deep copy and a shallow copy?