What are the lesser known but useful data structures?

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.

---

Scapegoat trees. A classic problem with plain binary trees is that they become unbalanced (eg 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.

---

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
}

---

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.

链接地址: http://www.djcxy.com/p/6778.html

上一篇: 在C / C ++中实现工作窃取队列？

下一篇: 什么是较少知道但有用的数据结构？