JavaScript lets you do so much with so little as we show here by implementing a Lisp-like list data structure.

JavaScript Data Structures 

Contents

1. The Associative Array
2. The String Object
3. The Array object
4. Speed dating - the art of the JavaScript Date object
5. Doing JavaScript Date Calculations
6. A Time Interval Object
7. Collection Object
8. Stacks, Queue & Deque
9. The Linked List
10. A Lisp-like list
11. The Binary Tree
12. Bit manipulation
13. Typed Arrays I
14. Typed Arrays II
15. Master JavaScript Regular Expressions
    * First Draft

The purpose of this article isn't to demonstrate how to implement the list processing language Lisp in JavaScript but to demonstrate a number of related ideas.

The first is that JavaScript really is a very powerful language and has many of the facilities which makes Lisp an attractive language. JavaScript's design wasn't influenced directly by Lisp but by a related language that was.

The second is to demonstrate how powerful a data structure the  linked list is and how easily it can be implemented in JavaScript.

First we have to know what a linked list is.

A linked list is composed of a set of data nodes. Each node stores some item of data and a pointer to the next node in the list. So for example you could create a list something like

   [A|---->[B|---->[C|---->[null|

The letters represent the data part of the node and the arrows represent the pointer part.

When you first see a structure like this it is easy to miss how powerful it is. At first sight it looks just like a linear list of items just a string or an array. The extra sophistication comes from adding one feature - allow the data to be anything including another pointer.

With this ability you can low build arbitrary list structures including trees of any arrangement.

For example a simple unbalanced binary tree:

   [|---->[B|---->[C|---->[null|
   V
  [D|---->[|---[E|---->[null|
          V
         [F|---->[null|

You can see how this simple binary node can be used to create more complex data structures by allowing the data to be another list.

A JavaScript list

The next step is to create a data structure in JavaScript that implements the list.

This is almost ridiculously easy and an indication of how powerful JavaScript really is. At this point you might be thinking that what we need is some sort of two part structure that can store data and a reference or perhaps two references.

This is a possible way of doing the job and it does have advantages but there is a simpler and more direct way of solving the problem.

The first thing we need is a function that will construct a single node. Following Lisp this will be called CONS - for reasons that are lost in the dark ages of programming. Also to follow Lisp the data part of the node is called CAR and the pointer part is called CDR for even more obscure reasons to do with the assembly language names for particular operations on the machine used to first implement Lisp.

There is no doubt that the use of CONS, CAR and CDR makes things look more advanced. Feel free to rename or just think of them as construct, head and tail.

So history lesson over we can now write the CONS function:

CONS=function(a,b){
        return {CAR:a,CDR: b};
     };

This simply takes two items a and b and returns an object with a as the CAR property and b as the CDR property. Yes this is the start of a linked list and not a pointer or reference in sight.

This isn't the way Lisp does the job and in Lisp CAR and CDR are functions not properties but it is in the spirit of the language we are using i.e. JavaScript.

How can this be a linked list it is far too simple?

To see how it works let's build up a list that stores ABCD. First we start the list off with:

var list=CONS("D",null);

using null as the marker for the end of the list is as close to the original NIL marker used by Lisp.

We now have a list with one node with data "D" and pointer null. 

  [D|---->null

Adding another node is easy:

list=CONS("C",list);

and now we have a list with two nodes:

[C|---->[D|----->null

You should be getting the idea by now and the entire list is created using:

var list=CONS("D",null);
list=CONS("C",list);
list=CONS("B",list);
list=CONS("A",list);

and the entire list is:

   [A|---->[B|---->[C|---->[D|---->[null|

Notice the way that the list variable is used on the left and right of the later CONS function calls. The entire job could be done in one more complex-looking step:

var list2= CONS("A",CONS("B", CONS("C",
                                 CONS("D",null))));

And you will notice that this line ends with a lot of parentheses- something Lisp is well known for. 

Which brings us to the obligatory xkcd cartoon:

A classic if there ever was one.

More cartoon fun at xkcd a webcomic of romance,sarcasm, math, and language 

Scanning a list

Now let's write a small function that prints the list one letter at a time.

You might think that the obvious way to do this would be to use a for loop - but notice the list doesn't have an index variable and it doesn't have a length property.

In fact the Lisp way of doing the job is to use recursion again another feature Lisp is well known for.

To start off the function accepts a list L. If the list empty then the job is done and we return:

function displayList(L){
  if(L===null) return;

If the list isn't empty we can display its head i.e. the CAR:

  console.log(L.CAR);

and pass its "body" i.e. the list minus the head or its CDR to the same display function:

  displayList(L.CDR);
}

You can see that this might be recursion but it is very easy to understand - display the head, chop it off and do it again to what is left. These are the types of jobs that recursion is natural for.

The complete function is:

function displayList(L){
  if(L===null) return;
  console.log(L.CAR);
  displayList(L.CDR);
}

and if you call it using the list constructed earlier:

var list= CONS("A",CONS("B", CONS("C",
                                CONS("D",null))));
displayList(list);

You will see A, B, C, D printed one per line.

Notice that this display function only works with simple linear lists. If you give it a list that is a more general tree structure say then it fails. It is easy to convert to a general display function as we will discover a little later. 

<ASIN:1871962501>

<ASIN:1871962528>