Re: List container: Insert and Delete

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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1413 bytes --]

However, it doesn't solve the question of memory usage. I know the 'classic'
implementation of a bounded list is to have (in effect) a linked list within
an array (or three arrays), but that was not what I actually intended.

I actually intended the 'horrible' choice of an array where the first list
item is stored in the first element of the array, the second in the second,
etc. You might called this the 'na�ve' implementation. The reason why is
because it is the most memory efficient, and I assume that some applications
will require memory efficiency about speed concerns; especially considering
that appends still can be done very fast.

Possibly we need a different nomenclature, e.g. Bounded_List for the classic
implementation, and maybe Bounded_Vector for the na�ve? Or Packed_List?

--
Best wishes,
Nick Roberts




"Ted Dennison" <dennison@telepath.com> wrote in message
news:l%9I7.22965$xS6.35437@www.newsranger.com...
> In article <3BF08501.50C83D22@acm.org>, Jeffrey Carter says...
> >
> >I'm not sure what you're saying here; perhaps that initial "O(N)" should
> >be O(1)? Actually, for a bounded list you have 2 lists in the same
> >array: the real list and a free list. Because of the free list, there is
> >no searching for a hole. Insertions and deletions are O(1) for all
> >positions.
>
> Ahhh. I'd fogotten that you can make a list of the free stuff. That's
right, it
> is O(1).