Introduction to data structures and algorithms in javascript: Associative Arrays

This is the first of a series of posts that will provide a beginner level introduction to data structures and algorithms in javascript.

A fundamental data structure in javascript is the Associative Array. An Associative Array is an abstract data type that is composed of a collection of key, value pairs such that each key exist only once in the collection.

The reason that an Associative Array is considered to be a fundamental data structure in javascript is that every object in the language is in fact an Associative Array.

Consider the following example:

var someArray = new Object();
someArray["A"] = 0;
someArray["B"] = 1;
someArray["C"] = 2;

You can get the values stored in the array by referencing the indexes or by object qualified naming:

alert(someArray["C"]);  // value by index
alert(someArray.C); // value by object qualified naming

An Associative Array can also be created using object literal notation:

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

Doing so creates the exact same array as the earlier example.

An important characteristic of the Associative Array in javascript is the fact that it is an object. In other languages, creation of an array requires that you explicitly define the data type. Any addition to the array that is of a different data type would result in an error. In javascript, the array object is defined by its members.

For example, you can add a method to an associative array:

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

This is an important concept for beginners to understand because it may lead to some unexpected behavior. For example, looping through the array will show that there are four elements rather than three.

for(ind in someArray) {
    alert(ind);
}

This problem is typically solved in javascript by creating your own collection object.

var Collection = function() {
    this.count = 0;
    this.collection = {};
}

This defines a property for the count and an empty array. To make the collection object useful, it needs methods for adding and deleting elements from the collection array. These methods will update the count property.

this.add = function(key, item) {
    this.collection[key] = item;
    this.count  +=  1;
}
this.remove = function(key, item) {
    this.collection[key] = item;
    this.count  -=  1;
}

The collection object can now be used in the following manner:

var someCollection = new Collection();
someCollection.add("A", 0);
someCollection.add("B", 1);
someCollection.add("C", 2);
alert(someCollection.count);
alert(someCollection.collection["A"];
someCollection.remove("C");
Advertisements
Tags:

One Comment to “Introduction to data structures and algorithms in javascript: Associative Arrays”

  1. Thanks for the nicely written post. Following these examples we can create any data structures we need like linked lists, trees etc.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: