JavaScript data structures - a Lisp-like list
Written by Mike James   
Tuesday, 03 May 2011
Article Index
JavaScript data structures - a Lisp-like list
Towards a general structure

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

 

This is one of a series of articles on implementing data structures in JavaScript.

See also:

 

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

The first is that JavaScript really is a very powerful language and has many of the facilities which makes Lisp an attractive language.

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 point 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 Lips 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.

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.

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 brackets - something Lisp is well known for.

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);
}

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 tht 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, however.

Banner

<ASIN:0596517742>
<ASIN:0470684143>
<ASIN:0596517742>
<ASIN:1590597273>



Last Updated ( Tuesday, 15 January 2013 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.