What are the lesser known but useful data structures?

language-agnostic data-structures computer-science
f3lix picture f3lix · Feb 1, 2009 · Viewed 360.1k times · Source

There are some data structures around that are really useful but are unknown to most programmers. Which ones are they?

Everybody knows about linked lists, binary trees, and hashes, but what about Skip lists and Bloom filters for example. I would like to know more data structures that are not so common, but are worth knowing because they rely on great ideas and enrich a programmer's tool box.

PS: I am also interested in techniques like Dancing links which make clever use of properties of a common data structure.

EDIT: Please try to include links to pages describing the data structures in more detail. Also, try to add a couple of words on why a data structure is cool (as Jonas Kölker already pointed out). Also, try to provide one data-structure per answer. This will allow the better data structures to float to the top based on their votes alone.

Answer

David Phillips picture David Phillips · Feb 1, 2009

Tries, also known as prefix-trees or crit-bit trees, have existed for over 40 years but are still relatively unknown. A very cool use of tries is described in "TRASH - A dynamic LC-trie and hash data structure", which combines a trie with a hash function.

Related questions

Array versus linked-list

Why would someone want to use a linked-list over an array? Coding a linked-list is, no doubt, a bit more work than using an array and one may wonder what would justify the additional effort. I think insertion of new …

Read More
Ukkonen's suffix tree algorithm in plain English

I feel a bit thick at this point. I've spent days trying to fully wrap my head around suffix tree construction, but because I don't have a mathematical background, many of the explanations elude me as they start to make …

Read More
design a stack such that getMinimum( ) should be O(1)

This is one of an interview question. You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack. For example: consider the below example case #1 5 --> TOP 1 4 6 2 …

Read More