[kazagistar]

Almost any insertion requires a scan.

[wtetzner]

Well, given that the pointers are contained in the nodes themselves, if a piece of code is already looking at a node when deciding if an insertion is needed, then no additional scan is required.

[jstimpfle]

Many do, but there are also insertions in unsorted lists or insertions after a given element...