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
> 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
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@...
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net