Re: List Strawman JC01

[Ted Dennison<dennison@telepath.com>]

In article <3C0FAF78.6F006DF7@boeing.com>, Jeffrey Carter says...
>
>Since the time complexity comments were in my package, I thought we were
>talking about it. Its name is "List_Strawman_JC01", it has no parent
>package, and we have no other kind of list to compare it to.

The whole goal here is to progressively modify the strawman to a point where
there can be enough of a consensus to move forward on it. To that end, I thought
you were presenting your ideas in package form, rather than just arguing them
verbally. If there a consensus around any of those ideas, I would then put them
in the strawman. Remember that the strawman is not *my* baby, its *ours*. There
is certianly stuff in there that I would do completely differently if I were
writing the package by myself.

I hope we are not involved in a process where everyone feels like they are going
to go out and make their own package and convince people to use that package
instead. That's not drawing people together, its splintering them apart. If that
starts happening, clearly this whole process is doomed.

Perhaps I am just overreacting, and you are only trying to say that you think
the strawman doesn't need to be in a package hierarchy?

>Much of your discussion of "<" does not seem to be about package
>List_Strawman_JC01, which is what we are discussing here. For example
>
>> "Next" requires a direction parameter to disambiguate.
>> The only directional terminology we have at all is "Front" and "Back".
>
>These do not apply to this package.

Ahhh. So what you are saying is that I need to take more of a holistic approach
on the naming issue. That's a good point. 

So really the lynchpin in your argument here is that we change our terminology
from talking about "Front" and "Back" to "First" and "Last". This way we
arbitrarily assign a direction to what is otherwise a directionless data
structure, and then terms that rely on the notion of progressing suddenly make
sense.

I don't think I'd be in favor of that, because that lack of direction is really
an integral part of a (doubly-linked) list, and I don't see directionality
gaining us a great deal of anything for the loss of flexability. But of course
if I turn out to be in the minority on this, I'll so change the strawman.

>I'll ask you to go look at the spec (of List_Strawman_JC01) again. There
>is a First function, since this is a basic property of a list. There is

No its not. Its a basic property of a *singly* linked list. For a doubly-linked
list, there is no logical "first" element, and working from either end is
equivalent.

>The ordering property applies for all lists, regardless of
>implementation, just as it applies for arrays. An array is sorted in
>ascending order if no element is less than a preceding element. The fact
>that you can do
(examples using other data structures deleted)
You can't use examples of *other* data structures to make your point, because
they aren't doubly-linked lists. This reflexive property is what makes a
doubly-linked list different from arrays and singly-linked lists.

OK. Lets try a thought experiment here. Picture in your mind's eye an array
rotating slowing in space. You don't have any markers on it; its just a string
of values. How do you know which is the "first" element? That's easy right? You
just find the side with the lowest index.

Now lets try the same thought experiment with a singly linked list. You've got a
string of cells linked with directional arrows rotating in space with
directional arrows going between them. How do you know which is the "first"
element? Again, this is easy. Its the element that only has an arrow going out
of it, and no arrow going into it.

Now lets do the same thing with a doubly-linked list. We have a string of cells
with bidirectional arrows between them rotating in space. Now how do you find
which element is the "first" one? 

The answer of course is that you *can't*. What we have here is a truly
direction-neutral structure. We could always go "eeny-meeny-miny-mo" and pick
one of course. But just because we did that doesn't suddenly make a directional
bias inherent in the data structure. Its something the user imposes, and its
there only in as much as the user believes in it and adheres to it.

I'd like to hear from one of the instructors in the audience about this. After
all, you are the ones who have to teach students data structures using this
thing.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.