A general structure

How do you create a general structure using this form of linked list?

The answer is you just do it. For example consider a binary tree with a root and two leaves A and B. You can create this in one instruction:

var tree=CONS(CONS("A",null),CONS("B",null));

This creates a structure something like:

[ |---->[B|---->[null|


 | 
 V
[A|---->[null|

How do you access the elements in this structure?

You simply use the CAR and CDR properties.

For example, to display the stored "A" you would use:

console.log(tree.CAR.CAR);

and to display the stored B you would use:

console.log(tree.CDR.CAR);

Now you can think of CAR as say "left branch" and CDR as "right branch".

To extend the example to a four-item binary tree is just as easy although the parentheses are tricky:

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

This builds a tree that is the equivalent of:

    /\
   /\ /\
  A B C D

Again you can use the CAR and CDR properties to walk the tree and access elements.

For example to display the A and B items you would use:

console.log(tree.CAR.CAR.CAR);
console.log(tree.CAR.CDR.CAR);

and to display the other half of the tree:

console.log(tree.CDR.CAR.CAR);
console.log(tree.CDR.CDR.CAR);

You should have the idea well enough now to create and use a tree of any size.

In practice you wouldn't do it manually in this way but instead create some functions that allow you to build the tree without quite so many parentheses getting in the way.

Tree walk

Of course if you try the display function we wrote earlier on the tree it doesn't work because it assumes that a CAR is always going to be a data item to display rather than perhaps another list. That is the function assumes that CAR will always be a data item and CDR another list.

To convert it to work with any sort of list we have to deal with the possibility that either CAR or CDR might be a list.

The function starts in the same way:

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

If the list isn't null then we need to display its CAR but only if it isn't a list that needs further processing.

So how can you tell if L.CAR is a list?

Simple, if it is a list then it too has a CAR and CDR property.

So we can test using:

if (L.CAR.CAR === undefined) {

and if it is undefined then we can assume that L.CAR is a data item and we display it:

console.log(L.CAR);

If it isn't a data item then it is a list and we need to process it further so the else part of the if statement is:

}else{
 displayList(L.CAR);
}

Finally when the if statement is complete all of the tree that is accessible following the CAR side of the first node has been displayed i.e. the left part of the tree.

All we need to do now is process the right side as before:

 displayList(L.CDR);
}

Yes this is recursion again and not quite as easy to follow as for the linear list. 

The complete function is:

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

If you try it out using: 

tree=CONS(CONS(CONS("A"ll),CONS("B",null)),
            CONS(CONS("C",null),CONS("D",null)));
displayList(tree);

Then you will see A,B,C,D printed as the terminal nodes of the tree are encountered left-to-right.

Notice that now that the display function treats both the CAR and CDR parts of a node as a possible list the function can deal with lists of any complexity.

Where next

So where to from here?

You can work your way though the Lisp set of functions if you really want, to implementing each one as you go, but you still won't have a Lisp implementation. Lisp is more than just list handling but not much more. What is amazing is that so much can be achieved using so little. Back in the early days when Lisp was first invented it really didn't amount to much more than CONS, CAR and CDR functions and it captured the minds of its users because it was so simple and yet so powerful.

JavaScript has many of the facilities of Lisp and if you want to you can write Lisp-style functional programs using it, but is is just one aspect of this chameleon of a language.

In most cases it is better to try to understand JavaScript on its own terms and try not to make it look like another language.

What is important is that you have seen the technique of using properties to reference other objects and so have learned another way of building up complex data structures. 

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

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

 

 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:0596517742>

<ASIN:1871962501>

<ASIN:1871962528>