793
votes

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.

1

83 Answers 83

12
votes

Scapegoat trees. A classic problem with plain binary trees is that they become unbalanced (e.g. when keys are inserted in ascending order.)

Balanced binary trees (AKA AVL trees) waste a lot of time balancing after each insertion.

Red-Black trees stay balanced, but require a extra bit of storage for each node.

Scapegoat trees stay balanced like red-black trees, but don't require ANY additional storage. They do this by analyzing the tree after each insertion, and making minor adjustments. See http://en.wikipedia.org/wiki/Scapegoat_tree.

12
votes

An unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references. It is related to the B-tree.

record node {
    node next       // reference to next node in list
    int numElements // number of elements in this node, up to maxElements
    array elements  // an array of numElements elements, with space allocated for maxElements elements
}
11
votes

2-3 Finger Trees by Hinze and Paterson are a great functional data structure swiss-army knife with great asymptotics for a wide range of operations. While complex, they are much simpler than the imperative structures by Persistent lists with catenation via recursive slow-down by Kaplan and Tarjan that preceded them.

They work as a catenable deque with O(1) access to either end, O(log min(n,m)) append, and provide O(log min(n,length - n)) indexing with direct access to a monoidal prefix sum over any portion of the sequence.

Implementations exist in Haskell, Coq, F#, Scala, Java, C, Clojure, C# and other languages.

You can use them to implement priority search queues, interval maps, ropes with fast head access, maps, sets, catenable sequences or pretty much any structure where you can phrase it as collecting a monoidal result over a quickly catenable/indexable sequence.

I also have some slides describing their derivation and use.

2
  • while you add valuable info, your answer would perhaps have been better formulated by editing the one it is duplicating
    – Francois G
    Jan 14, 2011 at 1:42
  • I didn't spot yours until after I'd written mine, and the prospect of merging 20-odd references together and dealing with whatever feelings I'd bruise by dropping the reference to markcc's incorrect original summary article in someone else's post were more than I'd cared to fiddle with. Feel free to fold it in and I'll delete this one though. Jan 14, 2011 at 23:29
10
votes

Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance.

2
10
votes

One lesser known, but pretty nifty data structure is the Fenwick Tree (also sometimes called a Binary Indexed Tree or BIT). It stores cumulative sums and supports O(log(n)) operations. Although cumulative sums might not sound very exciting, it can be adapted to solve many problems requiring a sorted/log(n) data structure.

IMO, its main selling point is the ease with which can be implemented. Very useful in solving algorithmic problems that would involve coding a red-black/avl tree otherwise.

0
10
votes

I really really love Interval Trees. They allow you to take a bunch of intervals (ie start/end times, or whatever) and query for which intervals contain a given time, or which intervals were "active" during a given period. Querying can be done in O(log n) and pre-processing is O(n log n).

0
10
votes

XOR Linked List uses two XOR'd pointers to lessen the storage requirements for doubly-linked list. Kind of obscure but neat!

9
votes

Splash Tables are great. They're like a normal hash table, except they guarantee constant-time lookup and can handle 90% utilization without losing performance. They're a generalization of the Cuckoo Hash (also a great data structure). They do appear to be patented, but as with most pure software patents I wouldn't worry too much.

8
votes

Binary decision diagram is one of my favorite data structures, or in fact Reduced Ordered Binary Decision Diagram (ROBDD).

These kind of structures can for instance be used for:

  • Representing sets of items and performing very fast logical operations on those sets.
  • Any boolean expression, with the intention of finding all solutions for the expression

Note that many problems can be represented as a boolean expression. For instance the solution to a suduku can be expressed as a boolean expression. And building a BDD for that boolean expression will immediately yield the solution(s).

2
8
votes

Enhanced hashing algorithms are quite interesting. Linear hashing is neat, because it allows splitting one "bucket" in your hash table at a time, rather than rehashing the entire table. This is especially useful for distributed caches. However, with most simple splitting policies, you end up splitting all buckets in quick succession, and the load factor of the table oscillates pretty badly.

I think that spiral hashing is really neat too. Like linear hashing, one bucket at a time is split, and a little less than half of the records in the bucket are put into the same new bucket. It's very clean and fast. However, it can be inefficient if each "bucket" is hosted by a machine with similar specs. To utilize the hardware fully, you want a mix of less- and more-powerful machines.

0
8
votes

The Region Quadtree

(quoted from Wikipedia)

The region quadtree represents a partition of space in two dimensions by decomposing the region into four equal quadrants, subquadrants, and so on with each leaf node containing data corresponding to a specific subregion. Each node in the tree either has exactly four children, or has no children (a leaf node).

Quadtrees like this are good for storing spatial data, e.g. latitude and longitude or other types of coordinates.

This was by far my favorite data structure in college. Coding this guy and seeing it work was pretty cool. I highly recommend it if you're looking for a project that will take some thought and is a little off the beaten path. Anyway, it's a lot more fun than the standard BST derivatives that you're usually assigned in your data structures class!

In fact, as a bonus, I've found the notes from the lecture leading up to the class project (from Virginia Tech) here (pdf warning).

1
  • 1
    This was already (implicitly) mentioned here. Personally, I find quadtrees to be the obvious solution - R-trees are usually more efficient, and in my opinion much cooler. Nov 24, 2010 at 19:26
7
votes

I like treaps - for the simple, yet effective idea of superimposing a heap structure with random priority over a binary search tree in order to balance it.

6
votes

Counted unsorted balanced btrees.

Perfect for text editor buffers.

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html

6
votes

Fast Compact tries:

0
6
votes

I sometimes use Inversion LIsts to store ranges, and they are often used to store character classes in regular expressions. See for example http://www.ibm.com/developerworks/linux/library/l-cpinv.html

Another nice use case is for weighted random decisions. Suppose you have a list of symbols and associated probabilites, and you want to pick them at random according to these probabilities

   a => 0.1
   b => 0.5
   c => 0.4

Then you do a running sum of all the probabilities:

  (0.1, 0.6, 1.0)

This is your inversion list. You generate a random number between 0 and 1, and find the index of the next higher entry in the list. You can do that with a binary search, because it's sorted. Once you've got the index, you can look up the symbol in the original list.

If you have n symbols, you have O(n) preparation time, and then O(log(n)) acess time for each randomly chosen symbol - independently of the distribution of weights.

A variation of inversion lists uses negative numbers to indicate the endpoint of ranges, which makes it easy to count how many ranges overlap at a certain point. See http://www.perlmonks.org/index.pl?node_id=841368 for an example.

0
6
votes

Arne Andersson trees are a simpler alternative to red-black trees, in which only right links can be red. This greatly simplifies maintenance, while keeping performance on par with red-black trees. The original paper gives a nice and short implementation for insertion and deletion.

1
  • IIRC, unbox the red nodes and you have a 2-3 finger tree.
    – J D
    Mar 24, 2011 at 22:53
6
votes

DAWGs are a special kind of Trie where similar child trees are compressed into single parents. I extended modified DAWGs and came up with a nifty data structure called ASSDAWG (Anagram Search Sorted DAWG). The way this works is whenever a string is inserted into the DAWG, it is bucket-sorted first and then inserted and the leaf nodes hold an additional number indicating which permutations are valid if we reach that leaf node from root. This has 2 nifty advantages:

  1. Since I sort the strings before insertion and since DAWGs naturally collapse similar sub trees, I get high level of compression (e.g. "eat", "ate", "tea" all become 1 path a-e-t with a list of numbers at the leaf node indicating which permutations of a-e-t are valid).
  2. Searching for anagrams of a given string is super fast and trivial now as a path from root to leaf holds all the valid anagrams of that path at the leaf node using permutation-numbers.
2
  • (you do, however, lose the ability to do pattern matches. and i'm not entirely sure how you'd do anagrams with . and * in them) Mar 24, 2011 at 19:46
  • I used this to develop a multi-language Scrabble program. To handle blank tiles - when you are descending down from root to leaf, at each node, check how many blanks you have and you can choose to use up a blank to go to a different letter.
    – pathikrit
    Mar 24, 2011 at 20:36
5
votes

I like suffix tree and arrays for string processing, skip lists for balanced lists and splay trees for automatic balancing trees

5
votes

Take a look at the sideways heap, presented by Donald Knuth.

http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx

5
votes

BK-Trees, or Burkhard-Keller Trees are a tree-based data structure which can be used to quickly find near-matches to a string.

5
votes

Fenwick trees (or binary indexed trees) are a worthy addition to ones toolkit. If you have an array of counters and you need to constantly update them while querying for cumulative counts (as in PPM compression), Fenwick trees will do all operations in O(log n) time and require no extra space. See also this topcoder tutorial for a good introduction.

5
votes

Zobrist Hashing is a hash function generally used for representing a game board position (like in Chess) but surely has other uses. One nice things about it is that is can be incrementally updated as the board is updated.

4
votes

Splay Trees are cool. They reorder themselves in a way that moves the most often queried elements closer to the root.

1
  • this is a duplicate answer Perhaps you'd want to add complementary elements to the previous answer ?
    – Francois G
    Jan 15, 2011 at 11:26
4
votes

You can use a min-heap to find the minimum element in constant time, or a max-heap to find the the maximum element. But what if you wanted to do both operations? You can use a Min-Max to do both operations in constant time. It works by using min max ordering: alternating between min and max heap comparison between consecutive tree levels.

1
  • 1
    This is one of my favourite data structures. There is even a variant called a min-max-median heap which allows O(1) retrieval of any of the three.
    – Martin
    Feb 19, 2010 at 0:25
4
votes

B* tree

It's a variety of B-tree that is efficient for searching at the cost of a more expensive insertion.

4
votes

Per the Bloom Filter mentions, Deletable Bloom Filters (DlBF) are in some ways better than basic counting variants. See http://arxiv.org/abs/1005.0352

4
votes

Getting away from all these graph structures, I just love the simple Ring-Buffer.

When properly implemented you can seriously reduce your memory footprint while maintaining performance and sometimes even improving it.

0
3
votes

Skip lists are actually pretty awesome: http://en.wikipedia.org/wiki/Skip_list

3
votes

Priority deque is cheaper than having to maintain 2 separate priority queues with different orderings. http://www.alexandria.ucsb.edu/middleware/javadoc/edu/ucsb/adl/middleware/PriorityDeque.html http://cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf

Not the answer you're looking for? Browse other questions tagged or ask your own question.