Home Original page

an indexed list - how to do it in python

Olivier Dagenais olivierS.dagenaisP at canadaA.comM
Sat Aug 12 13:07:03 EDT 2000 
It looks to me like you're trying to reproduce the behaviour of VB's
collection class.  When I reproduced it, I was using a linked list (for O(1)
insertion, but O(n) integer index retrieval) as well as a hash table, where
the data of a pair was a reference to a linked list node.

You could use an array for O(n) insertion but O(1) integer index retrieval,
but there isn't (as far as I know) a data structure that permits O(1)
_ordered_ insertion and retrieval.  The closest you get is O(log(n)), and
that's using a balanced tree, like AVL...


--
----------------------------------------------------------------------
Olivier A. Dagenais - Carleton University - Computer Science III


<dmost at magna.com.au> wrote in message news:8n3tm2$jug$1 at nnrp1.deja.com...
> I want to create, in Python, an object that mixes the behavior of a
> sequence and a mapping. The primary behavior should be that of a
> mutable sequence, or list, but the objects in the list should also be
> accessible by a key value.
>
> In my mind, this object would be defined something like this:
>
> Class IndexedSequence:
>     def __init__(self):
>         self.data = []
>         self.keys = []
>         self.index = {}
>
>
> At some point in time, this data structure might look like this:
> self.data = ["nurk", "bazar"]
> self.keys = ["fred", "jill"]
> seld.index = {"fred":0, "jill":1}
>
> Operations that append to this data structure operate just fine.
> The problem is that there is no way to eliminate the renumbering
> required by insertion or deletion.
>
> I could rebuild the index on the next index access operation after
> insertion or deletion, but this seems overly stupid to me.
>
> Given an object and a list to which it belongs, how can I find its
> position in a list in O(1) operations.
>
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
More information about the Python-list mailing list