The pointer to where the list really starts must be retained for the purpose of freeing the memory appropriately.

Indeed, remove(0) could be made faster by having a second pointer which is increased in this case. And if an .add(0, x) happens afterwards, this could be made faster by decrementing this "data start timer" as long as it is bigger than the "memory start timer".

But all other operations, i. e. insertions and deletions to other indexes, would still be O(n), so that wouldn't change much.

Just know what your operations will be and thus which data structure to pick.

From the docs:

list.remove(x) Remove the first item from the list whose value is x. It is an error if there is no such item.

Without going into the details of the implementation, the item to remove can be anywhere in the list. A linear scan time is necessary in order to find the item before it can be removed. Once you find the index of the item to remove, you need to shift all the elements down by one index. In any case there's index amount of traversal and size - index amount of shifting involved. Therefore the removal time is equivalent to traversing the entire list: O(n).

You can find the source here: https://hg.python.org/cpython/file/tip/Objects/listobject.c#l2197 (also look for list_ass_slice(..)).

However, a set is different. It uses the hash value of the object being stored to locate it in its buckets. On an average, locating of objects using hash value is almost constant time. Note that it might not always be constant time where there's hash collision and a further search is required. But assuming a good hash function, it usually is.

UPDATE: I must thank Stefan Pochmann for pointing out the mistake.

The cost of a remove is O(n) as you have to shuffle the elements to the "right" of that point "left" by one:

                 Delete D
                     |
                     V
+-----+-----+-----+-----+-----+-----+-----+
|  A  |  B  |  C  |  D  |  E  |  F  |  G  |
+-----+-----+-----+-----+-----+-----+-----+
                     <------------------
                      Move E, F, G left

If your test code is giving you O(1) then I suspect you're not measuring it properly :-)

The OpenJDK source, for example, has this:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

and the System.arraycopy is the O(n) cost for this function.

In addition, I'm not sure you've thought this through very well:

for (int i = 0; i < list.size() ; i++)
    list.remove(i);

This is going to remove the following elements from the original list:

    0, 2, 4, 8

and so on, because the act of removing element 0 shifts all other elements left - the item that was originally at offset 1 will be at offset 0 when you've deleted the original offset 0, and you then move on to delete offset 1.