I am looking for a fast data structure with the following properties: Maintains an indexed list of arbitrary, non-ordered objects (like a python List or C array) Allows fast: Insertion at any location Deletion at any location Lookup of an object by its index Reverse lookup, to determine the index of an object
Python's List has O(1) lookup, but O(N) insert, delete, and reverse-lookup. To make reverse lookup O(1) I could maintain a separate Dict mapping objects to indices, but this would cost an additional O(N) on every insertion and deletion. A linked list has O(1) insertion and deletion, but O(N) lookup and O(N) reverse lookup. I could maintain a separate Dict for the forward and reverse mappings, but this would cost O(N) on every insertion and deletion. A standard self-balancing tree cannot be used because the objects are not ordered, and self-balancing trees require ordered keys. I could use the index of an object as the sort key, but then insertion and deletion are O(N) because all subsequent keys must be altered. I could fabricate new sort keys to ensure that insertions occur at the desired location, but then the length of the keys will grow like O(N), making all operations at least O(N). I feel like there should be some kind of standard tree-like data structure that meets my requirements, but I can't find one. Do you know of one? Am I on a unicorn hunt? --Ben
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Sugar-devel mailing list Sugar-devel@lists.sugarlabs.org http://lists.sugarlabs.org/listinfo/sugar-devel