Re: List Strawman JC01

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Ted Dennison wrote:
> 
> 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?

Perhaps we were talking past each other here. I was discussing this
particular package as a vehicle to allow discussion of alternative names
and items that are still undecided while presenting everything we had
decided. Since the name of the package and the structure and contents of
any hierarchy containing it are still undecided, everything is/should be
presented in the package. I think the time complexity should be
associated with each operation, even if it is summarized elsewhere, in
the interests of locality.

> 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.

This quote seems to summarize the rest of the post (please correct me if
I'm oversimplifying).

Every data structures text I've seen describes the abstract concept of a
list as an ordered sequence of values with one value considered the
first value, another the next value, and so on to the last value. I
certainly haven't seen every data structures text, but I've seen a few,
and this was a general property of all lists in all of them, regardless
of implementation. Have you seen texts that say otherwise?

Generally, the concept of a list is presented something like:

A list X of length N can be considered an ordered sequence of values
x{i}:

x{1}, x{2}, x{3}, ..., x{N}

x{i} is the value at the ith position; x{1} is the value at the first
position, or first value, and x{N} is the last value.

[I use {i} to indicate what is typeset as a subscript; I chose {} to
emphasize that this is a notational inconvenience, not a programming
language.]

This is usually followed by some discussion of list operations from a
mathematical point of view:

X' = x{1}, ..., x{i-1}, y, x{i}, ..., x{N}

This is sufficiently common that we introduce an insertion function as
shorthand:

X' = ins(X,i,y), 1<=i<=N+1

i=N+1 means y is the last value of X'.

This is then followed by a discussion of using lists in programs;
programming issues, such as modifying one list rather than having lots
of lists that vary by one value; implementation issues
(bounded/unbounded; single/double); and one or more sample
implementations, often partial with the missing operations left as
exercises for the reader.

I have done this from memory because I don't have any texts available,
nor have I found any online. [However, see pp 70 and 72 of file
08Pointers.ppt available at

http://cs.calvin.edu/books/c++/ds/1e/NewPPSlides2/

(lecture slides for use with _C++: Introduction to Data Structures_ by
Larry Nyhoff)

for some evidence that such texts consider first and last elements basic
properties of lists.]

I hope this seems familiar, and would welcome comments from any
professors who teach data structures courses or authors who have written
texts. It's important that a standard list package implement basic list
concepts and properties.

Having learned that an implementation of a list is intended to be a
useful concrete version of this abstraction, and that this abstraction
includes the concepts of first, second, and last values, it seems to me
that it follows that every implementation includes these concepts.
Whether it's called First, Front, Head, or Horvald, every list has a
first element.

Imagine a sequence rotating in space, with one end labeled "First" and
the other end, "Last". How do you know which element is the first?

Of course, if what I learned about lists from multiple texts is wrong,
then so are my conclusions. In the meantime, that's my story and I'm
sticking to it.

-- 
Jeffrey Carter