Also: binary decision diagrams (BDDs), Prolog's difference lists, and the persistent variants of common data structures. I like skip lists, too, though they seem to be fairly well-known among programmers who don't just naively use linked lists and generic hash tables for everything.
BDDs are already on there (I'd never heard of them before Knuth's fasicle, but I guess he's sort of popularized them), as are a lot of persistent variants.
