I was reading about CPython’s implementation of list.pop(k) method and learned that it takes O(n-k) to remove the kth element of the list since it needs to move the posterior elements one position to the left. But couldn't it be faster when removing the first element if we simply shift the pointer of the list to the second element?
Heres the snippet of the current implementation:
PyObject **items = self->ob_item;
v = items[index];
const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
if (size_after_pop == 0) {
Py_INCREF(v);
list_clear(self);
status = 0;
}
else {
if ((size_after_pop - index) > 0) {
memmove(&items[index], &items[index+1], (size_after_pop - index) * sizeof(PyObject *));
}
status = list_resize(self, size_after_pop);
}
And here's what I have in mind:
PyObject **items = self->ob_item;
v = items[index];
const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
if (size_after_pop == 0) {
Py_INCREF(v);
list_clear(self);
status = 0;
}
else {
if ((size_after_pop - index) > 0) {
if (index == 0) {
self->ob_item = &items[1]; <------- here
} else {
memmove(&items[index], &items[index+1], (size_after_pop - index) * sizeof(PyObject *));
}
}
status = list_resize(self, size_after_pop);
}
But what about removing the first element?
What about it?
So, why if given an implementation of a dynamic array in C we can’t simply shift the pointer of the first element to the second when removing the first?
We can, and such data structures are known. One of the most common variants is called a "circular buffer".
I can't speak specifically to why CPython uses a different approach, but the general tradeoffs involve code complexity vs. performance vs. memory use (vs. possibly other factors). The analysis of those usually involves judgement calls about the frequencies of various use cases, properties of different options with respect to those use cases, and long-term maintenance burden, among others. If there's a better answer in the CPython case than "it seemed like a good idea at the time", then it will be that Guido or whoever judged that a simple variation on dynamic arrays represented the best balance of performance, memory use, and maintainability.
Addendum in response to edited question
Your specific proposed variation is not feasible because it loses the pointer to start of the space allocated for the list elements. It is necessary to retain that pointer, somewhere, or at least to retain enough information to be able to recompute it. Otherwise,
the list could not be expanded beyond its current capacity leaking memory,
the list could not be garbage collected without leaking memory, and
the space previously used for the first element would become unusable. For example, it could not be leveraged to provide for an insert() at index 0.
The first two of those follow from the characteristics of C's dynamic memory allocation functions. realloc() and free() require as input the pointer to the beginning of the allocated region to operate on, as returned by a previous call to malloc(), calloc(), or realloc(). Only that pointer value will do, not, for example, a pointer into the middle of the allocated space.
The last follows because you don't know how much space there is for elements before the first.
Of course, you could retain the information needed to determine the beginning of the allocated region, but then you'd have changed to a different kind of data structure, such as the aforementioned circular buffer. With all the tradeoffs already described.