What are the lesser known but cool data structures?
Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure.<p><a href="http://en.wikipedia.org/wiki/Unrolled_linked_list" rel="nofollow">http://en.wikipedia.org/wiki/Unrolled_linked_list</a><p>The 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.