linked lists and a matter of terminology

[Michael S. Zick]

On Fri May 19 2006 09:34, Robert P. J. Day wrote:
> On Fri, 19 May 2006, Michael S. Zick wrote:
> 
> > On Fri May 19 2006 09:08, Robert P. J. Day wrote:
> > >
> > >   and while we're on the subject of linked lists, can i make a
> > > suggestion to rename those function primitives?  i've never been happy
> > > with primitives like "add_to" and "add_to_end" since they're sort of
> > > vague and wishy-washy.  i think it would be far more meaningful to use
> > > "prepend" and "append", which have *independently* unambiguous
> > > meanings.
> > >
> > >   (as an aside, i've always been thoroughly disgusted with perl's
> > > decision to name the four related operators "push", "pop", "shift" and
> > > "unshift".  what hideous and inconsistent choices.  grrrrrr ...)
> > >
> > >   in any event, i think "prepend" and "append" are more
> > > clearly-defined since they obviously denote an underlying ordering.
> > >
> > >   thoughts?
> > >
> >
> > "prepend" and "append" imply a known order context.
> 
> yup, they sure do.
> 
> > That is, the location they refer to depends on if the list is being
> > used FIFO or FILO.
> 
> i disagree.  "prepend" has always meant "at the front," while "append"
> has always meant "at the end."  if you start getting into distinctions
> of FIFO versus FILO, then you should be using a "stack," not a "list."
> the standard operations on the abstract data type "list" have been
> around for a long time.  there's no reason not to use them here.
> 
> > And if you are using the list to reverse the order become meaningless.
> 
> if you "reverse" a list, then it's a new list with a different order.
> no problem there.  the last shall be first, the first shall be last.
> :-)
>

You can reverse a list by just changing your direction of access without
any data movement.

If you build head->tail and access tail->head the list is effectively
"reversed".

> 
> > But I agree, the current names are ugly (no comment on the 2,000lb
> > camel).
> 
> > How about:
> > add_head, add_tail, rmv_head, rmv_tail?
> 
> well, personally, i'd still go with "append" and "prepend" but a more
> salient question is, what operations *should* be supported for the
> abstract data type you're defining?
> 
> if you want to define a structure that supports LIFO behaviour, you
> should perhaps call it a "stack."  if you want FIFO, well, that's a
> "queue."  all of these things have a long and well-defined history.
> i'm just sayin'.
> 

For any given linked list of elements, the list might be either at any 
moment in the program flow.  Historically, that is where bi-directional
lists came from.

Neither a "stack" or a "gueue" implies: "linked list"
Although a linked list may indeed provide such behaviors.

If you stick with names that describe the function being performed,
rather than the implied behavior of the result, you end up with 
more readable code.

Mike
> rday
> 
> 
>