JavaScript has some good basic facilities for implementing data structures without too much effort. In this article the data structure under review is the collection, including an enumerator.

JavaScript Data Structures 

Contents

1. The Associative Array
2. The String Object
3. The Array object
4. Speed dating - the art of the JavaScript Date object
5. Doing JavaScript Date Calculations
6. A Time Interval Object
7. Collection Object
8. Stacks, Queue & Deque
9. The Linked List
10. A Lisp-like list
11. The Binary Tree
12. Bit manipulation
13. Typed Arrays I
14. Typed Arrays II
15. Master JavaScript Regular Expressions
    * First Draft

JavaScript is not the language you think of to demonstrate deep ideas in computer science, but I can't think why. It is a simple powerful language that lets you do things in different styles of programming so that you can see better what the deeper idea is all about. There is also the small matter that JavaScript is a popular much used language and just occasionally there is a need for a more advanced data structure.

We start off looking at one of the simplest of the advanced data structures - the collection. But first we need to look at the most basic of JavaScript data structures - the associative array. This is also known as a hash and it is the basis for JavaScripts objects. In fact a JavaScript object is just an associative array.

Associative array

The associative array is the fundamental Javascript data structure.

Every object in Javascript is an associative array as well as being whatever else you designed it to be.

For example:

var myArray=new Object();

myArray["A"]=0;
myArray["B"]=1;
myArray["C"]=2;

This creates an associative array and you can retrieve values using array indexing:

myArray["B"];

or standard object qualified naming:

myArray.B;

Which you use just depend on how you are thinking of the instance - as an object or as an associative array. The syntax

myArray["B"];

makes it clear that you are retrieving the data that is associated with the key "B" - this is what an associative array is all about. In general you store some value along with a key and the key is used to retrieve the data. This is also the reason that an associative array is also referred to as key,value storage. 

In the earlier days of computing this sort of storage was complicated and costly to implement but today JavaScript and most other languages offer you a built in associative array. Indeed languages like JavaScript are almost entirely based on the availability of a fast and efficient associative array.

You can also create an associative array using Object Literal notation.

For example

var  MyArray={A:0,B:1,C:2};

creates the same array.

So the only real problem with using a JavaScript associative array is that it can look a lot like an object!

This really only causes a problem when you add methods i.e. function valued properties to an object that you are treating as an associative array.

For example, the only way to step though the contents of an associative array is to use the For in loop:

for(index in myArray){
 alert(myArray[index]);
}

This works perfectly but if myArray has had say a Count method added to return the number of items in the array then the for in loop includes the method.

That is if you try

var  MyArray={A:0,B:1,C:2};
MyArray.Count=function()
{
 return 3
};

for(index in MyArray)
{
 alert(index);
};

You will see displayed A, B C, Count - that is the associative array has four items not three.

The situation is even worse in that that if MyArray has any prototype properties, i.e. properties inherited from its prototype, added to it then these too are included in the for in loop.

This mixing of associative data and properties is a problem if you are trying to create data handling objects. For example, if you want to create a collection object you can't simply add methods to the object that is going to be used to store the collection and expect for in to work.

What this means is that you either have to abandon for in or you have to modify the way that it is used slightly.

As we will see there really isn't a 100% good solution to the problem but the end results are very usable.

There are also changes in ES2015 that make this problem go away but for the moment let's stay with pre-ES2015 JavaScript which runs everywhere. It also gives us a good example of how to implement a simple enumerator.