Algorithms and data structures in JavaScript

In today’s article will be a very important topic, namely: algorithms and data structures in JavaScript. It is an important topic for programming in general. We should not have prejudices — Javascript is suitable for this purpose very well. Perhaps some things will be in ths language a bit harder, but that others will be simplified, e.g. basic stack implementation (FIFO).

Algorithms in JavaScript

Today we will focus more on examples of solutions, rather than the theory.

Factorial

A classic example at start — Factorial and recursion.

Example — calculating factorial in JavaScript:

function factorial(n) {
    if (n == 0)
        return 1;
    else
        return (n * factorial(n-1));
}

alert(factorial(5));

Leap year

The next algorithm is to check whether a given year is a leap year or not.


// is leap year - JavaScript
function checkLeapYear(year) {
    if ( ((year % 4 == 0)
          &&
          (year % 100 != 0)) || (year % 400 == 0) ) {
        alert(year + ' is leap');

        return true;
    } else {
        alert(year + ' is NOT leap');

        return false;
    }
}

alert(checkLeapYear(2012));
alert(checkLeapYear(2013));

Min-Max algorithm

So determining the lowest and highest values of the given set.

Example — implementation of the min-max algorithm in JavaScript:

var tab = new Array(16, 9, 86, 48, 59, 2, 78, 240, 18);
// default
var min = tab[0];
var max = tab[0];

for (var i = 0; i < tab.length; i++) {

    if (min > tab[i]) {
        min = tab[i];
    }

    if (max < tab[i]) {
        max = tab[i];
    }
}

alert("Min = " + min + ", Max = " + max);

It’s a simple, but effective implementation based on the comparison among elements in the array.

Random string

This algorithm is a simple generator of random string.


var _list = "abcdefghijklmnopqrstuvwxyz9876543210";

function randomStringGenerator(how_long) {
    var tmp = '', i = 0;
    var list_len = _list.length;

    for (i = 0; i < how_long; i++) {
        tmp += _list.charAt(Math.floor(Math.random() * list_len));
    }

    return tmp;
}

alert(randomStringGenerator(8));

The implementation is based on the input list of characters (it can be any adjusted).

Binary search

Based on the “divide and conquer”, the binary search a simple but optimal way to find the value even in large input lists.

Example — binary search in JavaScript:

inputList = new Array();
inputList[0] = 'E';
inputList[1] = 'I';
inputList[2] = 'O';
inputList[3] = 'P';
inputList[4] = 'Q';
inputList[5] = 'R';
inputList[6] = 'T';
inputList[7] = 'U';
inputList[8] = 'W';
inputList[9] = 'Y';

function binarySearch(inputList, key) {
    var left = 0;
    var right = inputList.length - 1;

    while (left <= right) {
        var mid = parseInt((left + right) / 2);

        if (inputList[mid] == key)
            return mid;
        else if (inputList[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return 'Not found';
}

alert(binarySearch(inputList, 'T'));
alert(binarySearch(inputList, 'Z')); // Not found

Data structures in JavaScript

In JavaScript we implement the data structures without major problems.

Stack / LIFO

A stack or a LIFO (Last In, First Out) is a classic when discussing data structures.

In JavaScript this data structure can be quickly implemented.

Example — a simple implementation of stack in JavaScript:

function ourStack() {
    var stack = new Array();
    stack.push('Audi');
    stack.push('Skoda');
    stack.push('Opel');
    stack.push('VW');

    // in this case VW is at the top of the stack
    // (added as the last)

    alert(stack.toString());
    stack.pop(); // get VW
    alert(stack.toString()); // no VW anymore

    // add new element
    stack.push('Mercedes');
    alert(stack.toString()); // Mercedes on the top
}

ourStack();

We simply used JavaScript arrays and methods. These methods are typical for LIFO implementations:

– push() — add element

– pop() — get (remove) the last element from the stack

This is obviously a very simple approach. We may be tempted to implement more advanced stack, such as here:

http://www.algorytm.org/klasyczne/stos/stos-1-js.html

In JavaScript we can implement in many ways (sometimes really brilliant) other, more advanced data structures, such as linked lists or trees.

Libraries supporting algorithms and data structures in JavaScript

Making own implementations of algorithms and data structures, is certainly an excellent workout of programming.

However, in case of typical algorithms and data structures, it’s good to consider ready libraries, because if something is well done and shared, let’s use it so save our precious time.

Algorithms in JavaScript — a library implements basic algorithms:

https://github.com/idosela/algorithms-in-javascript

Data Structures and Utilities — very interesting library with implementations of many data structures in JavaScript:

https://github.com/monmohan/dsjslib

computer-science-in-javascript — implementation of couple algorithms and data structures, developed by JavaScript guru — Nicholas C. Zakas:

https://github.com/nzakas/computer-science-in-javascript

CryptoJS — is an advanced library that implements the algorithms used in cryptography:

https://code.google.com/p/crypto-js/

And a bonus for the curious:

http://www.codeproject.com/Articles/669131/Data-Structures-with-JavaScript

Summary

Algorithms and data structures are really huge topic. Especially if we add issues of computational complexity and optimization. But without a doubt it is worth to explore these issues.

Personally, I go deeper and deeper into game programming in HTML5 and JavaScript. So in this case (and many others) , algorithms and data structures are essential.

Thank you for your attention.