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

See also: computational complexity.

Let’s now turn to the data structures.

#### 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.