Re: List container: Insert and Delete

[Jeffrey Carter <jrcarter@acm.org>]

Nick Roberts wrote:
> 
> We're programmers, Jeff, not mathematicians. We don't have to worry about
> what the mathematical definition of a list is. What we do have to worry
> about is what is: (a) useful from a user's point of view; (b) practical from
> an implementational point of view.

I'm a software engineer, but I use lists when I need to insert and
delete at arbitrary points in a sequence, just as with the mathematical
definition.

> 
> My suggestion that insertions and deletions be positioned by specifying an
> integer (starting at 1 for the first item in the list) satisfies (a), I
> think, but not necessarily (b), depending on the implementation.

Positive integers are generally used to indicate positions in lists in
mathematical notation. For a software list implemented using pointers
(an unbounded list), using integers to indicate positions becomes an
O(N) time operation for every reference to the list. It is better to
abstract the concept of a position to something that provides the same
behavior but with O(1) time complexity.

> 
> However, I'm pretty sure that trying to do insertions and deletions while
> iterating through a list fails both (a) and (b) miserably. That's what I was
> trying to get across.

I agree that one should not be doing insertions and deletions while
iterating over a list. Iterators should not allow this, and positions
should generally not be used for iteration.

-- 
Jeff Carter
"I blow my nose on you."
Monty Python & the Holy Grail