What are some lesser known data structures and algorithms that one should know of?

Question

Recently I came across the SkipList data structure. It really helped me to solve an otherwise difficult-to-solve problem. I was struggling to solve it using Balanced Binary tree but it became very complex as the tree needs to be always balanced and I wanted to know the existence of not only a particular value but values in a certain range. SkipList helped me to solve that problem effectively.

I am wondering what other data structures do I need to know of? I know about - Array, List, Stack, Queue, Linked List, hashtable, tree and its different forms like B-tree, Trie etc. Would like to know if you find some other data structure/concept interesting as well as useful in a regular development cycle.

Answer 1

You didn't mention graphs which are very powerful and if you don't know about them you should definitely read up on them. Look up Dijkstra's algorithm and the A* search algorithm as well as general Depth First Search and Breadth First Search.

You also left out heaps, which are often used as the underlying structure for a priority queue. Binary heaps are the simplest, but you could also look into min-max-median heaps, binomial heaps (fast merges) and Fibonacci heaps (fast decrease key - useful for some graph algorithms).

Other interesting data structures include Patricia tries which are space-efficient tries (keyed on substrings instead of characters), splay trees, which are balanced and can be programmed to be persistent. Also checkout Bloom filters, which is a probabilistic data structure that allow you to determine if an element is a member of a set. It can have false positives but not false negatives and is space/time efficient.

Finally, you can go the functional route and look into immutable and persistent data structures. Many of those are just functional versions of data structures you already know. If you are interested in that then I recommend checking out Okasaki's Purely Functional Datastructures.

Answer 2

You have both "List" and "Linked List", and it's not at all clear what difference (if any) you intend between the two. Anyway, one obvious structure you've skipped is the heap (which you might be classing as a type of tree, but that's quite uncertain at best). Ultimately, trees are a subset of graphs, so if you haven't studied graphs (in general) that's probably an area to explore.

I would note that none of these is particularly "recent" though -- they've all been known for decades now. Most of these really general structures have been known for quite a while. More recently discovered ones tend to relate to more specific subject areas.