Why is DList insertion log n?

[rkompass]

On Sunday, 16 February 2025 at 18:46:56 UTC, Ian wrote:
> Hi,
>
> I'm looking at the double linked list in std.containers and it 
> says that insertion in front or back are O(log n). How come 
> they are not O(1) ?
>
> https://dlang.org/phobos/std_container_dlist.html#.DList.insertFront
>
> Also, is this question more for "General"? I'm a "new user" and 
> "learning" so it made sense here, but I'm learning my way 
> around the forum.
>
>  Ian


 From the source code at 
[https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784](https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784)
I would say it is O(1), as you expected.
So the docs you refer to seem to be not correct in this case. I 
assume the complexity info did not have the highest priority at 
creation of the docs. Rather attention was on the usage details.