Hey Benjamin, Taking a guess with the information you've given perhaps a <a href="http://en.wikipedia.org/wiki/Hash_table">hash table</a> could help? Fast lookup/retrieval, but just have to consider what you would enumerate as the key, and loading. Let me know if you want some help applying this, memories of a uni assignment have just come flooding back. James. <div class="gmail_quote">2009/6/7 Benjamin M. Schwartz <<a href="mailto:bmschwar@fas.harvard.edu">bmschwar@fas.harvard.edu</a>> <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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 _______________________________________________ Sugar-devel mailing list <a href="mailto:Sugar-devel@lists.sugarlabs.org">Sugar-devel@lists.sugarlabs.org</a> <a href="http://lists.sugarlabs.org/listinfo/sugar-devel" target="_blank">http://lists.sugarlabs.org/listinfo/sugar-devel</a> </blockquote></div>