Javascript Data Structures - a collection object
Javascript Data Structures - a collection object
Written by Ian Elliot   
Thursday, 22 September 2016
Article Index
Javascript Data Structures - a collection object
Enumerators

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.

 

Chapter List 

  1. A collection object

  2. JavaScript Data Structures - the String Object

  3. JavaScript Data Structures - the Array object

  4. Speed dating - the art of the JavaScript Date object

  5. Javascript data structures - Stacks

  6. JavaScript Data Structures - The Linked List

  7. JavaScript data structures - a Lisp-like list

  8. Stacks, Queue and Deque

  9. Javascript data structures - The Binary Tree

  10. JavaScript Data Structures - Typed Arrays I

  11. JavaScript Data Structures - Typed Arrays II

 
datastruct

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.

A Collection object

A standard associative array is an idea starting place for a collection implementation. A collection can be though of as a key value store that keeps track of the data you add to it and has some basic functions to add and remove data. This is almost what an associative array does so it makes sense to start from this augmented by some appropriate methods. 

Let's take the approach of implementing a constructor function that generates a collection object with the methods we need.  The data can be stored internally in an associative array.

The new Collection object has a count property and a collection property.

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

The collection property is the internal associative array that we are going to use to store the key,value pairs. It could be made private using any of the standard techniques based on of closure if you want to restrict access to it.

Adding an item

The first method we need is Add(key,item) which adds a new item under the associated key. With all collections you have to decide if you are going to allow duplicate keys but in most cases its is simpler and more logical to add the restriction that all keys are unique:

this.add=function(key,item)
{
 if(this.collection[key]!=undefined)
                             return undefined;
 this.collection[key]=item;
 return ++this.count
}

This add method returns the current count if the item has been added and undefined if the key already exists in the collection. notice that the count is incremented in the return statement. 

Remove method

A remove method is just as easy to create but in this case we need to make sure that there is actually a key within the collection to be removed:

this.remove=function(key)
{
 if(this.collection[key]==undefined)
                        return undefined;
 delete this.collection[key]
 return --this.count
}

Once again the method either returns the current count of items after the removal or undefined if no item was removed. You can modify this to return the count, no matter what happens.

Notice that way that the add and remove methods automatically keep a count of the number of items in the collection. Also notice that as count is directly accessible this scheme can be defeated. If you want to protect the count then make it private using closure and provide a getCount method.

Item key

Most collection objects also have something like an item(key) method that returns the item corresponding to the key specified. This too is easy to write:

this.item=function(key)
{
 return this.collection[key];
}

Notice that if the key isn't in the collection the returned value is undefined.

Using the Collection

With these methods you can use the collection for useful things but in most cases you would probably define additional methods.

For example a removeAll could be used to clear the collection. You could extend the definition of item to be item(key,item) and allow the user to change the item associated with the key - so creating a mutable collection.

For example:

var myCol=new Collection();
myCol.add("A",0);
myCol.add("B",1);
myCol.add("C",2);
alert(myCol.count);

This creates a new collection and adds three items. The alert displays 3.

To see the value associated with any key you could use:

alert(myCol.item("B"));

which would display 1.

To remove an item:

myCol.remove("C");
alert(myCol.item("C"));
alert(myCol.count);

Now the first alert will show undefined and the count will show 2.

Notice that while the examples use simple values for the key and the value they can in practice be more complicated. For example the key can be any string and the value can be any object. 

 

Banner

<ASIN:059680279X>

<ASIN:0980285801>

<ASIN:0273721534>

<ASIN:0596805527>

<ASIN:0470684143>

<ASIN:0137054890>



Last Updated ( Friday, 30 September 2016 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2016 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.