16 ms·
I believe you have linked list and vectors flipped. vectors have O(n) insert, and linked lists have O(1) insert. Regardless, your point still stands.
by mdwrigh2 15y ago
I believe you have linked list and vectors flipped. vectors have O(n) insert, and linked lists have O(1) insert. Regardless, your point still stands.
- bunderbunder 15y agoIn the basic case, linked lists are O(n) for inserting at position n, on account of having to follow n elements' worth of pointer trail to get to that position. When you're inserting at the first position (as should normally be the case for most applications to which linked lists are well suited), n happens to be 1. For certain applications where you already have a pointer to position n by the time you find out you need to insert there, then insertion does end up taking constant time as long as it's not a persistent linked list. But big-O is for describing the worst case, not the ideal case that you can achieve given certain optimizations.
- bumeye 15y agoNote that this is such a case where you've already got the pointer. mdwrigh2 is totally right. I flipped the O(1) for linked list insertion with the O(n) for verctor insertion :).