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

1 2
3
3
votes

I think the FM-index by Paolo Ferragina and Giovanni Manzini is really cool. Especially in bioinformatics. It's essentially a compressed full text index that utilizes a combination of a suffix array and a burrows-wheeler transform of the reference text. The index can be searched without decompressing the whole index.

3
votes

Ternary Search Tree

  • Quick prefix search (for incremental autocomplete,etc)
  • Partial Matching (When you want to find all words within X hamming distance of a string)
  • Wildcard Searches

Quite Easy to implement.

0
3
votes

A queue implemented using 2 stacks is pretty space efficient (as opposed to using a linked list which will have at least a 1 extra pointer/reference overhead).

How to implement a queue using two stacks?

This has worked well for me when the queues are huge. If I save 8 bytes on a pointer, it means that queues with a million entries save about 8MB of RAM.

2
votes

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.

2
  • 3
    The other extreme is C++, where every self-respecting library comes with its own string data type, which is of course incompatible with all the other string types except const char*. Personally, I prefer the environments where I don't have to spend so much time converting strings from one type to another.
    – Niki
    Sep 23, 2010 at 6:48
  • That's one of the reasons I say wonders of C#. It's very rare the case where you need anything beyond string or StringBuilder native types for text.
    – sergiol
    Feb 24, 2012 at 23:21
2
votes

PQ-Trees

2
votes

I personally find sparse matrix data structures to be very interesting. http://www.netlib.org/linalg/html_templates/node90.html

The famous BLAS libraries use these. And when you deal with linear systems that contain 100,000's of rows and columns, it becomes critical to use these. Some of these also resemble the compact grid (basically like a bucket-sorted grid) which is common in computer graphics. http://www.cs.kuleuven.be/~ares/publications/LD08CFRGRT/LD08CFRGRT.pdf

Also as far as computer graphics is concerned, MAC grids are somewhat interesting, but only because they're clever. http://www.seas.upenn.edu/~cis665/projects/Liquation_665_Report.pdf

2
votes

Delta list/delta queue are used in programs like cron or event simulators to work out when the next event should fire. http://everything2.com/title/delta+list http://www.cs.iastate.edu/~cs554/lec_notes/delta_clock.pdf

0
2
votes

Bucket Brigade

They are used extensively in Apache. Basically they are a linked list that loops around on itself in a ring. I am not sure if they are used outside of Apache and Apache modules but they fit the bill as a cool yet lesser known data structure. A bucket is a container for some arbitrary data and a bucket brigade is a collection of buckets. The idea is that you want to be able to modify and insert data at any point in the structure.

Lets say that you have a bucket brigade that contains an html document with one character per bucket. You want to convert all the < and > symbols into &lt; and &gt; entities. The bucket brigade allows you to insert some extra buckets in the brigade when you come across a < or > symbol in order to fit the extra characters required for the entity. Because the bucket brigade is in a ring you can insert backwards or forwards. This is much easier to do (in C) than using a simple buffer.

Some reference on bucket brigades below:

Apache Bucket Brigade Reference

Introduction to Buckets and Brigades

2
  • Yeah, it sounds like a circular linked list with a variant record type along with some O(1) insertion properties. Jul 22, 2010 at 18:34
  • This is also a popular way to implement queues and deques.
    – J D
    Mar 24, 2011 at 22:51
2
votes

A corner-stitched data structure. From the summary:

Corner stitching is a technique for representing rectangular two-dimensional objects. It appears to be especially well-suited for interactive editing systems for VLSI layouts. The data structure has two important features: first, empty space is represented explicitly; and second, rectangular areas are stitched together at their corners like a patchwork quilt. This organization results in fast algorithms (linear time or better) for searching, creation, deletion, stretching, and compaction. The algorithms are presented under a simplified model of VLSI circuits, and the storage requirements of the structure are discussed. Measurements indicate that corner stitching requires approximately three times as much memory space as the simplest possible representation.

2
votes

Burrows–Wheeler transform (block-sorting compression)

Its essential algorithm for compression. Let say that you want to compress lines on text files. You would say that if you sort the lines, you lost information. But BWT works like this - it reduces entropy a lot by sorting input, keeping integer indexes to recover the original order.

2
  • 2
    BWT is purely an algorithm and not a data structure though.
    – J D
    Mar 24, 2011 at 22:54
  • 2
    @Jon, you're technically right, but why make the distinction? In designing data structures, I often find that a data structure and the algorithm around it go hand-in-hand. That one implies the other. Put another way, isn't the whole point of a data structure the operations you can perform on it and their runtime and memory use? I could say that the data structure for the Burrows-Wheeler transform plus run-length encoding is a data structure for representing arbitrary strings whose memory use (unlike a regular character array) is less than O(n) for many strings. And that's interesting. Jul 2, 2011 at 20:33
2
votes

PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric, D.R.Morrison (1968).

A PATRICIA tree is related to a Trie. The problem with Tries is that when the set of keys is sparse, i.e. when the actual keys form a small subset of the set of potential keys, as is very often the case, many (most) of the internal nodes in the Trie have only one descendant. This causes the Trie to have a high space-complexity.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/

2
votes

I am not sure if this data structure has a name, but the proposed tokenmap data structure for inclusion into Boost is kind of interesting. It is a dynamically resizable map where look-ups are not only O(1), they are simple array accesses. I wrote most of the background material on this data structure which describes the fundamental principle behind how it works.

Something like a tokenmap is used by operating systems to map file or resource handles to data structures representing the file or resource.

2
votes

Disjoint Set Forests allow fast membership queries and union operations and are most famously used in Kruskal's Algorithm for minimum spanning trees.

The really cool thing is that both operations have amortized running time proportional to the inverse of the Ackermann Function, making this the "fastest" non-constant time data structure.

1
vote

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

1
vote

Environment tracking recursive structures.

Compilers use a structure that is recursive but not like a tree. Inner scopes have a pointer to an enclosing scope so the nesting is inside-out. Verifying whether a variable is in scope is a recursive call from the inside scope to the enclosing scope.

public class Env
{    
    HashMap<String, Object> map;
    Env                     outer;

    Env()
    {
        outer = null;
        map = new HashMap();
    }

    Env(Env o)
    {
        outer = o;
        map = new HashMap();
    }

    void put(String key, Object value)
    {
        map.put(key, value);
    }

    Object get(String key)
    {
        if (map.containsKey(key))
        {
            return map.get(key);
        }
        if (outer != null)
        {
            return outer.get(key);
        }
        return null;
    }

    Env push()
    {
        return new Env(this);
    }

    Env pop()
    {
        return outer;
    }
}

I'm not sure if this structure even has a name. I call it an inside-out list.

3
  • 1
    Isn't this essentially a Linked List of HashMap<String, Object>? Jan 13, 2011 at 14:25
  • It ends up being more of a tree, i.e. a HashMap of HashMaps. You can't even declare it statically because you don't know the depth ahead of time. If you tried, it would look like this: HashMap<String, HashMap<String, HashMap<String, HashMap<String, ...>>> > Jan 13, 2011 at 15:59
  • One usually uses a Stack<HashMap<String,SymbolInformation>> for this, and one usually makes one pass through the AST, pushing and popping the stack as various scopes are encountered, and updating the hashes as new variables are added. If one really does want to keep the data structure around for lots of different branches of the tree at once, one uses a list in the Lisp sense, where the list nodes are immutable, and the later nodes in the list are shared by multiple lists.
    – Ken Bloom
    Mar 24, 2011 at 23:40
1
vote

There is a clever Data-structure out there that uses Arrays to save the Data of the Elements, but the Arrays are linked together in an Linked-List/Array.

This does have the advantage that the iteration over the elements is very fast (faster than a pure linked-list approach) and the costs for moving the Arrays with the Elements around in Memory and/or (de-)allocation are at a minimum. (Because of this this data-structure is usefull for Simulation stuff).

I know about it from here:

http://software.intel.com/en-us/blogs/2010/03/26/linked-list-verses-array/

"...and that an additional array is allocated and linked in to the cell list of arrays of particles. This is similar in some respects to how TBB implemented its concurrent container."(it is about ther Performance of Linked Lists vs. Arrays)

1
1
vote

Someone else already proposed Burkhard-Keller-Trees, but I thought I might mention them again in order to plug my own implementation. :)

http://well-adjusted.de/mspace.py/index.html

There are faster implementations around (see ActiveState's Python recipes or implementations in other languages), but I think/hope my code helps to understand these data structures.

By the way, both BK and VP trees can be used for much more than searching for similar strings. You can do similarity searches for arbitrary objects as long as you have a distance function that satisfies a few conditions (positivity, symmetry, triangle inequality).

1
1
vote

I had good luck with WPL Trees before. A tree variant that minimizes the weighted path length of the branches. Weight is determined by node access, so that frequently-accessed nodes migrate closer to the root. Not sure how they compare to splay trees, as I've never used those.

1
vote

Half edge data structure and winged edge for polygonal meshes.

Useful for computational geometry algorithms.

1
vote

I think Cycle Sort is a pretty neat sorting algorithm.

It's a sorting algorithm used to minimize the total number of writes. This is particularly useful when you're dealing with flash memory where the life-span of the flash memory is proportional to the amount of writes. Here is the Wikipedia article, but I recommend going to the first link. (nice visuals!)

0
votes
  • 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

4
  • 16
    @Zuu, Ok, I'll give some constructive criticism. You provided many data structures, of which only a small fraction could be considered "lesser known". There are no links in your post and it generally misses the entire point of the question.
    – mmcdole
    Feb 18, 2009 at 20:20
  • It's hard to tell what people would understand by 'lesser known'. Some people barely know what a balanced tree is. And while people might know the term 'heap' they don't know it's a general data structure that can actually be used with sense in a given application.
    – Zuu
    Feb 19, 2009 at 0:54
  • @Zuu: Why don't you create new entries for elsewhere unmentioned Collections? Mar 24, 2011 at 17:12
  • @user unknown, I don't intend to 'maintain' my answers. I find it rude that questions can be change in the first place, effectively leaving all existing answers irrelevant. This answer reflects the original question. If anyone wants to split it up, they're free to do so :-)
    – Zuu
    Apr 6, 2011 at 20:08
0
votes

Right-angle triangle networks (RTINs)

Beautifully simple way to adaptively subdivide a mesh. Split and merge operations are just a few lines of code each.

0
votes

I stumbled on another data structure Cartesian Tree when i read about some algorithms related to RMQ and LCA. In a cartesian tree, the lowest common ancestor between two nodes is the minimum node between them. It is useful to convert a RMQ problem to LCA.

1 2
3

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