3 ms·
What is the insertion time on this? It seems like it would be O(n) to insert at the head, at which point why don't you just use a vector? [edit]It is always l
by aidenn0 16y ago
What is the insertion time on this? It seems like it would be O(n) to insert at the head, at which point why don't you just use a vector?
[edit]It is always log(n) to insert at end, which is better than vector in the worst-case
- daniel-cussen 16y agoInsertion 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).