JavaScript may not have pointers but it has everything you need to construct sophisticated data structures if you think about things in the right way. In this article we implement a classical linked list 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

A linked list is one of the most powerful of all data structures in the sense that you can use it to create just about any other data structure.

The principle of the linked list is very simple. It consists of a set of objects usually called nodes that have two properties - data and successor. The data property stores the data that you want to keep in the list and the successor is a "pointer" or a reference to the next node in the list.

Before we look deeper into the linked list we need to make sure that the idea of the JavaScript reference is clearly understood.

References

Back in the early days of computing the pointer really was a pointer to a memory location. That is the pointer was a machine address that gave the exact location of the next node in the list. Today we have moved away from such low level considerations and in place of the pointer we use the reference to another object. The reason that references are safe compared to pointers is that you can't accidentally start using an area of memory that you were never supposed to have access to due to some weird or even intentional "bug". A reference is managed by the runtime system and can only reference valid objects.

So if references are so good where are they in JavaScript?

The answer is that they are what you use all the time without ever really thinking about it.

When you store a value in a variable e.g.

var a=10;

then you are doing just that - storing the value 10 in the variable a.

However when you do the same thing but with an object you don't store the object in the variable but a reference to the object.

For example:

var a={x:20,y:10};

doesn't store the object in the variable a. It stores a reference, which you can think of as a safe "pointer" to the object.

To see that this is true all you have to do is store a in another variable b say:

var b=a;

If the object {x:20,y:10} was stored in variable a then a copy of the object would now be stored in variable b. Of course this isn't what happens. A reference to the object is stored in a and the assignment stores a copy of the reference in variable b. After the assignment both a and b reference or "point" to the same object. You can prove this quite easily

b.y=20;
alert(a.y);

and you will see at once that storing something in b.y modifies a.y. Both a and b reference the same object.

A Simple Node

Now that we have the basics of references clearly established it it time to build a node - a data structure that can be linked to another data structure. A node has two fields:

var node1={
 data:null,
 next:null
};

data stores the data held in the node and next is a reference to the next node in the list.

You can set the data field simply:

node1.data="data1";

but there is nothing to set the next field to. Clearly to create a linked list of nodes we need at least one more node:

var node2={
 data:null,
 next:null
};

and now we can write:

node2.data="data2";
node1.next=node2;

where the important assignment is to the next property. Now node1.next "points" to node2 and node2 really is the next node in the list:

node1
 data->data1
 next ---------------->node2
                        data-> data2
                        next->null

You can see that you could carry this on indefinitely building up a bigger and bigger linked list.

You should also be able to see how to do basic operations like adding a new node - simply set the end node's next property to the new node. You can traverse the list starting from the first node by simply following the "next" properties e.g.

node1.next.data

is the data stored in node2.

Notice that because JavaScript is weakly typed you can store any data you care to in the data property - numbers, strings, objects, even another list. This ability for a list to have another list stored as one of its nodes is one of the most powerful features of the list data structure. It means that you can use the list to build more complex structures such as trees and acyclic graphs - but more of this in another article.

<ASIN:1871962579>

<ASIN:1871962560>

<ASIN:1871962501>

<ASIN:1871962528>