Re: List container: Insert and Delete

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Nick Roberts wrote:
> 
> (b) For a list based on an array, the operation: "delete the third item" is
> easy to implement, and fairly efficient for short lists; "insert before the
> third item" is ditto; and "replace the third item" is both easy and
> efficient (for any length of list). For a list based on a linked-list, the
> implementations of these operations are easy, and pretty efficient for short
> lists and for operations near to either end of the list.

For a bounded list (based on an array), deleting the third item is no
easier to implement than for an unbounded list, just as finding the Ith
item is O(N) for both types of list, unless a very poor implementation
is chosen for the bounded list.

-- 
Jeffrey Carter