JavaScript Data Structures


So far we have only been concerned with primitive data types, numbers, strings, and boolean. Text strings are very powerful, and with suitable library functions to take them apart and manipulate them, you can do almost anything. However, OOPS is the the programming fad du jour, so everybody wants to make everything into objects, even if it doesn't work very well. Therefore the useful string functions in the JavaScript library are buried in the String object. We can live with it. In a few more years some other programming fad will take precedence, and you will need to learn another whole new vocabulary for the same things you will have been doing all along. Think of it as job security. Making things artificially difficult keeps the riff-raff out. If you kept up with me this far, you are too smart to be foiled by it.
 

Arrays

Like strings, JavaScript crams much (but not all) of the array data type into the Array object, but most of what we want to do can be done without reference to that.

In JavaScript you can create an array "literal" by specifying values separated by commas within (square) brackets, thus:

var trees = ["elm", "oak", "maple", "ficus", "pine"];
Later in the program, you can access the array elements one at a time by what is called an index or subscript, an integer (numeric) value in brackets. The first element of a C or JavaScript array is always numbered [0] (see my essay "Why Zero is the First Number"). In out example above, trees[2] is the third element and has the value "maple". When you have array data, it is often convenient to use a for-loop to step through its values:
for (var i=0; i<5; i++) document.write(" "+trees[i]);
You can also change any single value in the array by putting it on the left of an assignment:
trees[2] = "apple";
You could change all of them using a for-loop.

If you give a value to a JavaScript array element beyond the length of the array, the array is extended to include that many elements. This dynamic behavior is frequent in scripting languages but unusual otherwise. Usually you need to declare the array size, and then you are stuck with that size unless you call a built-in function to change it.

A common programming exercise for beginners is the "Seive of Eratosthenes". You can look here for an explanation of what the program needs to do. Here follows how to do it in JavaScript for all the primes less than say 30. I start with an empty array which I fill with the numbers from 0 to 29 (so each number is in its own index). Then we loop though all the numbers starting at 2 (the first prime) looking for (and displaying) the primes, and using them to knock out their multiples in a second for-loop. Notice that the inner loop is incremented by the index of the outer loop, which gets larger each time:

var primes = []; // declared, no elements yet
for (i=0;i<30;i++) primes[i] = i; // fill it
for (i=2;i<30;i++)
{
  if (primes[i]==0) continue;
  document.write("<p>"+primes[i]+" is prime");
  for (n=i;n<30;n+=i) primes[n] = 0;
}
If you need the number of elements in an array, you need to use an object property to get it. You don't need to understand what that means (but after the next section you will) if you just remember that the length of an array is found by a dot after the variable name, followed by the word "length" like this:
document.write("<p>len="+primes.length);
Now let's look at objects to see what the dot means.
 

Objects

Besides arrays, the other interesting data structure is a collection of named values and functions called an object. I suspect they want people to think of the objects of programming as somehow related to real objects out there in the world, but that's in their imagination. Programming is like that, you get to invent any kind of reality you want, and it all exists in the electrons of your computer and the synapses of your brain and nowhere else.

The only truly Object Oriented Programming System (OOPS) that ever existed was SmallTalk, but that was 30 years ago and it's long dead now. However, the ideas were so cool that all the self-appointed language designers hurried to glue onto their own languages something resembling OOPS using duct tape and bubble gum. It shows. C++ comes pretty close, but since it also includes all of C (which was not OOPS at all), the metaphorical duct tape is still very visible and you can get stuck where it peels up. Java is somewhat more pure, but not entirely. Pure OOPS is not really very efficient, and they wanted Java to actually be useful. In JavaScript (which is different from Java, except the name) the OOPS part is just a whitewash. In a true OOPS, a class is a user-defined data type with its own name (which is traditionally capitalized), where you specify the named elements and methods, and variables of that type are called objects. But JavaScript is not strongly typed, so classes are rather hokey.

For historical reasons the functions associated with an OOPS class or object are called methods, but there's not much difference otherwise, except that object methods usually have an implicit parameter called this, which is the object that the method got called on. Once you have an object value (typically in a variable), then you can access its fields (variables within the class) and methods using the dot operator. Yes, they call it an operator, but it does not participate in real expressions, it's just a way to tell the compiler (or interpreter) to look inside the definition of this class for the following name.

Let's look at an example. If you were building a list of your favorite songs, you might define a Music class to describe what you know about each song. For example, you would have a title and an artist (strings), and maybe a play() method for when you wanted to listen to it. The fundamental insight with OOPS is that the object knows how to do (that is, it has a method for) anything you would ever want to do with that object. So if you had a variable mySong of type Music, that song's title would be mySong.title, and you could play the song in your program by calling the method mySong.play().

In other OOPS languages (this does not seem to work in JavaScript) you could define a subclass which has all the properties (data fields) of the parent object, plus additional information. Class SheetMusic would know everything about Music, and also know how to show() it on the screen. GuitarMusic could be a subslass of SheetMusic, but the show() method would also add (this is called overloaded) fingering for chords. And so on. But JavaScript was not intended to be a full programming language (nevermind that it actually is), so they left some of that stuff out. You can still do almost everything you can do in any other language, but some things are harder. OOPS is already harder, so doing things some other way is not that big a penalty.

In any case, most of the JavaScript built-in functions are defined as methods or properties of some built-in class. So if you want to know how long a string variable myVar is, the old functional way (like in C) is to call a function strlen(myVar), but the new OOPS way is to refer to myVar.length in your code. The problem with this is that if you have not been exceedingly careful with your types, it might be that myVar is a different type than String, and that other type might have a length property that means something quite different from what you had in mind. That's not visible here, where you are looking at it. This is why dynamic and weakly typed languages like JavaScript are very hard to write large programs in. You start to forget what you were doing, then you make mistakes. Liberal comments help, but you never know what you will forget before you forgot it, and then you can't remember it to write the comment. Small scripts for controlling a web page interactivity are fine. Small programs to learn programming are OK too. But there are better languages for big stuff.

Another useful string method lookinhere.indexOf(lookfor) tells you the position or index of a short string lookfor in a larger text lookinhere, considered as a method of the larger string. And once you have found it, you might want to extract it or replace it with something else. Here is a simple loop to replace every occurrance of "Peter" in a story with the name "Paul". JavaScript does not have a built-in function or method to replace a piece of text, so we make our own, which is the very essense of programming:

function replacestring(newly,start,len,old)
{
  if (start>0) newly = old.substr(0,start)+newly; // .substr(start,length)
  return newly+old.substr(start+len); // no length param gets all the rest
}

var story = "<p>Peter went to the market, where John told Peter to buy apples."
    + " Then Peter went home.";
var start = 0;
while (true) {
  var here = story.indexOf("Peter",start);
  if (here<0) break; // didn't find any (more)
  story = replacestring("Paul",here,5,story);
  start = here+5;}
document.write(story);

Math

Most programming languages have built-in functions to do the hard mathematical stuff like square root and trigonometry. In JavaScript these are methods of a magical Math object. It is sufficient if you just imagine that the name of the function includes both the Math object name and the dot:
Math.PI          // the value of pi, 3.14159265...
Math.abs(anum)   // the absolute value of anum, -anum if it is negative
Math.sqrt(anum)  // the square root
Math.floor(anum) // the largest integer not greater than anum (discards fraction)
Math.sin(anum)   // the trigonometric sine function
Math.cos(anum)   // the cosine
Many of the other standard math functions are there also. Look here for a complete list. Not many programmers use the math functions, but they are there if you need them. I majored in math at college, but it was almost 20 years before I actually used any in programming (see Tennis). You need to think precisely (as in mathematics), but all the hairy higher math is useless.
 

Web Functions

Not so much value for learning programming in general, but because JavaScript was designed to support the interactivity of web pages, there are numerous "objects" with built-in functions ("methods") for controlling the display of a web page and responding to user interaction. We have been using without explanation the write() method of built-in object document. Now you are in a position to understand what is going on. You can see the complete list here. A few of these come into play in making games work; we'll get to that shortly.

Now you know pretty much everything you need to write programs. In the next page we discuss debugging.

Tom Pittman
Rev 2010 December 22