[poll] anyone else needs fast random element access off a dictionary?

[Peter Hansen]

Duncan Booth wrote:
> 
> Michal Vitecek <fuf at mageo.cz> wrote:
> >  actually you can't update the list in O(1) time because of its internal
> >  working. by updating i do not only mean changing a value already stored
> >  in it but also removing a value off it:
> >
> >  afaik, when an item is removed from a list all items that are "behind"
> >  the one being removed are moved one place "forward" (to allow for O(1)
> >  item lookup), so again in a worst case scenario (when you always remove
> >  from the beginning of the list) you have O(N) time.
> 
> He was suggesting that instead of deleting an item from the end of the list
> you replace it with the element at the end of the list and drop the element
> off the end of the list. If you do it that way you do indeed get O(1) time
> to drop an element from a list. You change the order of elements in the
> list, but that isn't important here.

Need a small correction to the above to avoid confusion:  change first 
line to read "He was sugggesting that instead of deleting an item from 
the *middle* of the list ...."

-Peter