Well Known JavaScript Libraries for Data Structures?

Dejas · Oct 10, 2007

I'd like to be able to program using common data structures in
JavaScript such as hash tables and binary trees. I'd like to avoid
reinventing the wheel programming them myself so I thought I would ask
if well known and tested libraries already exist for JavaScript that
have these common data structures. Do such libraries publicly exist?

drink.the.koolaid · Oct 11, 2007

I'd like to be able to program using common data structures in
JavaScript such as hash tables and binary trees. I'd like to avoid
reinventing the wheel programming them myself so I thought I would ask
if well known and tested libraries already exist for JavaScript that
have these common data structures. Do such libraries publicly exist?

Not sure about libraries, but javascript arrays may be implemented
internally as hash tables... They supported key and numeric indexed
values:

<html>
<body>
<script>
var ar=new Array();
ar["Dogs"]=1;
ar["Dig"]=2;
ar[3]="Holes";
ar[4]=" In the Dirt";
document.write(ar["Dig"]);
document.write(ar[3]);
document.write(ar[4]);
</script>
</body>
</html>

Evertjan. · Oct 11, 2007

drink.the.koolaid wrote on 11 okt 2007 in comp.lang.javascript:

I'd like to be able to program using common data structures in
JavaScript such as hash tables and binary trees. I'd like to avoid
reinventing the wheel programming them myself so I thought I would ask
if well known and tested libraries already exist for JavaScript that
have these common data structures. Do such libraries publicly exist?

Click to expand...

Not sure about libraries, but javascript arrays may be implemented
internally as hash tables... They supported key and numeric indexed
values:

<script>
var ar=new Array();
ar["Dogs"]=1;
ar["Dig"]=2;
ar[3]="Holes";
ar[4]=" In the Dirt";
document.write(ar["Dig"]);
document.write(ar[3]);
document.write(ar[4]);
</script>

The assay is partly used as an object,
which has nothing to do with it's array behavour.

Richard Cornford · Oct 14, 2007

Is that the choice then; to use a "well known and tested" library or to
write them yourself?

It is much more likely that individual data structures have been
implemented in isolation. Searching this group for "HachTable", for
example, would turn up numerous implementations.

Do such libraries publicly exist?

Not sure about libraries, but javascript arrays may be
implemented internally as hash tables...

And they may not. Internal implementation details vary between
implementations.

They supported key and numeric indexed
values:

But they are still not suitable substitutes for a hash table data
structure because they never have the quality of being 'empty' (some
'keys' always map to values from the start of their existence). That
means you cannot safely use arbitrary keys with such objects.

Richard.

Thomas 'PointedEars' Lahn · Oct 14, 2007

Richard said:
But they are still not suitable substitutes for a hash table data
structure because they never have the quality of being 'empty' (some
'keys' always map to values from the start of their existence).

I assume you mean that is because of the prototype chain.

That means you cannot safely use arbitrary keys with such objects.

I think that would depend on the hash table implementation. An
implementation could map user-defined "keys" to previously unused
property names (with reduced efficiency and maybe even reduced
compatibility, of course).

PointedEars

Bart Van der Donck · Oct 14, 2007

Richard said:
drink.the.koolaid said:

They [arrays] supported key and numeric indexed
values:

Click to expand...

But they are still not suitable substitutes for a hash table data
structure because they never have the quality of being 'empty' (some
'keys' always map to values from the start of their existence). That
means you cannot safely use arbitrary keys with such objects.

I think this is inevitable in all fully object-oriented languages. I
tend to think it's a disadvantage. Feature-detecting every assignment,
something like

if (!objectName.myProperty) objectName.myProperty = 'myValue';

wouldn't be too practical too IMHO. A good dose of common sense is
perhaps best here, and just avoid the use of any 'dangerously'
sounding object- or property names.

I disagree that a user-defined Object could not be a suitable
substitute for the classic hash table. It's meant in javascript to use
them this way. Of course, like you said, with the important remark
that some property names are pre-populated.

Use Cases for Concurrent Data Structures	1	Sep 2, 2010
JavaScript libraries questions	20	Jun 6, 2009
Basic data structures question	2	Jun 9, 2008
Suggestions about transparent data structures	12	Feb 12, 2009
Collecting Rich Data Structures for students	10	Jan 9, 2008
recommended libraries for B-trees / linked lists / sort etc . . .	2	Mar 10, 2008
Looking for an Algorithms and Data Structures Book	28	Oct 24, 2005
suggestions about data structures for a sparse matrix class	3	Feb 14, 2009

Well Known JavaScript Libraries for Data Structures?

Dejas

drink.the.koolaid

Evertjan.

Richard Cornford

Thomas 'PointedEars' Lahn

Bart Van der Donck

Ask a Question

Similar Threads

Members online

Forum statistics

Latest Threads