mikelikesbikes/data-structures

The Data Structures Challenge

I'm setting myself a challenge: implement 42 data structures in 42 days.

The reason

The real killer insights of CS are in data structures and algorithms. I've done project-specific implementations of various simple structures, and I know a bit in abstract about more complex structures like bloom filters from reading source code. But I know my work would benefit greatly from a thorough grounding in data structures. I'm fed up with not knowing enough, so I'm fixing it. Abstract learning is not sufficient - I want to cement the knowledge by doing.

The structures

Enough talk: here's the unordered list (cobbled together from Stack Overflow posts) with wiki links.

Array-like structures

• Queue
• Priority queue
• Deque
• Double-ended priority queue
• Stack
• Linked list
• Work-stealing queue
• Suffix array
• Disjoint set
• Sparse array
• Sparse matrix

Graphical structures

Basic

• Graph
• Directed graph
• Directed acyclic graph

Heaps

• Heap
• Binary heap
• Fibonacci heap

Trees

• Tree
• Trie (radix tree)
• Binary tree
• Binary search tree
• Weight balanced tree
• Self-balancing binary search tree
• B-tree
• B+tree
• Rope
• Decision tree
• Treap
• R-tree
• Huffman tree
• Merkle tree
• Min-max heap
• Fenwick tree
• Suffix tree
• Suffix trie (note: PDF link, no wiki article)
• Splay tree
• Ternary tree

Probabilistic and streaming structures

• Bloom filter
• Quotient filter
• Skip list
• Counting bloom filter
• Count-Min sketch

Whew! A pretty long list. But many of these build on one another, so that many will inherit from their parent structures. The challenge is less daunting than it might appear at first.

Of course, some of these structures might be prohibitively slow in pure Ruby. I'm thinking in particular of bloom-filters and count-min sketches. But I'm going to go ahread an implement them in Ruby so that I understand them. Then, if performance is weak, I can rewrite in C and use Ruby bindings.

I'm also interested in implementing lock-free versions of as many of the above as possible. I couldn't find a nice list of structures with lock-free implementations, so I'll expand this point as I learn more..

The end

This is a living document - I will update with links to explanatory posts and code as I complete them. I will also structure and annotate the list as I learn more about the structures.

Have I missed an important structure? Is one of these redundant? Suggestions/corrections to this list are welcome.

See you on the other side!