>where you need hard O(1) insert even with a high constant factor You will need a truly concurrent memory allocator for that, too... or if you are just the ker

>where you need hard O(1) insert even with a high constant factor You will need a truly concurrent memory allocator for that, too... or if you are just the kernel (one of the reasons the linux kernel can benefit from linked lists) Overall, allocating new objects/memory is not guaranteed O(1).