4 ms·
The dynamic array is only amortized O(1) instead of guaranteed O(1) (do you have real-time constraints?), insertion mid-list/queue is always O(n) instead of O(1
by jedbrown 16y ago
The dynamic array is only amortized O(1) instead of guaranteed O(1) (do you have real-time constraints?), insertion mid-list/queue is always O(n) instead of O(1) with an iterator for the linked list variant. I was just disagreeing with "everything else is better with a growable array", the array implementation is indeed better for many common use cases, but splice is not the only exception.
- jemfinch 16y agoYour point about amortization is good. Insertion mid-list is just splice with a singleton; I don't bother mentioning it separately. Those really are the only two advantages of linked lists over growable arrays.
- jedbrown 16y agoOkay, how about removal mid-list with an iterator? Technically that could also be called "splice" after taking sublists, but that makes the term so broad as to be almost useless.