Why is DList insertion log n?
Ian
ian at iangarcia.net
Mon Feb 17 15:26:18 UTC 2025
On Sunday, 16 February 2025 at 20:57:58 UTC, rkompass 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.
That's fair. So it is O(1) in the end. I was trying and failing
to imagine what kind of operation would be happening there to
make it O(log n).
More information about the Digitalmars-d-learn
mailing list