Regard a simple problem of adding elements to a "list", every time into random place, e.g. in Python:

arr = []
for i in range(1000000):
    pos = random.randint(0, len(arr))
    value = random.randint(1000000, 9999999)
    arr.insert(pos, value)

With what data structure it can be effective? Linked list will allow O(1) insertion, but to find a place where to insert, we need to run O(n) from start. Some variants of trees may allow O(log(N)) insertion but it seems finding the proper index is equally difficult.

Wikipedia suggest Skip List with "minor modification" is what we want. Are there another structures (e.g. perhaps some modifications to some type of tree, perhaps, cartesian) useful for this task?