Javascript data structures library
Solution 1
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
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
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
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
If you find more of these, could you please add them to jswiki. Thanks. :)
julx
Updated on January 05, 2020Comments
-
julx over 4 years
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.
-
julx about 13 yearsI 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.
-
julx over 12 yearsCertainly looks promising. I understand you can use it without Google closure compiler?
-
Paweł Szczur over 12 yearsIndeed, 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.
-
julx over 12 yearsLooks like a solution to a long standing problem. I will definitely check it out.
-
Cesar Canassa over 12 yearsI 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.
-
julx over 12 yearsGood point, however in my case it was client side Javascript.
-
Colonel Panic about 12 yearsWhat does 'client side' mean?
-
julx about 12 yearsI meant it's run in a browser.
-
Cody over 9 yearsThis link redirects to
http://substance.io/composer/
-- an online print resource. Please update ansere! -
Martin Bramwell over 9 yearsThose 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)
-
user2465896 about 9 yearsThe 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.
-
Brian McCutchon almost 8 years@user2465896 Your second link is broken, and I can't find the docs on structs anywhere.
-
user2465896 almost 8 years@BrianMcCutchon The doc on structs is now there: https://google.github.io/closure-library/api/goog.structs.html. The whole API documentation is accessible from the drop-down menu.