[Epa095]

I got the impression that the expected performance of the double linked list insertion is actually O(1), since in most cases the elements arrive in sorted order. It's been a time since my algorithm courses, but I think all the 'normal' trees have log(n) insertion in that case.

[nrdvana]

O(n) is generally indistinguishable from O(log n) so if there is any chance of different behavior than the expected optimum, go with the better algorithm.