Search code examples
algorithmdata-structuresjavascript

Javascript data structures library

I'd like to ask for recommendation of JavaScript library/libraries that supply an implementation of some basic data structures such as a priority queue, map with arbitrary keys, tries, graphs, etc. along with some algorithms that operate on them.

I'm mostly interested in:

  • The set of features covered,
  • Flexibility of the solution - this mostly applies to graphs. For example do I have to use a supplied graph implementation,
  • Use of functional features of the language - again it sometimes gives greater flexibility,
  • Performance of the implementation

I'd like to point out that I'm aware that it's possible to implement using JavaScript the following data structures:

  • A map, if key values are either strings or numbers,
  • A set, (using a map implementation),
  • A queue, although as was pointed out below, it's inefficient on some browsers,

At the moment I'm mostly interested in priority queues (not to confuse with regular queues), graph implementations that aren't very intrusive as to the format of the input graph. For example they could use callbacks to traverse the structure of the graph rather than access some concrete properties with fixed names.

Solution

  • Edit

    As of August 2024, the Closure Library has been sunsetted as it's "no longer meeting the needs of modern Javascript Development, see the deprecation notice and suggested alternatives, but relevant to this question:

    • For many parts of the library (goog.array, goog.dom, goog.events, goog.json, etc), JavaScript's built-in solutions should be sufficient.
    • For many special-purpose packages (math, data structures, other algorithms), a small focused library is often better than Closure's monolithic approach.

    Original answer

    I recommend to use Closure Library (especially with closure compiler).

    Here you have a library with data structures goog.structs. The library contains:

    goog.structs.AvlTree
goog.structs.CircularBuffer
goog.structs.Heap
goog.structs.InversionMap
goog.structs.LinkedMap
goog.structs.Map
goog.structs.PriorityQueue
goog.structs.Set

    As example you can use unit test: goog.structs.PriorityQueueTest.

    If you need to work on arrays, there's also an array lib: goog.array.

    As noted in comments, the source has moved to github.com/google/closure and the documentation's new location is: google.github.io/closure-library.