Why is DList insertion log n?

[Jonathan M Davis]

On Sunday, February 16, 2025 1:57:58 PM MST rkompass via Digitalmars-d-learn wrote:
>  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.

Actually, the complexity of each of the operations was a key part of the
design, but when you're editing the documentation of a bunch of containers
with the same or similar operations, it's pretty easy to end up with copy
and paste errors that you miss. And they were added early enough in Phobos
v2 that I don't know if they were reviewed by anyone other than Andrei when
he wrote them, which makes it more likely that something would have been
missed.

- Jonathan M Davis