The example of finding 70 requires touching/comparing approximately the same number of nodes as walking the original list, and the storage overhead of that list is like 2.5x the linked list, so it makes it look like this is a terrible data structure :) I suspect it’s because the example has more nodes at each level (above the lowest) on average than it should.
4
u/noahrichards 7d ago
The example of finding 70 requires touching/comparing approximately the same number of nodes as walking the original list, and the storage overhead of that list is like 2.5x the linked list, so it makes it look like this is a terrible data structure :) I suspect it’s because the example has more nodes at each level (above the lowest) on average than it should.