Javascript data structures library
AlgorithmData StructuresJavascriptAlgorithm Problem Overview
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.
Algorithm Solutions
Solution 1 - Algorithm
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.
Solution 2 - Algorithm
You can try Buckets is a very complete JavaScript data structure library that includes:
- Linked List
- Dictionary
- Multi Dictionary
- Binary Search Tree
- Stack
- Queue
- Set
- Bag
- Binary Heap
- Priority Queue
Solution 3 - Algorithm
Probably most of what you want is built-in to Javascript in one way or another, or easy to put together with built-in functionality (native Javascript data structures are incredibly flexible). You might like JSClass.
As for the functional features of the language, underscore.js is where it's at..
Solution 4 - Algorithm
I can help you with the maps with arbitrary keys: my jshashtable does this, and there is also a hash set implementation built on top of it.
Solution 5 - Algorithm
If you find more of these, could you please add them to jswiki. Thanks. :)
Solution 6 - Algorithm
Especially for graph-like structures, i find graphlib very convenient:
https://github.com/cpettitt/graphlib/wiki/API-Reference
It is very straight-forward, faster than other implementations I tried, has all the basic features, popular graph-algorithms and a JSON data export.
Solution 7 - Algorithm
Adding a link to a custom javascript library which provides Priority Queues, Tries, Basic Graph processing and other implementation, for future reference of the visitors to this thread . Check out dsjslib
Solution 8 - Algorithm
I don't believe it's as feature rich as you want but it has graphs, hashes and collections.
I would take this a lightweight start that you can extend on.
As for what it does offer, it's well written, efficient and documented.
Solution 9 - Algorithm
Is your javascript in an application, or a web page? If it's for an application, why not outsource the data structures to Redis? There's a client for nodejs
> Redis is an open source, advanced key-value store. It is often referred to as a data structure server since keys can contain strings, hashes, lists, sets and sorted sets.