What are the lesser known but useful data structures?

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.

Bloom filter: Bit array of m bits, initially all set to 0.

To add an item you run it through k hash functions that will give you k indices in the array which you then set to 1.

To check if an item is in the set, compute the k indices and check if they are all set to 1.

Of course, this gives some probability of false-positives (according to wikipedia it's about 0.61^(m/n) where n is the number of inserted items). False-negatives are not possible.

Removing an item is impossible, but you can implement counting bloom filter, represented by array of ints and increment/decrement.

Rope: It's a string that allows for cheap prepends, substrings, middle insertions and appends. I've really only had use for it once, but no other structure would have sufficed. Regular strings and arrays prepends were just far too expensive for what we needed to do, and reversing everthing was out of the question.

Skip lists are pretty neat.

Wikipedia
A skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).

They can be used as an alternative to balanced trees (using probalistic balancing rather than strict enforcement of balancing). They are easy to implement and faster than say, a red-black tree. I think they should be in every good programmers toolchest.

If you want to get an in-depth introduction to skip-lists here is a link to a video of MIT's Introduction to Algorithms lecture on them.

Also, here is a Java applet demonstrating Skip Lists visually.

Spatial Indices, in particular R-trees and KD-trees, store spatial data efficiently. They are good for geographical map coordinate data and VLSI place and route algorithms, and sometimes for nearest-neighbor search.

Bit Arrays store individual bits compactly and allow fast bit operations.

Here are a few:

• Suffix tries. Useful for almost all kinds of string searching (http://en.wikipedia.org/wiki/Suffix_trie#Functionality). See also suffix arrays; they're not quite as fast as suffix trees, but a whole lot smaller.

• Splay trees (as mentioned above). The reason they are cool is threefold:

  • They are small: you only need the left and right pointers like you do in any binary tree (no node-color or size information needs to be stored)
  • They are (comparatively) very easy to implement
  • They offer optimal amortized complexity for a whole host of "measurement criteria" (log n lookup time being the one everybody knows). See http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

• Heap-ordered search trees: you store a bunch of (key, prio) pairs in a tree, such that it's a search tree with respect to the keys, and heap-ordered with respect to the priorities. One can show that such a tree has a unique shape (and it's not always fully packed up-and-to-the-left). With random priorities, it gives you expected O(log n) search time, IIRC.

• A niche one is adjacency lists for undirected planar graphs with O(1) neighbour queries. This is not so much a data structure as a particular way to organize an existing data structure. Here's how you do it: every planar graph has a node with degree at most 6. Pick such a node, put its neighbors in its neighbor list, remove it from the graph, and recurse until the graph is empty. When given a pair (u, v), look for u in v's neighbor list and for v in u's neighbor list. Both have size at most 6, so this is O(1).

By the above algorithm, if u and v are neighbors, you won't have both u in v's list and v in u's list. If you need this, just add each node's missing neighbors to that node's neighbor list, but store how much of the neighbor list you need to look through for fast lookup.

I think lock-free alternatives to standard data structures i.e lock-free queue, stack and list are much overlooked.
They are increasingly relevant as concurrency becomes a higher priority and are much more admirable goal than using Mutexes or locks to handle concurrent read/writes.

Here's some links
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Links to PDF]
http://www.boyet.com/Articles/LockfreeStack.html

Mike Acton's (often provocative) blog has some excellent articles on lock-free design and approaches

I think Disjoint Set is pretty nifty for cases when you need to divide a bunch of items into distinct sets and query membership. Good implementation of the Union and Find operations result in amortized costs that are effectively constant (inverse of Ackermnan's Function, if I recall my data structures class correctly).

Fibonacci heaps

They're used in some of the fastest known algorithms (asymptotically) for a lot of graph-related problems, such as the Shortest Path problem. Dijkstra's algorithm runs in O(E log V) time with standard binary heaps; using Fibonacci heaps improves that to O(E + V log V), which is a huge speedup for dense graphs. Unfortunately, though, they have a high constant factor, often making them impractical in practice.

Anyone with experience in 3D rendering should be familiar with BSP trees. Generally, it's the method by structuring a 3D scene to be manageable for rendering knowing the camera coordinates and bearing.

Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.

In other words, it is a method of breaking up intricately shaped polygons into convex sets, or smaller polygons consisting entirely of non-reflex angles (angles smaller than 180°). For a more general description of space partitioning, see space partitioning.

Originally, this approach was proposed in 3D computer graphics to increase the rendering efficiency. Some other applications include performing geometrical operations with shapes (constructive solid geometry) in CAD, collision detection in robotics and 3D computer games, and other computer applications that involve handling of complex spatial scenes.

Huffman trees - used for compression.

Have a look at Finger Trees, especially if you're a fan of the previously mentioned purely functional data structures. They're a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece.

As per the original article:

Our functional 2-3 finger trees are an instance of a general design technique in- troduced by Okasaki (1998), called implicit recursive slowdown. We have already noted that these trees are an extension of his implicit deque structure, replacing pairs with 2-3 nodes to provide the flexibility required for efficient concatenation and splitting.

A Finger Tree can be parameterized with a monoid, and using different monoids will result in different behaviors for the tree. This lets Finger Trees simulate other data structures.

Circular or ring buffer - used for streaming, among other things.

I'm surprised no one has mentioned Merkle trees (ie. Hash Trees).

Used in many cases (P2P programs, digital signatures) where you want to verify the hash of a whole file when you only have part of the file available to you.

<zvrba> Van Emde-Boas trees

I think it'd be useful to know why they're cool. In general, the question "why" is the most important to ask ;)

My answer is that they give you O(log log n) dictionaries with {1..n} keys, independent of how many of the keys are in use. Just like repeated halving gives you O(log n), repeated sqrting gives you O(log log n), which is what happens in the vEB tree.

How about splay trees?

Also, Chris Okasaki's purely functional data structures come to mind.

An interesting variant of the hash table is called Cuckoo Hashing. It uses multiple hash functions instead of just 1 in order to deal with hash collisions. Collisions are resolved by removing the old object from the location specified by the primary hash, and moving it to a location specified by an alternate hash function. Cuckoo Hashing allows for more efficient use of memory space because you can increase your load factor up to 91% with only 3 hash functions and still have good access time.

A min-max heap is a variation of a heap that implements a double-ended priority queue. It achieves this by by a simple change to the heap property: A tree is said to be min-max ordered if every element on even (odd) levels are less (greater) than all childrens and grand children. The levels are numbered starting from 1.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

• Kd-Trees, spatial data structure used (amongst others) in Real-Time Raytracing, has the downside that triangles that cross intersect the different spaces need to be clipped. Generally BVH's are faster because they are more lightweight.
• MX-CIF Quadtrees, store bounding boxes instead of arbitrary point sets by combining a regular quadtree with a binary tree on the edges of the quads.
• HAMT, hierarchical hash map with access times that generally exceed O(1) hash-maps due to the constants involved.
• Inverted Index, quite well known in the search-engine circles, because it's used for fast retrieval of documents associated with different search-terms.

Most, if not all, of these are documented on the NIST Dictionary of Algorithms and Data Structures

Van Emde-Boas trees. I have even a C++ implementation of it, for up to 2^20 integers.

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
}

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

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.

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.

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).

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.

Counted unsorted balanced btrees.

Perfect for text editor buffers.

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

Fast Compact tries:

• Judy arrays: Very fast and memory efficient ordered sparse dynamic arrays for bits, integers and strings. Judy arrays are faster and more memory efficient than any binary-search-tree.

• HAT-trie: A Cache-conscious Trie-based Data Structure for Strings

• B-tries for Disk-based String Management

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.

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

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

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

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

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.

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.

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

A proper string data structure. Almost every programmer settles for whatever native support that a language has for the structure and that's usually inefficient (especially for building strings, you need a separate class or something else).

The worst is treating a string as a character array in C and relying on the NULL byte for safety.

Binomial heap's have a lot of interesting properties, most useful of which is merging.

• Binary decision diagram (my very favorite data structure, good for representing boolean equations, and solving them. Effective for a great lot of things)
• Heaps (a tree where the parent of a node always maintains some relation to the children of the node, for instance, the parent of a node is always greater than each of it's children (max-heap) )
• Priority Queues (really just min-heaps and max-heaps, good for maintaining order of a lot of elements there the e.g. the item with the highest value is supposed to be removed first)
• Hash tables, (with all kinds of lookup strategies, and bucket overflow handling)
• Balanced binary search trees (Each of these have their own advantages)
  • RB-trees (overall good, when inserting, lookup, removing and iterating in an ordered fashion)
  • Avl-trees (faster for lookup than RB, but otherwise very similar to RB)
  • Splay-trees (faster for lookup when recently used nodes are likely to be reused)
  • Fusion-tree (Exploiting fast multiplication for getting even better lookup times)
  • B+Trees (Used for indexing in databases and file systems, very efficient when latency to read/write from/to the index is significant).
• Spatial indexes ( Excellent for querying for whether points/circles/rectangles/lines/cubes is in close proximity to or contained within each other)
  • BSP tree
  • Quadtree
  • Octree
  • Range-tree
  • Lots of similar but slightly different trees, and different dimensions
• Interval trees (good finding overlapping intervals, linear)
• Graphs
  • adjacency list (basically a list of edges)
  • adjacency matrix (a table representing directed edges of a graph with a single bit per edge. Very fast for graph traversal)

These are the ones i can come to think of. There are even more on wikipedia about data structures