А знаете ли вы...

[thesz]

...что сборка мусора может улучшать работу кешей?

Причина проста - если сборщик идёт "в глубину", то для списка он скопирует сперва "голову" списка (элемент, хранящий два указателя - на головной элемент и на хвост), потом головной элемент (прямо рядос с "головой"), потом перейдёт к хвосту списка.

В случае деревьев одна ветвь (первая в конструкторе) будет лежать лучше, чем другие. Ну, и что? Всё же лучше, чем совсем как попало.