6

Recently I came across the SkipList data structure. It really helped me to solve an otherwise difficult-to-solve problem. I was struggling to solve it using Balanced Binary tree but it became very complex as the tree needs to be always balanced and I wanted to know the existence of not only a particular value but values in a certain range. SkipList helped me to solve that problem effectively.

I am wondering what other data structures do I need to know of? I know about - Array, List, Stack, Queue, Linked List, hashtable, tree and its different forms like B-tree, Trie etc. Would like to know if you find some other data structure/concept interesting as well as useful in a regular development cycle.

knownothing
  • 57
  • 1
  • 1
  • 8
Shamik
  • 6,938
  • 11
  • 55
  • 72
  • Which language are you using that you have to build this stuff yourself? It is good to know this stuff, but I would avoid writing it myself, especially for production code. – Marcelo Cantos Jun 18 '10 at 14:43
  • I am using Java and C++. There are libraries that I am using for SkipList, but I did not know them at the first place which made me uncomfortable. – Shamik Jun 18 '10 at 14:45
  • Duplicates abound: http://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-cool-data-structures http://stackoverflow.com/questions/559748/what-are-the-complicated-data-structures-you-should-have-heard-of http://stackoverflow.com/questions/953679/what-are-some-of-the-other-old-researched-techniques-that-are-not-in-the-main-s http://stackoverflow.com/questions/654771/algorithms-and-data-structures-that-are-not-mainstream-closed – BlueRaja - Danny Pflughoeft Jun 18 '10 at 17:22

2 Answers2

3

You didn't mention graphs which are very powerful and if you don't know about them you should definitely read up on them. Look up Dijkstra's algorithm and the A* search algorithm as well as general Depth First Search and Breadth First Search.

You also left out heaps, which are often used as the underlying structure for a priority queue. Binary heaps are the simplest, but you could also look into min-max-median heaps, binomial heaps (fast merges) and Fibonacci heaps (fast decrease key - useful for some graph algorithms).

Other interesting data structures include Patricia tries which are space-efficient tries (keyed on substrings instead of characters), splay trees, which are balanced and can be programmed to be persistent. Also checkout Bloom filters, which is a probabilistic data structure that allow you to determine if an element is a member of a set. It can have false positives but not false negatives and is space/time efficient.

Finally, you can go the functional route and look into immutable and persistent data structures. Many of those are just functional versions of data structures you already know. If you are interested in that then I recommend checking out Okasaki's Purely Functional Datastructures.

Niki Yoshiuchi
  • 16,883
  • 1
  • 35
  • 44
  • That is a nice list. I am poor in Graph theory - never really practiced them after college. Any book or study material you would like to recommend me on Graph? – Shamik Jun 18 '10 at 15:00
  • When I started out I was using the CLRS aka *Introduction to Algorithms*, however I remember having some difficulty with it - the pseudo code used in the book isn't always clear. Unfortunately I don't really have any other recommendations. – Niki Yoshiuchi Jun 18 '10 at 15:03
1

You have both "List" and "Linked List", and it's not at all clear what difference (if any) you intend between the two. Anyway, one obvious structure you've skipped is the heap (which you might be classing as a type of tree, but that's quite uncertain at best). Ultimately, trees are a subset of graphs, so if you haven't studied graphs (in general) that's probably an area to explore.

I would note that none of these is particularly "recent" though -- they've all been known for decades now. Most of these really general structures have been known for quite a while. More recently discovered ones tend to relate to more specific subject areas.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111