Re: List container: Insert and Delete

["Nick Roberts" <nickroberts@adaos.worldonline.co.uk>]

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3BEEB766.B50C969@acm.org...
> 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.

I know it sounds like a good idea, but I don't think it is in reality. Just
look at all the messing around that has to be done, with pointers to check
you don't delete this, or to check you don't try to access something after
deleting it. It's just not worth it.

It's all very well saying access will be O(N), but that ignores the fact
that chasing down a linked list of pointers is a fast operation (because
each step is very simple). In practice, using integers to index positions
gains you: simplicty for the user; simplicity for the implementor. With
short lists, it's likely to be the most efficient possible implementation
anyway.

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

Your delicate distinction between an 'iterator' and a 'position' is a little
silly. The reasons why it should not be done with iterators are the same as
the reasons why it should not be done with positions.

I have prepared a proposal, which I am e-mailing to Ted Dennison today for
posting on his web site (which he has kindly agreed to). It defines an
abstract list with a big set of operations. In it is an inner package which
defines an 'unbounded' list type, for which I hope to produce a sample
implementation (based on the classic double linkage model). Then I will add
a (generic) child package with a 'bounded' list type, for which I will
produce an implementation (based on a fixed-size array).

The indexed operations will, of course, be of O(1) for the bounded list, yet
being both based on the abstract list type, they will be algorithmically
interchangeable. So there is a deeper reason for my insistence on indexed
operations: I am trying to make a bigger plan 'come together'.

Finally, my proposal includes all the usual head and tail dicing operations.
Chopping off, or adding on, one item to either end of a list will be the
most frequently used operations anyway, for which arguments about indexing
don't apply. The indexed operations are mainly there for convenience. As I
showed in an example in another thread, really serious manipulations of
lists are best done sequentially.

I hope you will look at my proposal, and perhaps be a little more convinced!

--
Best wishes,
Nick Roberts