void addToStart(int x, List& L) { L = cons(x, L); }
The time required is Θ(1). That is, it does not depend on the length of L.