63

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.

Improve this question
3
  • 7
    Not really an answer, so I'll comment: Some of those are part of the language. All JavaScript objects are maps with arbitrary keys; and as property values can be objects, they form graphs. JavaScript "arrays" (which aren't really arrays) provide stack features (push, pop). Commented May 6, 2011 at 9:36
  • @Crowder Yea, I agree. But keys really have to be either numeric or strings, so I wouldn't call it arbitrary. For push & pop, sure I can use it to implement a queue but not much help with a priority queue. I'm asking for the data structures that js lacks (it lacks many). Commented May 6, 2011 at 9:40
  • That's why it was a comment, not an answer. :-) (And yes, property names must be strings. In fact, even array indexes are property names, and thus strings, although we almost always use numbers -- in theory they're converted to strings and then the property is looked up, although one hopes implementations optimize that.) Commented May 6, 2011 at 9:43

9 Answers 9

Reset to default
37
+50

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Certainly looks promising. I understand you can use it without Google closure compiler?
Indeed, however it's quite convenient to use it with it, cause it's doing type checking and helping to prevent typo's and other occasional bugs.
Those links are now defunct ! Data structure library moved to : docs.closure-library.googlecode.com/git/…. PriorityQueue : search for structs_priorityqueue on this page : docs.closure-library.googlecode.com/git (5 files)
The library has moved to https://developers.google.com/closure/library/. See http://google.github.io/closure-library/api/namespace_goog_structs.html for data structures.
@user2465896 Your second link is broken, and I can't find the docs on structs anywhere.
|
20

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
Improve this answer

Comments

3

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..

Improve this answer

2 Comments

I disagree. Most of the libraries such as underscore.js provide usability features - let you write shorter, more elegant code. How would that help in implementing say, a priority queue. I specifically asked for features that are not present in js. Sure, I can implement a priority along with tries and graphs myself, however if someone has done it for me, I wouldn't mind using this work.
I would go with underscore.js route myself and implement anything thats missing myself. Google Closure is a great library but it really shines when you use it with the closure compiler, besides it looks like something implemented by Java coders and not JavaScript.
3

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.

Improve this answer

Comments

3

Efficient queue.

If you find more of these, could you please add them to jswiki. Thanks. :)

Improve this answer

Comments

3

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.

Improve this answer

Comments

1

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

Improve this answer

Comments

0

data.js.

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.

Improve this answer

1 Comment

This link redirects to http://substance.io/composer/ -- an online print resource. Please update ansere!
0

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.

Improve this answer

3 Comments

Good point, however in my case it was client side Javascript.
What does 'client side' mean?
I meant it's run in a browser.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.