The implementation that uses laziness to get true backpointers seems to have caught everybody's imagination. Several people have hinted at the big weakness of this implementation, but lest any beginners reading this thread be misled, let me just state that weakness explicitly -- it takes O(n) time to make even the simplest change to such a list.* What it boils down to is that this implementation is only useful when the list is mostly static (that is, not updated very often). And, in many situations where the list *is* mostly static, an array might be a better choice. Chris * Laziness can sometimes save you from paying this entire O(n) cost up front, but if you are going to end up eventually looking at the entire list, you'll eventually pay the entire cost. Furthermore, this O(n) cost cannot be amortized across multiple updates -- every update pays an additional O(n).
