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.
