From: Brian H. <bh...@sp...> - 2004-08-21 20:59:03
|
On Sat, 21 Aug 2004, Jesse Guardiani wrote: My opinion: it's six one way, half a dozen the other. > I see negative issues with the counter: > > 1.) Adds a bit of complexity to the code and possibility for bugs. Linked > Lists are already plagued by complexity anyway, some I'm not sure I > see the problem here. Linked lists aren't *that* complex, and adding a counter isn't that big of a deal. > > 2.) An integer counter puts a cap on the number of possible elements. This > is a more serious problem, IMO, which I didn't realize until a few minutes > ago. Not an important one. On a 32 bit system, max_int is 1,073,741,823. Assume each linked list element takes two words of memory, or 8 bytes, that's 8GB of memory. You run out of memory long before you overflow your counter. > > I thought I read someone saying something about List.length being O(1), which > is what sparked the idea in the first place, but now that I look at it, it > looks O(N) too, so... nevermind. > List.length is O(N). That doesn't mean Dllist.length should be. -- "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 |