From: Brian H. <bh...@sp...> - 2004-08-22 15:22:52
|
On 23 Aug 2004, skaller wrote: > You could also allow circularity, and the condition: > > x.next == x > > can be used to mark the end of a linear list. I like this trick. It allows me to drop the circularity. The downside to doing this is that now I need a pointer not only to the head of the list, but also the tail of the list. With a circular list, I don't, as the tail of the list is just head.prev. Which is where the original t came from- it contained two elements, the head and tail pointers. If you don't have a tail pointer, finding the tail of a non-circular list is O(N). -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |