Is using [::-1] in python to reverse a list O(1) space?

user_12060041 0
Viewed 725

So if I wrote:

item_list = item_list[::-1]

Would this be O(1) space? I think that item_list[::-1] results in the creation of a new list, so this might be O(n). Is item_list.reverse() then the proper method to reverse with O(1) space in python?

reverse time-complexity python-3.x list python
1 Answers

You are right that some_list[::-1] creates a new list, and that that list will have n "slots", and thus need O(n) memory.

Furthermore in CPython [GitHub], an interpreter of Python, the .reverse() is done in O(1) memory. Indeed, if we look at the reverse method [GitHub], we see:

/*[clinic input]
list.reverse
Reverse *IN PLACE*.
[clinic start generated code]*/

static PyObject *
list_reverse_impl(PyListObject *self)
/*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
{
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    Py_RETURN_NONE;
}

It thus calls a function reverse_slice, and this is implemented as [GitHub]:

/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

It thus works with two pointers, one that iterates in ascending order, and one in descending order, and these "swap" values with each other, until they meet each other halfway.

user_675790
Related