Re: List container: Insert and Delete

[Ted Dennison<dennison@telepath.com>]

In article <3BF14752.B3F3FBC@boeing.com>, Jeffrey Carter says...
>
>I've never actually encountered a situation that needed a bounded list,
>so I really can't comment (not that I'll let that stop me). I have
>encountered situations that needed a bounded queue, however. I have

That's precisely my experience, which is what makes me wonder if it really needs
to be a full O(1)-insert list. Every time I've needed a bounded list, I've ended
up writing a circular queue.

>For a list, the only basic operation that is O(N) in time is usually
>Length; it is of course possible to make Length O(1) by keeping a count,
>but that doesn't seem to be necessary. I would want every operation to
>have its time complexity and pre- and post-conditions (where applicable)
>clearly documented.

I think a lot of us are suffering under a bit of a terminology disconnect here.
I'm used to thinking of "lists" as bascily any linearly linked structure. In a
way, that means it is the union of queues, stacks, and any other nifty concept
that you can come up with using a lineraly linked-list. Thus using our "List"
type, you ought to be able to simulate any of those other aforementioned
structures. But they are all types of lists, and saying a stack isn't a list is
as confusing to me as saying a penny isn't a coin.

Some people however appear to think of "List"s as a specific type of structure
with specific implementations and algorithms. I'm sure somewhere there's a
language or even perhaps a whole software engineering discipline that uses that
definition for lack of a better name (good terms for different types of lists
must be awfully hard to come by once you get a good half a dozen or more of
them).

On the off chance that I'm just way obsolete in my knowledge (My last algorithms
course was 5 whole years ago. It could happen.), I went on a web hunt to see if
I could find any general source of computing knowledge that uses List in the
latter way rather than the former. I came up blank. I did find a few supporting
the former though:

http://hissa.nist.gov/dads/HTML/list.html (Dictionary of Algorithms, Data
Structures, and Problems at NIST)

http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=list&action=Search (Foldoc,
which is always my authoratitive source, but it is user-submitted...)

There were also numerous online Data Structures texts that used "Lists" as a
heading, with stuff like "Singly Linked Lists" and "Doubly Linked Lists" as
subheadings.

Anyway, the strawman was presented with the impression that the goal was to
create a simple basic "List" type from which Queues, stacks, and the like can be
implemented by the user. Acutal implementations of course have to be hashed out,
but I don't believe it was anyone's intention to specify a particular
implementation by choosing the word "List". Just the opposite, in fact.

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