What are the lesser known but cool data structures?
Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure.http://en.wikipedia.org/wiki/Unrolled_linked_listThe idea is the same as a linked list, but instead of just one element in each node, it stores an entire array.  This simple change fixes the two biggest problems with linked lists — memory overhead and cache efficiency.  It's also easy to tweak to be more "array-like" or more "list-like" as needed.