Is using list_[::-1] in python to reverse a list O(n) memory complexity? What about list_.reverse()?

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

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

It thus calls a function?reverse_slice, and this is implemented as:

/*[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:

/* Reverse a slice of a list in place, from lo u
p 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.

So, basically when?using slicing to reverse list you will end up with O(n) memory complexity, while using .reverse() method you will get constant memory complexity (O(1)).

#python #complexity #interviewpreparation #interview #list #reverse