Re: List container: Insert and Delete

["Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>]

If its any consolation, I have always heard and used the term "Lists" pretty
much as you have. Stacks, Queues, Single/Double, etc, were always special
cases of a "List". I would consider Trees (binary and otherwise) and Maps
outside of this set, but inside some general set called "Linked Data
Structures" or "Containers".

I'd really hate to have us get hung up on terminology and formalism. I think
if we get something that is generally useful - out of which you can get the
functionality of a stack or queue or whatever - then for *practical* usage,
we've got what we want. If an operation doesn't fit some formal definition,
but is useful and easily implemented, then fine. If soneone isn't going to
be happy about using the term "List" unless it fits some definition, then
lets call them "Gazorenthorpes" and move on. The important thing is having a
data structure of some sort that will exhibit the most common and useful
behavior in real-world programming situations.

Out of all the linked data structures I've ever heard about, the only two
that I've ever used with any frequency are Lists and Maps. (The minute you
get into trees of any sort, they start becoming so specialized to the
application that they always seemed to me to be something that would be
difficult to generalize & still be useful. Better to build them as you need
them...)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:aYeI7.23350$xS6.36692@www.newsranger.com...
>
> 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.