How is list += implemented in Python?

Question

What is its time and space complexity?

I haven't been able to find an authoritative answer elsewhere on the web.

Also, not sure why, but StackOverflow won't let me post this question until I write more text in this box.

I'm left wondering, where's your question? By simply saying _"What is its time and space complexity?"_ no one will figure it out for you, I thought I'm reading physics here. You should add examples and explain what you're looking for. — GIZ, Jun 17 '16 at 17:14
@direprobs: Time and space complexity are standard computer programming terms; the question's meaning is evident without examples or further explanation. — user2357112, Jun 17 '16 at 17:26
@direprobs: both terms have CS meaning too, they are not just physics terms. — Martijn Pieters, Jun 17 '16 at 17:26
There are answers here on SO that [detail how `+=` works](http://stackoverflow.com/questions/2347265/why-does-behave-unexpectedly-on-lists), and from there found that [this is already documented on the Python wiki](https://wiki.python.org/moin/TimeComplexity). — Martijn Pieters, Jun 17 '16 at 17:35
Welcome to Stack Overflow. If the form is trying to stop you posting short, unspecific questions, then maybe you need to rethink your question, not just type filler text. Ingest [ask] to have a better experience in future. — Peter Wood, Jun 17 '16 at 17:39
This kind of thing is a lot harder to find than you might expect for a newbie. The wiki page doesn't actually list `+=` or space complexity, and the resources that come up for a search for `Python list += complexity` don't make it apparent that `+=` and `extend` are mostly equivalent. It's harder than you'd expect to get the filter to accept your questions, too, especially since the feedback is pretty bad. I actually had to make my first question *worse* to get the site to take it when I was starting out. — user2357112, Jun 17 '16 at 17:51

user2357112 · Answer 1 · 2016-06-17T17:34:18.193

l += other_thing is mostly equivalent to

l.extend(other_thing)

or

for thing in other_thing:
    l.append(thing)

Under the hood, the list stores an array of pointers to its elements, usually with extra space at the end to accommodate future elements. Appending elements consists of a pointer copy and a reference count update if the list has room; if the list is out of room, the array is copied into a multiplicatively larger array first.

The average-case and amortized time complexity of the += operation is O(len(other_thing)); the worst-case time complexity is O(len(l) + len(other_thing)). The size of the individual elements doesn't matter. The operation could require O(len(l) + len(other_thing)) space for a resize, although most of the space it uses is part of l.

score 3 · Answer 2 · answered Jun 17 '16 at 17:25

the source code for python is freely available on github so you can always go look at it

static PyObject *
list_inplace_concat(PyListObject *self, PyObject *other)
{
    PyObject *result;

    result = listextend(self, other);
    if (result == NULL)
        return result;
    Py_DECREF(result);
    Py_INCREF(self);
    return (PyObject *)self;
}

as you can see it just calls listextend, which you can see the complexity of at https://wiki.python.org/moin/TimeComplexity

How is list += implemented in Python?

2 Answers2