The indexable skip list (http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list) is another interesting structure for this kind of proble

The indexable skip list (http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list) is another interesting structure for this kind of problem. It's an expansion of the concept described, with a probablistic twist. It has O(log(n)) insertion, deletion and random access time, and linear traversal time, for a log(n) space overhead over a standard singly linked list. The main drawback is that, in order to get that kind of performance, you have to know roughly the expected size of your structure in advance (although it should be fairly easy to create one whose "added machinery" grows with the list). Example implmentations: Python : http://code.activestate.com/recipes/576930/ http://code.activestate.com/recipes/576930/ Lua : http://love2d.org/wiki/Skip_list http://love2d.org/wiki/Skip_list (a port of the former by yours truly, with some added functionality). Both are released under the MIT License.