JavaScript Data Structures - The Linked List
Written by Ian Elliot   
Monday, 14 January 2013
Article Index
JavaScript Data Structures - The Linked List
Traversing the list
When to use a list

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.

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

See also:

 

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.

Banner

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

A List Object

Of course manually creating  node each time you need one and manually adding it to the list isn't really the best way to do things. A much better idea is to create a List object that can be used without much information about its inner workings. That is the List object stores and retrieves data from a linked list.

Obviously as we are going to want to create perhaps multiple List objects we are going to have to implement a constructor

function List(){

We also need an easy way to create a node and one possible way is to provide the constructor function List with a makeNode method:

List.makeNode=function(){
 return {data:null,next:null};
};

If this seems strange to you recall that a function is also an object and can have methods and properties. This approach is similar to providing class or static methods and properties.

We need some properties to record the start and end of the list:

this.start=null;
this.end=null;

It is possible to avoid having to record the end of the list by performing a traverse of the entire list each time you need to access the end - but in most cases storing a reference tot he end of the list is more economical.

Next we need an add instance function. This uses the static makeNode function and has to set the start, end and next references correctly. If the list has just been started then start and end will be null and we need to set them:

this.add=function (data){
 if(this.start===null){
   this.start=List.makeNode();
   this.end=this.start;
 }

You can see that in this case all you have to do is set the start and end to reference the new node.

If the list has already had some nodes added you need to add the new node to the end of the list and update end and the next property of the previous end node:

 else{
  this.end.next=List.makeNode();
  this.end=this.end.next;
 };

And finally we can set the data in the new node:

this.end.data=data;
};

Using the add method we can create a linked list with as many nodes as we care to use. For example:

var list=new List();
for(var i=1;i<=10;i++){
 list.add(i);
};

creates a list with ten nodes containing data 1 to 10.

<ASIN:0596805527>

<ASIN:0470344725>

<ASIN:1449393632>

<ASIN:0321700953>

 



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.