Advanced data structures in practice

Questions

In the 10 years I ve been programming, I can count the number of data structures I ve used on one hand: arrays, linked lists (I m lumping stacks and queues in with this), and dictionaries. This isn t really surprising given that nearly all of the applications I ve written fall into the forms-over-data / CRUD category.

I ve never needed to use a red-black tree, skip list, double-ended queue, circularly linked list, priority queue, heaps, graphs, or any of the dozens of exotic data structures that have been researched in the past 50 years. I feel like I m missing out.

This is an open-ended question, but where are these "exotic" data structures used in practice? Does anyone have any real-world experience using these data structures to solve a particular problem?

Answers

Some examples. They re vague because they were work for employers:

http://en.wikipedia.org/wiki/Heap_(data_structure) http://en.wikipedia.org/wiki/Heap_(data_structure) http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Array_data_structure#Non-linear_formulas http://en.wikipedia.org/wiki/Array_data_structure#Non-linear_formulas http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests http://en.wikipedia.org/wiki/Z-order_(curve) http://en.wikipedia.org/wiki/Z-order_(curve)

Knowing what s out there in data-structures-land comes in handy -- "weeks in the lab can save you hours in the library". The bloom-filter case was only worthwhile because of the scale: if the problem had come up at a startup instead of Yahoo, I d have used a plain old hashtable. The other examples I think are reasonable anywhere (though nowadays you re less likely to code them yourself).

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/389216/advanced-data-structures-in-practice

Related