The complexity of insert an element in a list

We may think that insert an element in a list’s complexity is O(1). Here the list, I mean the std::list in C++. Yes, sometimes, it is correct. However, we need also to take the time of finding the iterator into account.

Here is a pretty clear explanation

Inserts anywhere in a std::list are constant time operations.
That said, before you can insert, you need to get an iterator to the location you'd like to insert to, which is a linear time operation unless you're talking about the front or back.

Related problem

406. Queue Reconstruction by Height

Solution

I am using python’s list here. Python’s list is not the data structure list, from the data structure’s perspective, it is more like a stack.

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(x[0], -x[1]))
        res = []
        while people:
            h, v = people.pop()
            res.insert(v, [h, v])
        return res

I am still looking for an O(1) solution to insert the element into a specified spot.