Insertion into the middle is O(n) because you have to rearrange everything after that. Adding something to the end (#'add) is O(logn). Inserting at the head is indeed slow (unless you are willing to break the structure) but there are many reasons not to use a vector; insertion time isn't everything. With vectors, you have to make sure your vector has empty space left or is a dynamic array. Here, you don't have to worry about anything (short of blowing the stack).