By now, you are aware that JavaScript is no longer a web browser-only programming language. Over the past several years, several server-side JavaScript engines and frameworks have been introduced, including the Mozilla JavaScript shell and, most importantly, Node.js. These systems require that JavaScript programmers learn new techniques for solving problems in ways they could not implement very efficiently or effectively in the browser.
Many years ago, the Swiss computer scientist Niklaus Wirth wrote a book titled Algorithms + Data Structures = Programs. Wirth wrote that a program is formed from a set of algorithms that are based on particular representations and structures of data. Wirth’s formula for writing a computer program is to start with the proper representation and structure of the data, which when followed by a set of algorithms that act to manipulate and transform the data, lead to a successful computer program. A computer program will not be successful if the data structures underlying it are faulty or insufficient.
Creating Data Structures in JavaScript
When working in JavaScript, the two native data structures you have are the array and the object. Arrays are great when the data you are working with is flat, but very often data take on a different shape, such as hierarchical, associative, or even tree-shaped. Objects can sometimes work quite well to solve associative problems, such as simple mappings, but objects are not as versatile as a custom-made dictionary data structure that is designed to efficiently store and retrieve key-value pairs.
Choosing the proper data structure for a problem is often the key to finding a good solution to a problem. More importantly, choosing the wrong data structure can make some problems almost impossible to solve. For example, if the goal of a program is to be able to search a data set quickly, storing the data as objects in memory is probably the wrong choice. Learning the proper use of data structures will keep choices like this from being made.
Practical Stacks
An example of a data structure that lends itself to efficient solutions is the stack. A stack is a list that only allows access to the top element of the list. You can add new piece of data to the stack (called a push operation), and you can remove the top element from the stack (called a pop operation). The only other major operation allowed is a peek, or view, operation to examine the top element of the stack.
What are stacks used for? In computer science, stacks are used to implement function calling in programming languages, and in computer architecture hardware stacks are used to allocate and access memory. There are many more uses for stacks in computer science, but let’s focus on the use of stacks for more day-to-day tasks.
One good use of a stack is to convert a number from decimal to binary. The algorithm is quite simple: take the number you are converting modulus 2, and push that result on the stack; divide the number by 2, and go back to the previous step while the number is greater than 0. To get the converted number, pop off all the elements of the stack until the stack is empty.
Here’s another stack example: parentheses balancing. Scan an expression and push each left parenthesis and its position onto a stack. When your scanner gets to a right (closing) parenthesis, pop the stack. An unbalanced expression will have a parenthesis left on the stack after the full expression is scanned.
Effective Binary Search Trees
Another data structure that lends itself to very efficient algorithms is the binary search tree. A tree is a data structure where each data element is stored in a node, with the first node being the root node, and nodes below it are child nodes. In a binary tree, each parent node can have exactly two child nodes, one to the left of the parent and one to the right of the parent. In a binary search tree, there is a further rule that child nodes must be ordered with smaller values stored in the left child node and greater values stored in the right child node.
When a binary search tree is fully formed, you can find the minimum value of any data set by following the left child nodes to the bottom of the binary search tree, and the maximum value is found by following the right child nodes to the bottom of the binary search tree. This leads to a huge performance gain over searching through an unsorted data set.
Add to Your Toolbox
The expanding use of JavaScript to solve server-side programming problems presents an opportunity for JavaScript programmers, especially those who don’t have a traditional education in Computer Science, to begin discovering how the use of data structures can help them come up with innovative solutions to the problems they face every day. Being familiar with the common data structures used to solve programming problems and learning how to use them effectively is a key skill in becoming a more professional computer programmer.