list or container O(1)-ish insertion/deletion performance, with array semantics

Question

I'm looking for a collection that offers list semantics, but also allows array semantics. Say I have a list with the following items:

apple orange carrot pear 

then my container array would:

container[0] == apple 
container[1] == orangle 
container[2] == carrot 

Then say I delete the orange element:

container[0] == apple 
container[1] == carrot 

I want to collapse gaps in the array without having to do an explicit resizing, Ie if I delete container[0], then the container collapses, so that container[1] is now mapped as container[0], and container[2] as container[1], etc. I still need to access the list with array semantics, and null values aren't allow (in my particular use case).

EDIT:

To answer some questions - I know O(1) is impossible, but I don't want a container with array semantics approaching O(log N). Sort of defeats the purpose, I could just iterate the list.

I originally had some verbiage here on sort order, I'm not sure what I was thinking at the time (Friday beer-o-clock most likely). One of the use-cases is Qt list that contains images - deleting an image from the list should collapse the list, not necessary take the last item from the list and throw it in it's place. In this case, yet, I do want to preserve list semantics.

The key differences I see as separating list and array: Array - constant-time access List - arbitrary insertion

I'm also not overly concerned if rebalancing invalidates iterators.

Answer 1

You could do an ArrayList/Vector (Java/C++) and when you delete, instead swap the last element with the deleted element first. So if you have A B C D E, and you delete C, you'll end up with A B E D. Note that references to E will have to look at 2 instead of 4 now (assuming 0 indexed) but you said sort order isn't a problem.

I don't know if it handles this automatically (optimized for removing from the end easily) but if it's not you could easily write your own array-wrapper class.