Data Structures in JavaScript

• What is a data structure?
• Linked lists

The variables that we have met up to now have been fairly simple ones. Firstly we met scalar variables which is the technical name for simple numbers and strings. Then, in a later section, we met arrays, which are simply groups of scalar variables all lumped together under a single name. Now we are going to glue those arrays and scalar variables into some larger structures.

If we were dealing with a language such as C++ or Pascal to do this, we would have to know about a type of variable called a pointer. However, neither JavaScript nor its close cousin Java has pointers in the language, so we do the same thing using an array. We will therefore be making a lot of use of arrays in this section.

What is a data structure?

In general, a data structure can be represented on paper using a series of rectangles joined by a series of arrows. The rectangles represent the particular data items and the arrows, the relationships between them. The diagram at the bottom of this page shows some example data structures.

In that diagram, the rectangles represent the single items in the structure (objects such as people, ideas or whatever) and the small dots represent links between the items so that you can track from one object to the next. Although you can create an infinite number of arrangements of data items with different relationships between them, there are only a few standard data structures with which you should be familiar. Having said that, let's get stuck in!

In "proper" computer languages, data structures would be set up by setting aside an area of memory for each node, as necessary, and deleting the memory areas individually when nodes are no longer needed. The only way (that I know of) in JavaScript to create a data structure containing several items (called "nodes") joined together is to put them in an array. Fortunately, unlike languages such as C++, in JavaScript we don't need to specify in advance how many elements the array will have - we can keep adding nodes indefinitely.

Let's define a simple object that we can use for our data structures. We will do this using user-defined objects, a concept that you met in the previous section.

function node (name)
{ this.name = name;
  this.next = -1;
  this.prev = -1;
  this.valid = true;
}

var nodes = new Array();
nodes[0] = new node("Richard");

The data structure, as I have defined it, only contains one piece of real information, name, which is set to the parameter provided, name. Normally, you would have a lot more information in here, but I have kept it brief as I want to concentrate on the mechanics of the whole process. The three other properties of the object are used to maintain the data structure. The nodes themselves are stored in the array nodes, with first node being set up in the first element (number 0). All the other elements will stem from that directly or indirectly.

We'll deal with this.next and this.prev later. They are set to the values -1 to indicate that they have not been assigned yet. For the moment, just look at this.valid. This indicates that an entry in the array contains a valid node, and is not just unused. This might seem unnecessary, as we would only declare nodes that we are about to use, but we may well need to delete nodes from the data structure. Rather than "shuffle up" all the elements that follow it to remove the unwanted one, we can simply mark the deleted node as "invalid", and the array element can be re-used the next time we need a fresh one. We don't even need to delete any data from the node.

Before we go on to study individual data structures, we will need two general routines, one for getting a new (empty) node in the list and one for deleting a node. Deleting the node is the easy part, as I have stated:

function delete_node (which)
{ nodes[which].valid = false;
}

As for getting a new, empty node, we look through all the existing elements in the array. If we find one that already exists, but which doesn't contain valid data (i.e. it is available to be re-used), then we will use that one. If we reach the end of the list without finding such a node, then we will create a new one at the end (using new node()). Either way, the function takes the new name to put in the node as its parameter, and at the end returns the index of the array element that it has created/re-assigned:

function get_node (new_name)
{ var n;
  var len = nodes.length;        // For convenience
  var found_it = -1;             // -1 indicates no free node (yet)
  for (n = 0; n < len; n++)
   if (nodes[n].valid == false)
    found_it = n;                // Found a note to be re-used

  if (found_it == -1)            // Still!
   { nodes[len] = new node(new_name);
     found_it = len;
   }
  else
   nodes[found_it].name = new_name;

  return found_it;        // found_it now holds index of new slot
}

In this array, nodes.length gives the number of elements (used or unused) in the array, but it also gives the index in the array of the first element that is "beyond the array limit", e.g. if there are 10 elements in the array, then nodes.length will be 10, the elements will be numbered 0 to 9, and the first "virgin" element will have the index 10.

Notice that we there are two statements in which we set the name to its new value. nodes[len] = new node(new_name) grabs the space for a new node and sets the name up at the same time. Alternatively, we may be re-using a node (if found_it ends up at some value other that -1). In that case, the name is set up using nodes[found_it].name = new_name.

Just one other point before we start looking at structures in particular. The first node in the list will start off at index 0, but this may change later (if that node is deleted), so we store the index of the starting node in a variable:

var START = 0; // Default value

Now we come to specifics. Each of the following data structures has its own page dedicated to it, so please click on one of the following links:

Singly-linked list	Doubly-linked list
Tree

Go back	Main menu	Top of the page