What happens internally when concatenating two lists in Python?

Question

When concatenating two lists,

a = [0......, 10000000]
b = [0......, 10000000]

a = a + b

does the Python runtime allocate a bigger array and loop through both arrays and put the elements of a and b into the bigger array?

Or does it loop through the elements of b and append them to a and resize as necessary?

I am interested in the CPython implementation.

Answer 1

You can find out by looking at the id of a before and after concatenating b:

>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> id(a)
140025874463112
>>> a = a + b
>>> id(a)
140025874467144

Here, since the id is different, we see that the interpreter has created a new list and bound it to the name a. The old a list will be garbage collected eventually.

However, the behaviour can be different when using the augmented assignment operator +=:

>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> id(a)
140025844068296
>>> a += b
>>> id(a)
140025844068296

Here, since the id is the same, we see that the interpreter has reused the same list object a and appended the values of b to it.

For more detailed information, see these questions:

• Why does += behave unexpectedly on lists?
• Does list concatenation with the `+` operator always return a new `list` instance?

Answer 2

In CPython, two lists are concatenated in function list_concat.

You can see in the linked source code that that function allocates the space needed to fit both lists.

size = Py_SIZE(a) + Py_SIZE(b);
np = (PyListObject *) list_new_prealloc(size);

Then it copies the items from both lists to the new list.

for (i = 0; i < Py_SIZE(a); i++) {
    ...
}
...
for (i = 0; i < Py_SIZE(b); i++) {
    ...
}

Answer 3

You can see the implementation in listobject.c::list_concat. Python will get the size of a and b and create a new list object of that size. It will then loop through the values of a and b, which are C pointers to python objects, increment their ref counts and add those pointers to the new list.

Answer 4

It will create a new list with a shallow copy of the items in the first list, followed by a shallow copy of the items in the second list. The + operator calls the object.__add__(self, other) method. For example, for the expression x + y, where x is an instance of a class that has an __add__() method, x.__add__(y) is called. You can read more in the documentation.