Faster List Intersection Using Skip Pointers

The indexable 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/

Lua : 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.

Another HN'er is busy with something that comes close to this but has a bunch of twists.