## Re: [Ocaml-lib-devel] Re: Re: Dllist with enums

 Re: [Ocaml-lib-devel] Re: Re: Dllist with enums From: skaller - 2004-08-22 15:50:46 On Mon, 2004-08-23 at 01:31, Brian Hurt wrote: > 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). You're assuming that 'append to end of list' is a fundamental operation. However, if a list is just a node pointer, the fundamental operations are the local ones: move forward, move backward, insert before, insert after delete before, delete after In that case, whether the list is terminated by a small circle, or the whole list is a circle, is irrelevant: 'find end' is at best a derived operation, so O(N) performance is OK. In particular, you can track the end of the list if you want. Or the head. Indeed, you might want to make some point in the middle special. Consider a dlist of 'instructions' (I use lists of instructions in my Felix compiler, but they're unfortunately not dlists). It happens some operations really need the head and tail. For example, tail recursion is just a reinitialisation of the argument and a jump to the start, which needs a label .. I would like to check if there is one and insert it if necessary. And 'return e' in a function could be done with an initialisation of a special return variable v, and a jump to the last instruction which says 'return v' -- so i need the second last instruction to be a label. So I could easily need three cursors to easily process the list... and all three need to support queries, movement, and insertion. What I'm saying is -- 'append to end of list' is such a weak operation it isn't worth supporting. Maintaining multiple cursors is already enough, and can do much more, and you only pay for it if you need it. What would be really nice is to preserve the ability functional lists have of allowing pattern matching. -- John Skaller, mailto:skaller@... voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net