A skip list written in Python is itself an optimization. You could simply use a sorted list with the bisect module.